Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-23T12:51:55.788Z 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: [email protected])
YUVAL PERES
Affiliation:
Microsoft Research, 1 Microsoft Way, Redmond, WA 98052, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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