Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-06T16:13:07.916Z Has data issue: false hasContentIssue false
  • English
  • Français

Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures

Published online by Cambridge University Press:  19 September 2013

ROBIN PEMANTLE  and
YUVAL PERES
ROBIN PEMANTLE
Affiliation:
Department of Mathematics, University of Pennsylvania, 209 South 33rd Street, Philadelphia, PA 19104, USA (e-mail: pemantle@math.upenn.edu)
YUVAL PERES
Affiliation:
Microsoft Research, 1 Microsoft Way, Redmond, WA 98052, USA (e-mail: peres@microsoft.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let {X1 , . . , Xn} be a collection of binary-valued random variables and let f : {0, 1}n → $\mathbb{R}$ be a Lipschitz function. Under a negative dependence hypothesis known as the strong Rayleigh condition, we show that f − ${\mathbb E}$f satisfies a concentration inequality. The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; some familiar examples from these classes are generalized negative binomials and spanning tree measures. For instance, any Lipschitz-1 function of the edges of a uniform spanning tree on vertex set V (e.g., the number of leaves) satisfies the Gaussian concentration inequality

\begin{linenomath}$${{\mathbb P} (f - {\mathbb E} f \geq a) \leq \exp \biggl( - \frac{a^2}{8 \, |V|} \biggr) }.$$\end{linenomath}
We also prove a continuous version for concentration of Lipschitz functionals of a determinantal point process.

Keywords

60G55
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 140 - 160
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. and Spencer, J. (2008) The Probabilistic Method, third edition, Wiley.CrossRefGoogle Scholar
[2]Borcea, J., Brändén, P. and Liggett, T. (2009) Negative dependence and the geometry of polynomials. J. Amer. Math. Soc. 22 521–567.CrossRefGoogle Scholar
[3]Burton, R. and Pemantle, R. (1993) Local characteristics, entropy and limit theorems for uniform spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21 1329–1371.CrossRefGoogle Scholar
[4]Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493–507.CrossRefGoogle Scholar
[5]Dubhashi, D. and Ranjan, D. (1998) Balls and bins: A study in negative dependence. Random Struct. Alg. 13 99–124.3.0.CO;2-M>CrossRefGoogle Scholar
[6]Durrett, R. (2004) Probability: Theory and Examples, third edition, Duxbury Press.Google Scholar
[7]Farcomeni, A. (2008) Some finite sample properties of negatively dependent random variables. Theor. Prob. Math. Statist. 77 155–163.CrossRefGoogle Scholar
[8]Feder, T. and Mihail, M. (1992) Balanced matroids. In Annual ACM Symposium on Theory of Computing, pp. 26–38.CrossRefGoogle Scholar
[9]Freedman, D. (1975) On tail probabilities for martingales. Ann. Probab. 3 100–118.CrossRefGoogle Scholar
[10]Ginibre, J. (1965) Statistical ensembles of complex, quaternion, and real matrices. J. Math. Phys. 6 440–449.CrossRefGoogle Scholar
[11]Gharan, S., Saberi, A. and Singh, M. (2011) A randomized rounding approach to the Traveling Salesman Problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 550–559.CrossRefGoogle Scholar
[12]Goldman, A. (2010) The palm measure and the Voronoi tesselation for the Ginibre process. Ann. Appl. Probab. 20 90–128.CrossRefGoogle Scholar
[13]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.CrossRefGoogle Scholar
[14]Hough, J. B., Krishnapur, M., Peres, Y. and Virág, B. (2006) Determinantal processes and independence. Probability Surveys 3 206–229.CrossRefGoogle Scholar
[15]Hough, J. B., Krishnapur, M., Peres, Y. and Virág, B. (2009) Zeros of Gaussian Analytic Functions and Determinantal Point Processes, Vol. 51 of University Lecture Series, AMS.CrossRefGoogle Scholar
[16]Johansson, K. (2003) Discrete polynuclear growth and determinantal processes. Comm. Math. Phys. 242 277–329.CrossRefGoogle Scholar
[17]Kallenberg, O. (1986) Random Measures, fourth edition, Academic Press.Google Scholar
[18]Karlin, S. and McGregor, J. (1959) Confidence probabilities. Pacific J. Math. 9 1141–1164.CrossRefGoogle Scholar
[19]Le Caer, G. and Ho, J. S. (1990) The Voronoi tesselation generated from eigenvalues of complex random matrices. J. Phys. A 23 3279–3295.CrossRefGoogle Scholar
[20]Liggett, T. (1977) The stochastic evolution of an infinite system of interacting particles. In Ecole de Probabilites de Saint Flour VI, 1976, Vol. 598 of Lecture Notes in Mathematics, Springer, pp. 187–248.CrossRefGoogle Scholar
[21]Lyons, R. (2003) Determinantal probability measures. IHES 98 167–212.CrossRefGoogle Scholar
[22]McDiarmid, C. (1989) On the method of bounded differences. In Surveys in Combinatorics (Siemons, J., ed.), Vol. 41 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 148–188.Google Scholar
[23]Panconesi, A. and Srinivasan, A. (1997) Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput. 26 350–368.CrossRefGoogle Scholar
[24]Pemantle, R. (2000) Toward a theory of negative dependence. J. Math. Phys. 41 1371–1390.CrossRefGoogle Scholar
[25]Peres, Y. and Virág, B. (2005) Zeros of the i.i.d. Gaussian power series: A conformally invariant determinantal process. Acta Math. 194 1–35.CrossRefGoogle Scholar
[26]Soshnikov, A. (2000) Determinantal random point fields. Uspekhi Mat. Nauk 55 107–160.Google Scholar
[27]Tutte, W. (1971) Introduction to the Theory of Matroids, Vol. 37 of Modern Analytic and Computational Methods in Science and Mathematics, American Elsevier.Google Scholar
[28]Wagner, D. G. (2011) Multivariate stable polynomials: Theory and application. Bull. Amer. Math. Soc. 48 53–84.CrossRefGoogle Scholar