Geometric influences

DOI10.1214/11-AOP643zbMATH Open1255.60015arXiv0911.1601OpenAlexW3037758910MaRDI QIDQ428146FDOQ428146

Authors: Nathan Keller, Elchanan Mossel, Arnab Sen 

Publication date: 19 June 2012

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

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.

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

Recommendations

• scientific article; zbMATH DE number 3863213
• scientific article; zbMATH DE number 124750

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)

Cites Work

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

Cited In (14)

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

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)