Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures

2011/08/02 by Pemantle, Robin, Peres, Yuval · 1 citation
#60E15 #60G55 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1108.0687

Abstract

Let X₁ ,..., X_n be a collection of binary valued random variables and let f : 0,1ⁿ -> R be a Lipschitz function. Under a negative dependence hypothesis known as the \em strong Rayleigh condition, we show that f - E f satisfies a concentration inequality generalizing the classical Gaussian concentration inequality for sums of independent Bernoullis: P (S_n - E S_n > a) < exp (-2 a² / n). 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, the number of vertices of odd degree in a uniform random spanning tree of a graph satisfies a Gaussian concentration inequality with n replaced by |V|, the number of vertices. We also prove a continuous version for concentration of Lipschitz functionals of a determinantal point process.

Cited by

• Normalized matching property for competing urn models

Related

• Variations and extensions of the Gaussian concentration inequality, Part I
• Concentration of Lipschitz Functions of Negatively Dependent Variables
• Concentration inequalities for some negatively dependent binary random variables
• Variations and extensions of the Gaussian concentration inequality, Part II
• Log concavity and concentration of Lipschitz functions on the Boolean\n hypercube