论文标题
Lipschitz功能的原木凹和集中度
Log concavity and concentration of Lipschitz functions on the Boolean hypercube
论文作者
论文摘要
众所周知，其密度是$ e^{ - v} $的度量，其中$ v $是$ \ rr^n $均匀凸出的潜力。为了在离散的超越立方体上搜索对日志covity的概念，我们考虑$ \ { - 1,1 \}^n $的措施，其多利线扩展$ f $满足$ \ log \ log \ nabla^2 f（x）\ preceqβ\ id $ geq 0 $，我们指的是$ - c，c。我们证明，这些度量满足了一个非平凡的浓度结合，即任何锤lipchitz测试功能$φ$满足$ \var_ν[φ] \ leq n^{2-c_β} $ for $c_β> 0 $。作为推论，我们证明了一种浓度，以表现出所谓的瑞利特性。即，我们表明，对于在任何外部磁场（或指数倾斜）下，任意两个坐标之间的相关性是非阳性的，锤型 - lipschitz函数的相关性。
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 $β\geq 0$, which we refer to as $β$-semi-log-concave. We prove that these measures satisfy a nontrivial concentration bound, namely, any Hamming Lipchitz test function $φ$ satisfies $\Var_ν[φ] \leq n^{2-C_β}$ for $C_β>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.
