Geometric influences

DOI10.1214/11-AOP643MaRDI QIDQ428146zbMATH OpenOpenAlexFDO

Authors Nathan Keller, Elchanan Mossel, Arnab Sen

Publication date 19 June 2012

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.1601, https://projecteuclid.org/euclid.aop/1336136061

zbMATH Keywords

isoperimetric inequalityGaussian measureproduct spaceinfluencesKahn-Kalai-linial influence bound

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We present a new definition of influences in product spaces of continuous distributions. Our definition is geometric, and for monotone sets it is identical with the measure of the boundary with respect to uniform enlargement. We prove analogs of the Kahn-Kalai-Linial (KKL) and Talagrand's influence sum bounds for the new definition. We further prove an analog of a result of Friedgut showing that sets with small "influence sum" are essentially determined by a small number of coordinates. In particular, we establish the following tight analog of the KKL bound: for any set in $mathbb{R}^n$ of Gaussian measure $t$, there exists a coordinate $i$ such that the $i$th geometric influence of the set is at least $ct(1-t)sqrtlogn/n$, where $c$ is a universal constant. This result is then used to obtain an isoperimetric inequality for the Gaussian measure on $mathbb{R}^n$ and the class of sets invariant under transitive permutation group of the coordinates.

Cites work

• scientific article; zbMATH DE number 5504150 (Why is no real title available?)
• scientific article; zbMATH DE number 3503316 (Why is no real title available?)
• An Efron-Stein inequality for nonsymmetric statistics
• An approximate zero-one law
• Boolean functions with low average sensitivity depend on few coordinates
• Decision Trees and Influences of Variables Over Product Probability Spaces
• Every monotone graph property has a sharp threshold
• Extremal properties of half-spaces for log-concave distributions
• IX. On the problem of the most efficient tests of statistical hypotheses
• Infinite dimensional isoperimetric inequalities in product spaces with the supremum distance
• Influence and sharp-threshold theorems for monotonic measures
• Isoperimetric problem for uniform enlargement
• Lévy-Gromov's isoperimetric inequality for an infinite dimensional diffusion generator
• Noise stability of functions with low influences: invariance and optimality
• On Russo's approximate zero-one law
• On the influences of variables on Boolean functions in product spaces
• Porosity and \(\sigma\)-porosity
• Symétrisation dans l'espace de Gauss.
• The Brunn-Minkowski inequality in Gauss space
• The influence of variables in product spaces

Cited in

(14)

• On the influences of variables on Boolean functions in product spaces
• On the failure of concentration for the \(\ell_\infty\)-ball
• The critical threshold for Bargmann-Fock percolation
• Probabilistic view of voting, paradoxes, and manipulation
• Influence and sharp-threshold theorems for monotonic measures
• On quantitative noise stability and influences for discrete and continuous models
• Talagrand inequality at second order and application to Boolean analysis
• Influences in Product Spaces: KKL and BKKKL Revisited
• Hypercontractive measures, Talagrand's inequality, and influences
• Bargmann-Fock percolation is noise sensitive
• Perimeters, uniform enlargement and high dimensions
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Geometric influences. II: Correlation inequalities and noise sensitivity
• Quantitative correlation inequalities via extremal power series

This page was built for publication: Geometric influences

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