Talagrand inequality at second order and application to Boolean analysis

DOI10.1007/S10959-019-00957-2MaRDI QIDQ2181612zbMATH OpenOpenAlexWikidataFDO

Authors Kevin Tanguy

Publication date 19 May 2020

Published in Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

hypercontractivityfunctional inequalitiesinfluencesBoolean analysis

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Continuous-time Markov processes on general state spaces (60J25) Boolean functions (06E30) Contents, measures, outer measures, capacities (28A12)

Abstract: This note is concerned with an extension, at second order, of an inequality on the discrete cube $C_n=-1,1$ (equipped with the uniform measure) due to Talagrand (cite{TalL1L2}). As an application, the main result of this note is a Theorem in the spirit of a famous result from Kahn, Kalai and Linial (cf. cite{KKL}) concerning the influence of Boolean functions. The notion of the influence of a couple of coordinates $(i,j)in{1,ldots,n}^2$ is introduced in section 2 and the following alternative is obtained : for any Boolean function $f,:,C_{n}o0,1$, either there exists a coordinate with influence at least of order $(1/n{)}^{1/(1+eta)}$, with $,0<eta<1$ (independent of $f$ and $n$) or there exists a couple of coordinates $(i,j)in{1,ldots,n}^2$ with $ieqj$, with influence at least of order $(logn/n{)}^2$. In section 4, it is shown that this extension of Talagrand inequality can also be obtained, with minor modifications, for the standard Gaussian measure $gamm{a}_n$ on $mathbb{R}^n$ ; the obtained inequality can be of independent interest. The arguments rely on interpolation methods by semigroup together with hypercontractive estimates. At the end of the article, some related open questions are presented.

Recommendations

• Talagrand's influence inequality revisited
• Hypercontractive measures, Talagrand's inequality, and influences
• On boundaries and influences
• Edge-Isoperimetric Inequalities and Influences
• Geometric influences. II: Correlation inequalities and noise sensitivity

Cites work

• A Gaussian small deviation inequality for convex functions
• Analysis and geometry of Markov diffusion operators
• Analysis of Boolean Functions
• Concentration inequalities. A nonasymptotic theory of independence
• Dichotomies, structure, and concentration in normed spaces
• Every monotone graph property has a sharp threshold
• Geometric influences
• Higher order concentration of measure
• Hypercontractive measures, Talagrand's inequality, and influences
• Interpolation, correlation identities, and inequalities for infinitely divisible variables
• L'algèbre de Lie des gradients itérés d'un générateur markovien---développements de moyennes et entropies
• Logarithmic Sobolev Inequalities
• Logarithmic Sobolev inequalities for finite Markov chains
• Noise Sensitivity of Boolean Functions and Percolation
• Non asymptotic variance bounds and deviation inequalities by optimal transport
• On Gaussian and Bernoulli covariance representations
• On Russo's approximate zero-one law
• Probability in Banach spaces. Isoperimetry and processes
• Quantitative relation between noise sensitivity and influences
• Some superconcentration inequalities for extrema of stationary Gaussian processes
• Superconcentration and related topics
• The concentration of measure phenomenon
• The free Markoff field

Cited in

(6)

• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Boolean functions with small second-order influences on the discrete cube
• Hypercontractive measures, Talagrand's inequality, and influences
• Talagrand's influence inequality revisited
• Edge-Isoperimetric Inequalities and Influences
• Strong contraction and influences in tail spaces

This page was built for publication: Talagrand inequality at second order and application to Boolean analysis

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