Concentration Of Lipschitz Functionals Of Determinantal And Other Strong Rayleigh Measures

Let X_1 ,…, X_n be a collection of binary valued random variables and let f : {0,1}^n -> 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^2 / 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.