Log concavity and concentration of Lipschitz functions on the Boolean hypercube

DOI10.1016/J.JFA.2022.109392MaRDI QIDQ2076308zbMATH OpenOpenAlexFDO

Authors Ronen Eldan, Omer Shamir

Publication date 16 February 2022

Published in Journal of Functional Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.13108

zbMATH Keywords

concentration inequalitieslog concave measuresRayleigh distributionsBoolean hypercube

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Inequalities; stochastic orderings (60E15) Characterization and structure theory of statistical distributions (62E10)

Abstract: It is well-known that measures whose density is the form $e^{-V}$ where $V$ is a uniformly convex potential on $R{R}^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 $$, for $$, which we refer to as $$-semi-log-concave. We prove that these measures satisfy a nontrivial concentration bound, namely, any Hamming Lipchitz test function $varphi$ satisfies $$ for $$. 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.

Recommendations

• The log-convex density conjecture
• The log convex density conjecture in hyperbolic space
• On Hadamard inequality for log-concave functions
• On the Hadamard's inequality for log-convex functions on the coordinates
• The Log-Concavity Conjecture for the Duistermaat-Heckman Measure Revisited
• Proof of the log-convex density conjecture
• A strong log-concavity property for measures on Boolean algebras
• Concentration of non‐Lipschitz functions and applications
• On concentration inequalities for vector-valued Lipschitz functions
• Log-convexity and log-concavity of hypergeometric-like functions

Cites work

• scientific article; zbMATH DE number 51724 (Why is no real title available?)
• Balls and bins: A study in negative dependence
• Brownian motion. With an appendix by Oded Schramm and Wendelin Werner
• Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
• Concentration of measures supported on the cube
• Inequalities with applications to percolation and reliability
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• Log-concavity and strong log-concavity: a review
• Negatively correlated random variables and Mason's conjecture for independent sets in matroids
• On a combinatorial conjecture concerning disjoint occurrences of events
• Some concepts of negative dependence
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
• Thin shell implies spectral gap up to polylog via a stochastic localization scheme
• Towards a theory of negative dependence.

Cited in

(5)

• Concentration of measure, classification of submeasures, and dynamics of \(L_0\)
• Bounds on the covariance matrix of the Sherrington-Kirkpatrick model
• Asymptotic geometric analysis: achievements and perspective
• Concentration of measures supported on the cube
• Parallel discrete sampling via continuous walks

This page was built for publication: Log concavity and concentration of Lipschitz functions on the Boolean hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2076308)