Chapter 11: Gaussian space and Invariance Principles

The final destination of this chapter is a proof of the following theorem due to Mossel, O’Donnell, and Oleszkiewicz [MOO05a,MOO10], first mentioned in Chapter 5.25:

Majority Is Stablest Theorem Fix $\rho \in (0,1)$. Let $f : \{-1,1\}^n \to [-1,1]$ have $\mathop{\bf E}[f] = 0$. Then, assuming $\mathbf{MaxInf}[f] \leq \epsilon$, or more generally that $f$ has no $(\epsilon,\epsilon)$-notable coordinates, \[ \mathbf{Stab}_\rho[f] \leq 1 – \tfrac{2}{\pi} \arccos \rho + o_\epsilon(1). \]

This bound is tight; recalling Theorem 2.44, the bound $1 – \tfrac{2}{\pi} \arccos \rho$ is achieved by taking $f = \mathrm{Maj}_n$, the volume-$\tfrac{1}{2}$ Hamming ball indicator, for $n \to \infty$. More generally, in Section 7 we’ll prove the General-Volume Majority Is Stablest Theorem, which shows that for any fixed volume, “Hamming ball indicators have maximal noise stability among small-influence functions”. There are two main ideas underlying this theorem. The first is that “functions on Gaussian space” are a special case of small-influence Boolean functions. In other words, a Boolean function may always be a “Gaussian function in disguise”. This motivates analysis of Gaussian functions, the topic introduced in Sections 1 and 2. It also means that a prerequisite for proving the (General-Volume) Majority Is Stablest Theorem is proving its Gaussian special cases, namely, Borell’s Isoperimetric Theorem (Section 3) and the Gaussian Isoperimetric Inequality (Section 4). In many ways, working in the Gaussian setting is nicer because tools like rotational symmetry and differentiation are available.

The second idea is the converse to the first: In Section 6 we prove the Invariance Principle, a generalization of the Berry–Esseen Central Limit Theorem, which shows that any low-degree (or uniformly noise-stable) Boolean function with small influences is approximable by a Gaussian function. In fact, the Invariance Principle roughly shows that given such a Boolean function, if you plug any independent mean-$0$, variance-$1$ random variables into its Fourier expansion, the distribution doesn’t change much. In Section 7 we use the Invariance Principle to prove the Majority Is Stablest Theorem by reducing to its Gaussian special case, Borell’s Isoperimetric Theorem.

2 comments to Chapter 11: Gaussian space and Invariance Principles

  • Andy D

    Hi Ryan, this introduction gives us a clear idea of the “second idea” used, the Invariance Principle; by contrast the first idea is left somewhat mysterious. Is it possible to sharpen the description?

  • Hi Andy, thanks for the comment. I kind of see what you mean; let me think about it. On the other hand, I’ve been striving (and failing) to keep these chapter intros short (take a look at the ones from the early chapters…)

Leave a Reply to Andy D Cancel reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>