Log concavity and concentration of Lipschitz functions on the Boolean hypercube

Abstract

It is well-known that measures whose density is the form $e^{-V}$ where $V$ is a uniformly convex potential on $\RR^n$ attain strong concentration properties. In search of a notion of log-concavity on the discrete hypercube, we consider measures on $\{-1,1{\}}^n$ whose multi-linear extension $f$ satisfies $\log \nabla^2 f(x) \preceq β\Id$, for $\beta \ge 0$, which we refer to as $\beta$-semi-log-concave. We prove that these measures satisfy a nontrivial concentration bound, namely, any Hamming Lipchitz test function $\phi$ satisfies $\Var_ν[φ] \leq n^{2-C_β}$ for $C_{\beta }>0$. As a corollary, we prove a concentration bound for measures which exhibit the so-called Rayleigh property. Namely, we show that for measures such that under any external field (or exponential tilt), the correlation between any two coordinates is non-positive, Hamming-Lipschitz functions admit nontrivial concentration.

arXiv commentPreliminary version