![Real Analysis in Computer Science_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Real%20Analysis%20in%20Computer%20Science_hi-res.jpg?h=e2b42a27&itok=jpgiJZrK)
Abstract
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).