Fall 2013

Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures

Tuesday, October 1st, 2013 11:40 am12:30 pm

Add to Calendar

Let f(X_1 , ..., X_n} be a a Lipschitz function of n binary random variables.

If the variables X_i are independent, it is classical that f satisfies a Gaussian concentration inequality.

We show that such an inequality holds for a large class of negatively dependent variables known as strong Rayleigh. (This inequality is easy and well known if f is linear under weaker hypothesis on the X_i, but new for nonlinear f).The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; the most familiar example is the uniform spanning tree. For instance, any Lipschitz function of the edges of a uniform spanning tree in a given graph (e.g., the number of leaves) satisfies a Gaussian concentration inequality. This answers a question posed by Elchanan Mossel. (Joint work with Robin Pemantle).