Talagrand’s inequality and hypercontractivity
1. Talagrand’s inequality
Theorem 1 (Talagrand) Let . Let be the uniform measure on .
This improves on the KKL theorem. Indeed, it implies
Theorem 2 (Kahn, Kalai, Linial) Let . Then there exists such that
Indeed, for any ,
Today, I will prove Talagrand’s inequality in a slightly extended context.
2. Markov chains
A Markov kernel on a finite set is a function such that for all . Say is reversible with respect to invariant probability measure if
The corresponding Dirichlet form is .
The spectral gap is the best constant such that .
The logarithmic Sobolev constant is the best constant in
It is stronger than spectral gap, (with our choice of normalization).
Spectral gap is equivalent to exponential decay under heat flow.
Logarithmic Sobolev inequality is equivalent to hypercontractivity of heat flow,
On a product space , there is a product kernel, and
Example 1 Let .
In other words, , , .
Example 2 Product of copies of previous example.
For this example, Talagrand’s inequality states that
On the biased cube, i.e. , , , (Bonami-Beckner inequality).
2.1. Proof of Talagrand’s inequality for products
Now I give the proof.
Assume . Write
We treat separately small and large values of . Write
Commutation: commutes with the ‘s, so
by hypercontractivity and Hölder, given by
gives Talagrand’s inequality.
The main ingredients of the proof were
- Expression of energy as a sum of terms.
- Global hypercontractivity.
This carries over to certain non product situations.
2.2. The symmetric group
Let be the symmetric group, equipped with the kernel corresponding to the random walk associated to the generating set consisting of all transpositions, i.e.
Commutation holds: .
The spectral gap is due to Diaconis-Shahshahani in 1981.
Hypercontractivity was proven by Diaconis and Saloff-Coste (1996) and Lee-Yau (1998).
The above proof automatically gives the following Talagrand inequality.
In terms of influences of Boolean functions, there exists a transposition such that
It is not that exciting since it follows from spectral gap. For Talagrand’s inequality to improve on spectral gap, must be substantially larger than , i.e.
3. Continuous setting
3.1. Gaussian case
From now on, is the Gaussian measure on . Then Talagrand’s inequality reads
The proof goes along similar lines. is replaced by the Ornstein-Uhlenbeck semigroup
It commutes with partial derivatives. Hypercontractivity holds with .
On , use measure . Assume a lower bound on the Hessian (the correct formulation involves the Ricci curvature of the semigroup). Then commutation holds up to a factor :
And one gets a Talagrand inequality.
3.3. The round sphere
Let . Write
Commutation holds. . This gives a Talagrand inequality
4. Talagrand inequality
Apply Talagrand’s inequality to characteristic functions of sets. The -influence makes sense (Keller, Mossel, Sen 2010).
In the Gaussian case, it has the following geometric meaning. Given , let
Theorem 3 (Keller, Mossel, Sen 2010) There exists such that
This is optimal.
4.2. Proof of the -influence bound
I show that a slight modification of above proof gives Keller, Mossel and Sen’s result.
Change into :
Use spectral gap,
Trick: If , is Lipschitz,
This easily follows from the integral representation of the Ornstein-Uhlenbeck semigroup. Estimate
Talgrand’s inequality for norms reads
From there, the application to influences is immediate.
4.3. Connections with isoperimetry
On , use Gaussian measure again. The Talagrand inequality reads
In terms of influences, there exists such that
In case one only one factor, this says that
We recognize a quantitative form of the Gaussian isoperimetric inequality
as tends to . So we merely lost a constant factor.