
In this chapter we complete the proof of the Hypercontractivity Theorem for uniform $\pm 1$ bits. We then generalize the $(p,2)$ and $(2,q)$ statements to the setting of arbitrary product probability spaces, proving the following:
The General Hypercontractivity Theorem Let $(\Omega_1, \pi_1), \dots, (\Omega_n, \pi_n)$ be finite probability spaces, in each of which every outcome has probability at least $\lambda$. Let $f \in L^2(\Omega_1 \times \cdots \times \Omega_n, \pi_1 \otimes \cdots \otimes \pi_n)$. Then for any $q > 2$ and $0 \leq \rho \leq \frac{1}{\sqrt{q1}} \cdot \lambda^{1/21/q}$, \[ \\mathrm{T}_\rho f\_q \leq \f\_2 \quad\text{and}\quad \\mathrm{T}_\rho f\_2 \leq \f\_{q'}. \] (In fact, the upper bound on $\rho$ can be slightly relaxed to the value stated in Theorem 17 of this chapter.)
Continue reading Chapter 10: Advanced hypercontractivity
The history of the Hypercontractivity Theorem is complicated.
Continue reading Chapter 9 notes
Recalling the social choice setting of Chapter 2.5, consider a $2$candidate, $n$voter election using a monotone voting rule $f : \{1,1\}^n \to \{1,1\}$. We assume the impartial culture assumption (that the votes are independent and uniformly random), but with a twist: one of the candidates, say $b \in \{1,1\}$, is able to secretly bribe $k$ voters, fixing their votes to $b$. (Since $f$ is monotone, this is always the optimal way for the candidate to fix the bribed votes.) How much can this influence the outcome of the election?
Continue reading §9.6: Highlight: The Kahn–Kalai–Linial Theorem
With the $(2,q)$ and $(p,2)$Hypercontractivity Theorems in hand, let’s revisit some applications we saw in Sections 1 and 2.
Continue reading §9.5: Applications of hypercontractivity
At this point we have established that if $f : \{1,1\} \to {\mathbb R}$ then for any $p \leq 2 \leq q$, \[ \\mathrm{T}_{\sqrt{p1}} f\_2 \leq \f\_p, \qquad \\mathrm{T}_{1/\sqrt{q1}} f\_q \leq \f\_2. \] We would like to extend these facts to the case of general $f : \{1,1\}^n \to {\mathbb R}$; i.e., establish the $(p,2)$ and $(2,q)$Hypercontractivity Theorems stated at the beginning of the chapter. A natural approach is induction.
Continue reading §9.4: Twofunction hypercontractivity and induction
Although you can get a lot of mileage out of studying the $4$norm of random variables, it’s also natural to consider other norms.
Continue reading §9.3: $(2,q)$ and $(p,2)$hypercontractivity for a single bit
An immediate consequence of the Bonami Lemma is that for any $f : \{1,1\}^n \to {\mathbb R}$ and $k \in {\mathbb N}$, \begin{equation} \label{eqn:24hyperconk} \\mathrm{T}_{1/\sqrt{3}} f^{=k}\_4 = \tfrac{1}{\sqrt{3}^k} \f^{=k}\_4 \leq \f^{=k}\_2. \end{equation}
Continue reading §9.2: Small subsets of the hypercube are noisesensitive
As anyone who has worked in probability knows, a random variable can sometimes behave in rather “unreasonable” ways. It may be never close to its expectation. It might exceed its expectation almost always, or almost never. It might have finite $1$st, $2$nd, and $3$rd moments, but an infinite $4$th moment. All of this poor behaviour can cause a lot of trouble — wouldn’t it be nice to have a class of “reasonable” random variables?
Continue reading §9.1: Lowdegree polynomials are reasonable
In 1970, Bonami proved the following central result:
The Hypercontractivity Theorem Let $f : \{1,1\}^n \to {\mathbb R}$ and let ${1 \leq p \leq q \leq \infty}$. Then $\\mathrm{T}_\rho f\_q \leq \f\_p$ for $0 \leq \rho \leq \sqrt{\tfrac{p1}{q1}}$.
Continue reading Chapter 9: Basics of hypercontractivity


Recent comments