Concentration of a Lipschitz Function of Negatively Associated Random Variables (Yuval Peres)

Let   f : \{ 0 , 1 \}^n \to \mathbb{R} be a Lipschitz function.  If the binary variables \{ X_1 , \ldots , X_n \} are independent, then it is well known that f(X)=f(X_1, \ldots,X_n) satisfies a Gaussian concentration inequality (*) \mathbb{P} \left( f(X) - \mathbb{E} f(X) \ge a \right) \leq \exp(- \frac{a^2}{c n} ) for a suitable c>0.


Does such an inequality also hold if the binary variables  \{ X_1 , \ldots , X_n \}   are negatively associated (i.e., increasing  functions of disjoint subsets of these  variables are negatively correlated) rather than independent?


This is classical when f is an increasing linear function of X, and therefore also holds for any linear Lipschitz function f (with a different constant c).

In 2009, Elchanan Mossel (personal communication) asked whether (*)  holds for negatively associated X_i and nonlinear Lipschitz functions. This is still open. A central motivation was the ensemble of uniform spanning trees in a graph G, which was proved in [1] to have negative association (the relevant binary variables are indexed by the edges of G and are indicators for inclusion in the uniform spanning tree.)

In [2] the inequality (*) is proved under a more restrictive negative dependence hypothesis known as the strong Rayleigh condition,  defined in [3]. The class of strong Rayleigh measures includes determinantal measures (which include the uniform spanning tree) and also weighted uniform matroids and spanning tree measures. However, it is hard to verify directly if a measure is strong Rayleigh, and not all negatively associated measures on the hypercube satisfy this condition.


[1] T. Feder and M. Mihail. (1992). Balanced matroids. Annual ACM Symposium on Theory of Computing, 26-38, 1992.

[2] R. Pemantle and Y. Peres (2014). Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures. Combinatorics, Probability and Computing 23, 140–160.  

[3]  J. Borcea, P. Branden, and T. Liggett (2009).  Negative dependence and the geometry of polynomials. J. AMS, 22:521–567, 2009.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s