Theorem 2.32 and Proposition 2.57, discussed in Section 2, were essentially proved by Titsworth in 1962 [Tit62] (see also [Tit63]). More precisely, Titsworth solved a version of the problem from Exercise 7. His motivation was in fact the construction of “interplanetary ranging systems” for measuring deep space distances; e.g. the distance from Earth to Venus. The connection between ranging systems and boolean functions was suggested by his advisor, Golomb. Titsworth [Tit62] was also the first to compute the Fourier expansion of $\mathrm{Maj}_n$. His approach involved generating functions and contour integration. Other approaches have used special properties of binomial coefficients [Bra87] or of Kravchuk polynomials [Kal02]. The asymptotics of $\mathbf{W}^{k}[\mathrm{Maj}_n]$ described in Section 3 may have first appeared in [Kal02], with the error bounds being from [O'D03]. Kravchuk polynomials were introduced in [Kra29].

The Berry–Esseen Theorem is due independently to Berry [Ber41] and Esseen [Ess42]. Shevtsova [She10a] has the record for the smallest known constant $B$ that works therein: $.56$, as mentioned in our theorem statement. The nonuniform version described in Exercise 32 is due to Bikelis [Bik66]. The multidimensional version Theorem 33 stated in Exercise 34 is due to Bentkus [Ben04]. Sheppard proved his formula in 1899 [She99]. The results of Theorem 15 may have appeared first in [O'D04,O'D03].

The Level-1 Inequality should probably be considered folklore; it was perhaps first published in [Tal96] and we have followed his proof. The first half of the $\frac{2}{\pi}$ Theorem is from [KKMO07]; the second half is from [MORS10]. The previous best closeness result for the FKN Theorem had $\delta/2$ in place of our $\delta/4$. That result was from [FKN02]; their proof (like ours) relies on having a separate proof of closeness $O(\delta)$. Kindler and Safra [KS02] (see also [Kin02]) gave a self-contained proof of the $\delta/2$ bound relying only on the Hoeffding bound. The result of Exercise 6 is from [KKMO07]; Exercise 40 was suggested by Servedio.

Peres’s Theorem was published in 2004 [Per04] but was mentioned by Benjamini, Kalai, and Schramm [BKS99], who proved the worse upper bound $O(\delta^{1/4})$. The proof we presented is a simplification due to Gopalan, and incorporates an idea of [DHK+10,HKM10a]. These latter two works are responsible for the best known bounds in the direction of the Gotsman–Linial Conjecture, mentioned at the end of Section 5 (in particular, for Exercise 43).

25. Complete the proof of Theorem 19 by showing that $(1-\tfrac{k+1}{n} +\tfrac{k}{n^2})^{-1/2} \leq 1+2k/n$ for all $1 \leq k \leq n/2$.
26. Using just the facts that $\mathbf{Stab}_\rho[\mathrm{Maj}_n] \to \frac{2}{\pi} \arcsin \rho$ for all $\rho \in [-1,1]$ and that $\mathbf{Stab}_\rho[\mathrm{Maj}_n] = \sum_{k \geq 0} \mathbf{W}^{k}[\mathrm{Maj}_n] \rho^k$, deduce that $\lim_{n \to \infty} \mathbf{W}^{k}[\mathrm{Maj}_n] \to [\rho^k](\frac{2}{\pi} \arcsin \rho)$ for all $k \in {\mathbb N}$. (Hint: by induction on $k$, always taking $\rho$ “small enough”.)

27. 1. For $0 \leq j \leq m$ integers, show that $\hat{\lVert} \mathrm{Maj}_{2m+1}^{=2j+1} \hat{\rVert}_1 = \binom{m}{j} \frac{1}{2j+1} \cdot \frac{2m+1}{2^{2m}}\binom{2m}{m}$.
    2. Deduce that $\hat{\lVert} \mathrm{Maj}_{2m+1} \hat{\rVert}_1 = \mathop{\bf E}\left[\frac{1}{2\boldsymbol{X}+1}\right] \cdot \frac{2m+1}{2^{m}}\binom{2m}{m}$, where $\boldsymbol{X} \sim \mathrm{Binomial}(m,1/2)$.
    3. Deduce that $\hat{\lVert} \mathrm{Maj}_n \hat{\rVert}_1 \sim \frac{2}{\sqrt{\pi}} \frac{1}{\sqrt{n}} 2^{n/2}$.
28. 1. Show that for each odd $k \in {\mathbb N}$, \[ \left(\tfrac{2}{\pi}\right)^{3/2} k^{-3/2} \leq [\rho^k] (\tfrac{2}{\pi} \arcsin \rho) \leq \left(\tfrac{2}{\pi}\right)^{3/2} k^{-3/2}(1+O(1/k)). \] (Hint: Stirling’s approximation.)
    2. Prove Corollary 20. (Hint: for the second statement you’ll need to approximate the sum $\sum_{\text{odd } j > k} \left(\tfrac{2}{\pi}\right)^{3/2} j^{-3/2}$ by an integral.)
29. For integer $0 \leq k \leq n$, define $\mathcal{K}_k : \{-1,1\}^n \to {\mathbb R}$ by $\mathcal{K}_k(x) = \sum_{|S| = k} x^S$. Since $\mathcal{K}_k$ is symmetric, the value $\mathcal{K}_k(x)$ depends only on the number $z$ of $-1$’s in $x$; or equivalently, on $\sum_{i=1}^n x_i$. Thus we may define $K_k : \{0, 1, \dots, n\} \to {\mathbb R}$ by $K_k(z) = \mathcal{K}_k(x)$ for any $x$ with $\sum_i x_i = n – 2z$.
    1. Show that $K_k(z)$ can be expressed as a degree-$k$ polynomial in $z$. It is called the Kravchuk (or Krawtchouk) polynomial of degree $k$. (The dependence on $n$ is usually implicit.)
    2. Show that $\sum_{k=0}^n \mathcal{K}_k(x) = 2^n \cdot 1_{(1, \dots, 1)}(x)$.
    3. Show for $\rho \in [-1,1]$ that $\sum_{k=0}^n \mathcal{K}_k(x)\rho^k = 2^n\mathop{\bf Pr}[\boldsymbol{y} = (1, \dots, 1)]$, where $\boldsymbol{y} = N_\rho(x)$.
    4. Deduce the generating function identity $K_k(z) = [\rho^k]((1-\rho)^z(1+\rho)^{n-z})$.
30. Prove Proposition 21.
31. Prove Proposition 22 using the Central Limit Theorem. (Hint for $\mathbf{W}^{1}[f_n]$: use symmetry to show it equals the square of $\mathop{\bf E}[f_n({\boldsymbol{x}})\mathop{{\textstyle \sum}} \frac{1}{\sqrt{n}} {\boldsymbol{x}}_i]$.)
32. Consider the setting of Theorem 13. Let $\boldsymbol{S} = \sum_i a_i {\boldsymbol{x}}_i$ where ${\boldsymbol{x}} \sim \{-1,1\}^n$, and let $\boldsymbol{Z} \sim \mathrm{N}(0,1)$.
    1. Show that $\mathop{\bf Pr}[|\boldsymbol{S}| \geq t]$, $\mathop{\bf Pr}[|\boldsymbol{Z}| \geq t] \leq 2\exp(-t^2/2)$ for all $t \geq 0$.
    2. Recalling $\mathop{\bf E}[|\boldsymbol{Y}|] = \int_0^\infty \mathop{\bf Pr}[|\boldsymbol{Y}| \geq t]\,dt$ for any random variable $\boldsymbol{Y}$, use the Berry–Esseen Theorem (and Remark 12, Exercise 16) to show \[ \Bigl|\mathop{\bf E}[|\boldsymbol{S}|] – \mathop{\bf E}[|\boldsymbol{Z}|]\Bigr| \leq O(\epsilon T + \exp(-T^2/2)) \] for any $T \geq 1$.
    3. Deduce $|\mathop{\bf E}[|\boldsymbol{S}|] – \sqrt{2/\pi}| \leq O(\epsilon\sqrt{\log(1/\epsilon)})$.
    4. Improve $O(\epsilon\sqrt{\log(1/\epsilon)})$ to the bound $O(\epsilon)$ stated in Theorem 13 by using the nonuniform Berry–Esseen Theorem, which states that the bound $B\beta$ in the Berry–Esseen Theorem can be improved to $C\beta\cdot\frac{1}{1+|u|^3}$ for some constant $C$.
33. Consider the sequence of LTFs defined in Proposition 22. Show that \[ \lim_{n \to \infty} \mathbf{Stab}_\rho[f_n] = \Lambda_\rho(\mu). \] Here $\mu = \overline{\Phi}(t)$ and $\Lambda_\rho(\mu)$ is the Gaussian quadrant probability defined by $\Lambda_\rho(\mu) = \mathop{\bf Pr}[\boldsymbol{z}_1 > t, \boldsymbol{z}_2 > t]$, where $\boldsymbol{z}_1, \boldsymbol{z}_2$ are standard Gaussians with correlation $\mathop{\bf E}[\boldsymbol{z}_1\boldsymbol{z}_2] = \rho$.
34. In this exercise you will complete the justification of Theorem 14 using the following multidimensional Berry-Esseen Theorem:

    Theorem 33 Let $\boldsymbol{X}_1, \dots, \boldsymbol{X}_n$ be independent ${\mathbb R}^d$-valued random vectors, each having mean zero. Write $\boldsymbol{S} = \sum_{i=1}^n \boldsymbol{X}_i$ and assume $\Sigma = \mathop{\bf Cov}[\boldsymbol{S}]$ is invertible. Let $\boldsymbol{Z} \sim \mathrm{N}(0,\Sigma)$ be a $d$-dimensional Gaussian with the same mean and covariance matrix as $\boldsymbol{S}$. Then for all convex sets $U \subseteq {\mathbb R}$, \[ |\mathop{\bf Pr}[\boldsymbol{S} \in U] – \mathop{\bf Pr}[\boldsymbol{Z} \in U]| \leq C d^{1/4} \beta, \] where $C$ is a universal constant, $\beta = \sum_{i=1}^n \mathop{\bf E}[\|\Sigma^{-1/2} \boldsymbol{X}_i\|_2^3]$, and $\|\cdot\|_2$ denotes the Euclidean norm on ${\mathbb R}^d$.

    1. Let $\Sigma = \begin{bmatrix} 1 & \rho \\ \rho & 1 \end{bmatrix}$ where $\rho \in (-1,1)$. Show that \[ \Sigma^{-1} = \begin{bmatrix} 1 & -\rho \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & (1 -\rho^2)^{-1} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ -\rho & 1 \end{bmatrix}. \]
    2. Compute $y^\top \Sigma^{-1} y$ for $y = \begin{bmatrix} \pm a \\ \pm a \end{bmatrix} \in {\mathbb R}^2$.
    3. Complete the proof of Theorem 14.
35. Show that Theorem 30 is essentially optimal by exhibiting functions $f : \{-1,1\}^n \to \{-1,1\}$ with $\widehat{f}(1) = 1-\delta/2$ and $\mathbf{W}^{1}[f] \geq 1 – \delta + \Omega(\delta^2 \log(1/\delta))$, for a sequence of $\delta$ tending to $0$.
36. Prove Corollary 29.
37. Fill in the details of the proof of Theorem 30.
38. From Theorem 31 we know that the statement “$\mathbf{I}[f] \leq O_k(1) \sqrt{n}$ for all $f \in \mathrm{PTF}_n$” implies the statement “$\mathbf{NS}_{\delta}[f] \leq O_k(1) \sqrt{\delta}$ for all $f \in \bigcup_n \mathrm{PTF}_{n,k}$”. Show also the converse implication. (Hint: Exercise 2.37.)
39. Estimate carefully the asymptotics of $\mathbf{I}[f]$, where $f \in \mathrm{PTF}_{n,k}$ is as in the strongest form of the Gotsman–Linial Conjecture.
40. Let $A, B \subseteq \{-1,1\}^n$ have cardinality $\alpha 2^n$ each, $\alpha \leq 1/2$. Thinking of $\{-1,1\}^n \subset {\mathbb R}^n$, let $\mu_A, \mu_B \in {\mathbb R}^n$ be the centers of mass of $A$, $B$. Show that these centers are close in Euclidean distance: $\|\mu_A – \mu_B\|_2 \leq O(\sqrt{\log(1/\alpha)})$.
41. Show that the Gaussian isoperimetric function satisfies $\mathcal{U} \cdot \mathcal{U}\ \prime\prime = -1$ on $(0,1)$. Deduce that $\mathcal{U}$ is concave.
42. Fix $\alpha \in (0, 1/2)$. Let $f : \{-1,1\}^n \to [-1,1]$ satisfy $\mathop{\bf E}[|f|] \leq \alpha$ and $|\widehat{f}(i)| \leq \epsilon$ for all $i \in [n]$. Show that $\mathbf{W}^{1}[f] \leq \mathcal{U}(\alpha) + C \epsilon$, where $\mathcal{U}$ is the Gaussian isoperimetric function and where the constant $C$ may depend on $\alpha$. (Hint: you will need the nonuniform Berry–Esseen Theorem from Exercise 32.)
43. In this exercise you will show by induction on $k$ that $\mathbf{Inf}[f] \leq 2 n^{1-1/2^k}$ for all $f : \{-1,1\}^n \to \{-1,1\}$ which are degree-$k$ PTFs. The $k = 0$ case is trivial. So for $k > 0$, suppose $f = \mathrm{sgn}(p)$ where $p : \{-1,1\}^n \to {\mathbb R}$ is a degree-$k$ polynomial which is never $0$.
    1. Show for $i \in [n]$ that $\mathop{\bf E}[f({\boldsymbol{x}}) {\boldsymbol{x}}_i \mathrm{sgn}(\mathrm{D}_i p({\boldsymbol{x}}))] = \mathbf{Inf}_i[f]$. (Hint: first use the decomposition $f = x_i \mathrm{D}_i f + \mathrm{E}_i f$ to reach $\mathop{\bf E}[\mathrm{D}_i f \cdot \mathrm{sgn}(\mathrm{D}_i p)]$; then show that $\mathrm{D}_if = \mathrm{sgn}(\mathrm{D}_i p)$ whenever $\mathrm{D}_i f \neq 0$.)
    2. Conclude that $\mathbf{I}[f] \leq \mathop{\bf E}[|\sum_i {\boldsymbol{x}}_i \mathrm{sgn}(\mathrm{D}_i p({\boldsymbol{x}}))|]$. Remark: when $k = 2$ and thus each $\mathrm{sgn}(\mathrm{D}_i p)$ is an LTF, it is conjectured that this bound is still $O(\sqrt{n})$.
    3. Apply Cauchy–Schwarz and deduce \[ \mathbf{I}[f] \leq \sqrt{n + \sum_{i \neq j} \mathop{\bf E}[{\boldsymbol{x}}_i {\boldsymbol{x}}_j \mathrm{sgn}(\mathrm{D}_i p({\boldsymbol{x}})) \mathrm{sgn}(\mathrm{D}_j p({\boldsymbol{x}}))]}. \]
    4. Use Exercise 2.15 and the AM-GM inequality to obtain $\mathbf{I}[f] \leq \sqrt{n + \sum_i \mathbf{I}[\mathrm{sgn}(\mathrm{D}_i p)]}$.
    5. Complete the induction.

Speaking of which, Li-Yang Tan heroically scribed those Barbados lectures and did a terrific job. You can find the resulting notes on analysis of boolean functions here.

Finally, the open problems in analysis of boolean functions, compiled at the Simons Symposium, have been arXived. Daniel Kane even solved one of them in the meantime!

1. 1. Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is an LTF. Show that it can be expressed as $f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots a_n x_n)$ where the $a_i$’s are integers. (Hint: first obtain rational $a_i$’s by a perturbation.)
   2. Show also that a degree-$d$ PTF has a representation in which all of the degree-$d$ polynomial’s coefficients are integers.
2. Let $f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots a_n x_n)$ be an LTF.
   1. Show that if $a_0 = 0$ then $\mathop{\bf E}[f] = 0$. (Hint: show that $f$ is in fact an odd function.)
   2. Show that if $a_0 \geq 0$ then $\mathop{\bf E}[f] \geq 0$. Show that the converse need not hold.
   3. Suppose $g : \{-1,1\}^n \to \{-1,1\}$ is an LTF with $\mathop{\bf E}[f] = 0$. Show that $g$ can be represented as $g(x) = \mathrm{sgn}(c_1 x_1 + \cdots + c_n x_n)$.
3. Suppose $f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots a_n x_n)$ is an LTF with $|a_1| \geq |a_2| \geq \cdots \geq |a_n|$. Show that $\mathbf{Inf}_1[f] \geq \mathbf{Inf}_2[f] \geq \cdots \geq \mathbf{Inf}_n[f]$. (Hint: why does it suffice to prove this for $n=2$?)
4. 1. Show that the number of functions $f : \{-1,1\}^n \to \{-1,1\}$ which are LTFs is at most $2^{n^2 + O(n)}$. (Hint: Chow’s Theorem.)
   2. More generally, show that the number of functions $f : \{-1,1\}^n \to \{-1,1\}$ which are degree-$k$ PTFs is at most $2^{n^{k+1} + O(n)}$.
5. 1. Suppose $\ell : \{-1,1\}^n \to {\mathbb R}$ is defined by $\ell(x) = a_0 + a_1 x_1 + \cdots a_n x_n$. Define $\widetilde{\ell} : \{-1,1\}^{n+1} \to {\mathbb R}$ by $\widetilde{\ell}(x_0, \dots, x_n) = a_0 x_0 + \ell(x)$. Show that $\|\widetilde{\ell}\|_1 = \|\ell\|_1$ and $\|\widetilde{\ell}\|^2_2 = \|\ell\|_2^2$.
   2. Complete the proof of Theorem 2.
6. Let $f : \{-1,1\}^n \to \{-1,1\}$ be an unbiased linear threshold function. Show that $\mathbf{Inf}_i[f] \geq \frac{1}{\sqrt{2 n}}$ for some $i \in [n]$, improving the KKL Theorem for LTFs.
7. Consider the following “correlation distillation” problem (cf. Exercise 2.49). For each $i \in [n]$ there is a number $\rho_i \in [-1,1]$ and an independent sequence of pairs of $\rho_i$-correlated bits, $(\boldsymbol{a}_1^{(1)}, \boldsymbol{b}_2^{(1)})$, $(\boldsymbol{a}_1^{(2)}, \boldsymbol{b}_2^{(2)})$, $(\boldsymbol{a}_1^{(3)}, \boldsymbol{b}_2^{(3)})$, etc. Party $A$ on Earth has access to the stream of bits $\boldsymbol{a}_1^{(1)}$, $\boldsymbol{a}_1^{(2)}$, $\boldsymbol{a}_1^{(3)}$,$\dots$. and a party $B$ on Venus has access to the stream $\boldsymbol{b}_1^{(1)}$, $\boldsymbol{b}_1^{(2)}$, $\boldsymbol{b}_1^{(3)}$, $\dots$. Neither party knows the numbers $\rho_1, \dots, \rho_n$. The goal is for $B$ to estimate these correlations. To assist in this, $A$ can send a small number of bits to $B$. A reasonable strategy is for $A$ to send $f(\boldsymbol{a}^{(1)})$, $f(\boldsymbol{a}^{(2)})$, $f(\boldsymbol{a}^{(3)})$, $\dots$ to $B$, where $f : \{-1,1\}^n \to \{-1,1\}$ is some boolean function. Using this information $B$ can try to estimate $\mathop{\bf E}[f(\boldsymbol{a}) \boldsymbol{b}_i]$ for each $i$.
   1. Show that $\mathop{\bf E}[f(\boldsymbol{a}) \boldsymbol{b}_i] = \widehat{f}(i) \rho_i$.
   2. This motivates choosing an $f$ for which all $\widehat{f}(i)$ are large. If we also insist all $\widehat{f}(i)$ be equal, show that majority functions $f$ maximize this common value.
8. For $n \geq 2$, let $\boldsymbol{f} : \{-1,1\}^n \to \{-1,1\}$ be a randomly chosen function (as in Exercise 1.8). Show that $\hat{\lVert} \boldsymbol{f} \hat{\rVert}_\infty \leq 2\sqrt{n} 2^{-n/2}$ except with probability at most $2^{-n}$.
9. Prove Theorem 6.

10. 1. Give as simple a proof as you can that the parity function $\chi_{[n]} : \{-1,1\}^n \to \{-1,1\}$ is not a PTF of degree $n-1$.
    2. Show that if $f : \{-1,1\}^n \to \{-1,1\}$ is not $\pm \chi_{[n]}$ then it is a PTF of degree $n-1$. (Hint: consider $f^{\leq n-1}$.)
11. For each $k \in {\mathbb N}^+$, show that there is a degree-$k$ PTF $f$ with $\mathbf{W}^{\leq k}[f] < 2^{1-k}$.
12. In this exercise you will show that threshold-of-parities circuits can be effectively simulated by threshold-of-threshold circuits, but not the converse.
    1. Let $f : \{-1,1\}^n \to \{-1,1\}$ be a symmetric function. Show that $f$ is computable as the sum of at most $2n$ LTFs, plus a constant.
    2. Deduce that if $f : \{-1,1\}^n \to \{-1,1\}$ is computable by a size-$s$ threshold-of-parities circuit then it is also computable by a size-$2ns$ threshold-of-thresholds circuit.
    3. Show that the complete quadratic function $\mathrm{CQ}_n : {\mathbb F}_2^{n} \to \{-1,1\}$ (see Exercise 1.1) is computable by a size-$2n$ threshold-of-thresholds circuit.
    4. Assume $n$ even. Show that any threshold-of-parities circuit for $\mathrm{CQ}_n$ requires size $2^{n/2}$.
13. Let $f : \{-1,1\}^n \to \{-1,1\}$ be computable by a DNF of size $s$. Show that $f$ has a PTF representation of sparsity $O(n s^2)$. (Hint: approximate the ANDs using Theorem 10.)
14. In contrast to the previous exercise, show that there is a function $f : \{-1,1\}^n \to \{-1,1\}$ computable by a depth-$3$ $\mathsf{AC}^0$ circuit (see Chapter 4.5) but requiring threshold-of-parities circuits of size at least $n^{\log n}$. (Hint: involve the inner product mod $2$ function and Exercise 4.12.)
15. Let $\mathcal{F}$ be a nonempty collection of subsets $S \subseteq [n]$. For each $a \in \{-1,1\}^n$, write $1_{\{a\}} : \{-1,1\}^n \to \{0,1\}$ for the indicator of $\{a\}$, write $1_{\{a\}}^\mathcal{F} : \{-1,1\}^n \to {\mathbb R}$ for $\sum_{S \in \mathcal{F}} \widehat{1_{\{a\}}}(S)\,\chi_S$, and write $\psi_a = \frac{2^n}{|\mathcal{F}|} \cdot 1_{\{a\}}^\mathcal{F}$.
    1. Show that $\psi_a(a) = 1$ and $\mathop{\bf E}[\psi_a^2] = \tfrac{1}{|\mathcal{F}|}$. Show also that for all $x \in \{-1,1\}^n$, $\psi_a(x) = \psi_x(a)$ and $\sum_{a : a \neq x} \psi_a(x)^2 = \frac{2^n}{|\mathcal{F}|} – 1$.
    2. Fix $0 < \epsilon < 1$ and suppose that $|\mathcal{F}| \geq (1 – \tfrac{\epsilon^2}{6n}) 2^n$. Let $\boldsymbol{f} : \{-1,1\}^n \to \{-1,1\}$ be a random function as in Exercise 1.8. Show that for each $x \in \{-1,1\}^n$, except with probability at most $4^{-n}$ it holds that $|\sum_{a : a \neq x} \boldsymbol{f}(a) \psi_a(x)| < \epsilon$.
    3. Deduce that for all but a $2^{-n}$ fraction of functions $f : \{-1,1\}^n \to \{-1,1\}$, there a multilinear polynomial $q : \{-1,1\}^n \to {\mathbb R}$ supported on the monomials $\{\chi_S : S \in \mathcal{F}\}$ such that $\|f – q\|_\infty < \epsilon$.
    4. Deduce that all but a $2^{-n}$ fraction of functions $f : \{-1,1\}^n \to \{-1,1\}$ have PTF representation of degree at most $n/2 + O(\sqrt{n \log n})$.
16. 1. Show that in the Berry–Esseen Theorem we can also conclude \[ |\mathop{\bf Pr}[\boldsymbol{S} < u] – \mathop{\bf Pr}[\boldsymbol{Z} < u]| \leq B \epsilon. \] (Hint: you’ll need that $\lim_{\delta \to 0^+} \mathop{\bf Pr}[\boldsymbol{Z} \leq u - \delta] = \mathop{\bf Pr}[\boldsymbol{Z} \leq u]$.)
    2. Deduce that if $I \subseteq {\mathbb R}$ is any interval we can also conclude \[ |\mathop{\bf Pr}[\boldsymbol{S} \in I] – \mathop{\bf Pr}[\boldsymbol{Z} \in I]| \leq 2B \beta. \]
17. Show that the assumptions $\mathop{\bf E}[\boldsymbol{X}_i] = 0$ and $\sum_{i=1}^n \mathop{\bf Var}[\boldsymbol{X}_i] = 1$ in the Berry–Esseen Theorem are not restrictive, as follows. Let $\boldsymbol{X}_1, \dots, \boldsymbol{X}_n$ be independent random variables with finite means and variances. Let $\boldsymbol{S} = \sum_{i=1}^n \boldsymbol{X}_i$ and let $\boldsymbol{Z} \sim \mathrm{N}(\mu,\sigma^2)$, where $\mu = \sum_{i=1}^n \mathop{\bf E}[\boldsymbol{X}_i]$ and $\sigma^2 = \sum_{i=1}^n \mathop{\bf Var}[\boldsymbol{X}_i]$. Assuming $\sigma^2 > 0$, show that for all $u \in {\mathbb R}$, \[ |\mathop{\bf Pr}[\boldsymbol{S} \leq u] – \mathop{\bf Pr}[\boldsymbol{Z} \leq u]| \leq B \epsilon / \sigma^3, \] where \[ \epsilon = \sum_{i=1}^n \|\boldsymbol{X}_i - \mathop{\bf E}[\boldsymbol{X}_i]\|_3^3. \]

18. 1. Use the generalized Binomial Theorem to compute the power series for $(1-z^2)^{-1/2}$, valid for $|z| < 1$.
    2. Integrate to obtain the power series for $\arcsin z$ given in Section 3, valid for $|z| < 1$.
    3. Confirm that equality holds also for $z = \pm 1$.
19. Verify that the random vector $\vec{\boldsymbol{S}}$ defined in equation (6) of Section 2 has $\mathop{\bf E}[\vec{\boldsymbol{S}}_1] = \mathop{\bf E}[\vec{\boldsymbol{S}}_2] = 0$, $\mathop{\bf E}[\vec{\boldsymbol{S}}_1^2] = \mathop{\bf E}[\vec{\boldsymbol{S}}_2^2] = 1$, $\mathop{\bf E}[\vec{\boldsymbol{S}}_1\vec{\boldsymbol{S}}_2] = \rho$; i.e., $\mathop{\bf E}[\vec{\boldsymbol{S}}] = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$ and $\mathop{\bf Cov}[\vec{\boldsymbol{S}}] = \begin{bmatrix} 1 & \rho \\ \rho & 1 \end{bmatrix}$.
20. In this exercise you will prove Sheppard’s Formula.
    1. Let $\boldsymbol{g}_1, \boldsymbol{g}_2$ be independent standard Gaussians and let \[ \boldsymbol{g}_1' = \boldsymbol{g}_1, \qquad \boldsymbol{g}_2' = \rho \boldsymbol{g}_1 + \sqrt{1-\rho^2} \boldsymbol{g}_2. \] Show that $(\boldsymbol{g}_1′, \boldsymbol{g}_2′)$ has the same distribution as the random vector $(\boldsymbol{z}_1, \boldsymbol{z}_2)$ in Sheppard’s formula.
    2. Assume for now that $\rho \in [0,1)$. Show that $\boldsymbol{g}_1′, \boldsymbol{g}_2′ > 0$ if and only if $(\boldsymbol{g}_1, \boldsymbol{g}_2)$ is in a certain region $R \subseteq {\mathbb R}^2$ consisting of a quadrant plus a wedge of angle $\arcsin \rho$.
    3. Using the circular symmetry of the random vector $(\boldsymbol{g}_1, \boldsymbol{g}_2)$, deduce Sheppard’s formula for $\rho \in [0,1)$.
    4. Treat the cases $\rho \in (-1,0)$, $\rho = \pm 1$.
21. Prove Corollary 17.
22. Fix $n$ odd. Using Theorem 16 show that $|\widehat{\mathrm{Maj}_n}(S)|$ is a decreasing function of $|S|$ for odd $1 \leq |S| \leq \frac{n-1}{2}$. Deduce (using also Corollary 17) that $\hat{\lVert} \mathrm{Maj}_n \hat{\rVert}_\infty = \mathrm{Maj}_n(\{1\}) \sim \frac{\sqrt{2/\pi}}{\sqrt{n}}$.
23. Prove Corollary 18.
24. Prove Theorem 15. (Hint: Corollary 18).

Indeed the idea here is correct, as was shown by Peres in 1999:

Peres’s Theorem Let $f : \{-1,1\}^n \to \{-1,1\}$ be any linear threshold function. Then $\mathbf{NS}_\delta[f] \leq O(\sqrt{\delta})$.

Pleasantly, the proof is quite simple and uses no heavy tools like the Central Limit Theorem. Before getting to it, let’s remark on an application to learning theory.

Peres’s Theorem immediately gives that LTFs have their Fourier spectrum $\epsilon$-concentrated up to degree $O(1/\epsilon^2)$ (Proposition 3.3) and hence the class of LTFs is learnable from random examples with error $\epsilon$ in time $n^{O(1/\epsilon^2)}$ (Corollary 3.34). The latter result is not too impressive since it’s been long known that LTFs are learnable in time $\mathrm{poly}(n, 1/\epsilon)$ using linear programming. However the noise sensitivity approach is much more flexible. Consider the concept class \[ \mathcal{C} = \{h = g(f_1, \dots, f_s) \mid \text{$f_1, \dots, f_s : \{-1,1\}^n \to \{-1,1\}$ are LTFs}\}. \] For each $h : \{-1,1\}^n \to \{-1,1\}$ in $\mathcal{C}$, Peres’s Theorem and a union bound (Exercise 2.38) imply that $\mathbf{NS}_\delta[h] \leq O(s \sqrt{\epsilon})$. Thus from Corollary 3.34 we get that the class $\mathcal{C}$ is learnable in time $n^{O(s^2/\epsilon^2)}$. This is the only known way of showing even that an AND of two LTFs is learnable with error $.01$ in time $\mathrm{poly}(n)$.

The trick for proving Peres’s Theorem is to employ a fairly general technique for bounding noise sensitivity using average sensitivity (total influence):

Theorem 31 Let $\delta \in (0,1/2]$ and let $A : {\mathbb N}^+ \to {\mathbb R}$. Let $\mathcal{C}$ be a class of boolean-valued functions closed under negation and identification of input variables. Suppose that each $f \in \mathcal{C}$ with domain $\{-1,1\}^n$ has $\mathbf{I}[f] \leq A(n)$. Then each $f \in \mathcal{C}$ has $\mathbf{NS}_\delta[f] \leq \frac{1}{m}A(m)$, where $m = \lfloor 1/\delta \rfloor$.

Proof: Fix any $f : \{-1,1\}^n \to \{-1,1\}$ from $\mathcal{C}$. Since noise sensitivity is an increasing function of the noise parameter (see the discussion surrounding Proposition 2.50) we may replace $\delta$ by $1/m$. Thus our task is to upper-bound $\mathbf{NS}_{1/m}[f] = \mathop{\bf Pr}[f({\boldsymbol{x}}) \neq f(\boldsymbol{y})]$ where ${\boldsymbol{x}} \sim \{-1,1\}^n$ is uniformly random and $\boldsymbol{y} \in \{-1,1\}^n$ is formed from ${\boldsymbol{x}}$ by negating each bit independently with probability $1/m$. The rough idea of the proof is that this is equivalent to randomly partitioning ${\boldsymbol{x}}$’s bits into $m$ parts and then negating a randomly chosen part.

More precisely, let $z \in \{-1,1\}^n$ and let $\pi : [n] \to [m]$ be a partition of $[n]$ into $m$ parts. Define \[ g_{z, \pi} : \{-1,1\}^m \to \{-1,1\}, \quad g_{z, \pi}(w) = f(z \circ w^{\pi}), \] where $\circ$ denotes entry-wise multiplication and $w^{\pi} = (w_{\pi(1)}, \dots, w_{\pi(n)}) \in \{-1,1\}^n$. Since $g_{z, \pi}$ is derived from $f$ by negating and identifying input variables it follows that $g_{z,\pi} \in \mathcal{C}$. So by assumption $g_{z,\pi}$ has total influence $\mathbf{I}[g_{z,\pi}] \leq A(m)$ and hence average influence $\pmb{\mathcal E}[g_{z,\pi}] \leq \frac{1}{m} A(m)$ (see Exercise 2.37).

Now suppose $\boldsymbol{z} \sim \{-1,1\}^n$ and $\boldsymbol{\pi} : [n] \to [m]$ are chosen uniformly at random. We certainly have \[ \mathop{\bf E}_{\boldsymbol{z}, \boldsymbol{\pi}}[\pmb{\mathcal E}[g_{\boldsymbol{z},\boldsymbol{\pi}}]] \leq \tfrac{1}{m}A(m). \] To complete the proof we will show that the left-hand side above is precisely $\mathbf{NS}_{1/m}[f]$. Recall that in the experiment for average influence $\pmb{\mathcal E}[g]$ we choose $\boldsymbol{w} \sim \{-1,1\}^m$ and $\boldsymbol{j} \sim [m]$ uniformly at random and check if $g(\boldsymbol{w}) \neq g(\boldsymbol{w}^{\oplus \boldsymbol{j}})$. Thus \[ \mathop{\bf E}_{\boldsymbol{z}, \boldsymbol{\pi}}[\pmb{\mathcal E}[g_{\boldsymbol{z},\boldsymbol{\pi}}]] = \mathop{\bf Pr}_{\boldsymbol{z}, \boldsymbol{\pi}, \boldsymbol{w}, \boldsymbol{j}}[g_{\boldsymbol{z}, \boldsymbol{\pi}}(\boldsymbol{w}) \neq g_{\boldsymbol{z}, \boldsymbol{\pi}}(\boldsymbol{w}^{\oplus \boldsymbol{j}})] = \mathop{\bf Pr}_{\boldsymbol{w}, \boldsymbol{\pi}, \boldsymbol{j}, \boldsymbol{z}}[f(\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}}) \neq f(\boldsymbol{z} \circ (\boldsymbol{w}^{\oplus \boldsymbol{j}})^{\boldsymbol{\pi}})]. \] It is not hard to see that the joint distribution of $\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}}$, $\boldsymbol{z} \circ (\boldsymbol{w}^{\oplus \boldsymbol{j}})^{\boldsymbol{\pi}}$ is the same as that of ${\boldsymbol{x}}$, $\boldsymbol{y}$. To be precise, define $\boldsymbol{J} = \boldsymbol{\pi}^{-1}(\boldsymbol{j})$, distributed as a random subset of $[n]$ in which each coordinate is included with probability $1/m$; and, define $\boldsymbol{\lambda} \in \{-1,1\}^n$ by $\boldsymbol{\lambda}_i = -1$ if and only if $i \in \boldsymbol{J}$. Then \[ \mathop{\bf Pr}_{\boldsymbol{w}, \boldsymbol{\pi}, \boldsymbol{j}, \boldsymbol{z}}[f(\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}}) \neq f(\boldsymbol{z} \circ (\boldsymbol{w}^{\oplus \boldsymbol{j}})^{\boldsymbol{\pi}})] = \mathop{\bf Pr}_{\boldsymbol{w}, \boldsymbol{\pi}, \boldsymbol{j}, \boldsymbol{z}}[f(\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}}) \neq f(\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}} \circ \boldsymbol{\lambda})]. \] But for every outcome of $\boldsymbol{w}$, $\boldsymbol{\pi}$, $\boldsymbol{j}$ (and hence $\boldsymbol{J}$, $\boldsymbol{\lambda}$), we may replace $\boldsymbol{z}$ with $\boldsymbol{z} \circ \boldsymbol{w}^{\boldsymbol{\pi}}$ since they have the same distribution, namely uniform on $\{-1,1\}^n$. Then the above becomes \[ \mathop{\bf Pr}_{\boldsymbol{w}, \boldsymbol{\pi}, \boldsymbol{j}, \boldsymbol{z}}[f(\boldsymbol{z}) \neq f(\boldsymbol{z} \circ \boldsymbol{\lambda})] = \mathbf{NS}_{1/m}[f], \] as claimed. $\Box$

Peres’s Theorem is now a simple corollary of Theorem 31.

Proof of Peres’s Theorem: Let $\mathcal{C}$ be the class of all linear threshold functions. This class is indeed closed under negating and identifying variables. Since each linear threshold function on $m$ bits is unate (i.e., monotone up to negation of some input coordinates, see Exercises 2.5, 2.6), its total influence is at most $\sqrt{m}$ (see Exercise 2.19). Applying Theorem 31 we get that for any LTF $f$ and any $\delta \in (0,1/2]$, \begin{align*} \mathbf{NS}_\delta[f] \leq \tfrac{1}{m}\sqrt{m} &= 1/\sqrt{m} \qquad \text{(for $m = \lfloor 1/\delta \rfloor$)} \\ &\leq O(\sqrt{\delta}). \qquad \qquad \qquad \qquad \qquad\Box \end{align*}

Remark 32 Our proof of Peres’s Theorem attained the upper-bound $\sqrt{1/\lfloor 1/\delta \rfloor}$. This is at most $\sqrt{3/2} \sqrt{\delta}$ for all $\delta \in (0,1/2]$ and it’s also $\sqrt{\delta} + O(\delta^{3/2})$ for small $\delta$. To further improve the constant we can use Theorem 2.32 in place of Exercise 2.19; it implies that all unate $m$-bit functions have total influence at most $\sqrt{2/\pi}\sqrt{m} + O(m^{-1/2})$. This lets us obtain the bound $\mathbf{NS}_\delta[f] \leq \sqrt{2/\pi} \sqrt{\delta} + O(\delta^{3/2})$ for all LTF $f$.

Recall from Theorem 2.44 that $\mathbf{NS}_\delta[\mathrm{Maj}_n] \sim \tfrac{2}{\pi} \sqrt{\delta}$ for large $n$. Thus the constant $\sqrt{2/\pi}$ in the bound from Remark 32 is fairly close to optimal. It seems quite likely that majority’s $\tfrac{2}{\pi}$ is the correct constant here. There is still slack in Peres’s proof because the random functions $g_{\boldsymbol{z}, \boldsymbol{\pi}}$ arising in Theorem 31 are unlikely to be majorities, even if $f$ is. The most elegant possible result in this direction would be to prove the following conjecture of Benjamini, Kalai, and Schramm:

Majority Is Least Stable Conjecture Let $f : \{-1,1\}^n \to \{-1,1\}$ be a linear threshold function, $n$ odd. Then for all $\rho \in [0,1]$, $\mathbf{Stab}_\rho[f] \geq \mathbf{Stab}_\rho[\mathrm{Maj}_n]$.

(This is a precise statement about majority’s noise stability within the class of LTFs; the Majority Is Stablest Theorem refers to its noise stability within the class of small-influence functions.) A very important problem in this area is to extend Peres’s Theorem to polynomial threshold functions. Let \[ \mathrm{PTF}_{n,k} = \{f : \{-1,1\}^n \to \{-1,1\} \mid f \text{ is a PTF of degree at most $k$}\}. \] The goal here is to prove that $\mathbf{NS}_\delta[f] \leq O_k(1) \sqrt{\delta}$ for all $f \in \mathrm{PTF}_{n,k}$. This is currently not known even for $k = 2$. Since $\bigcup_n \mathrm{PTF}_{n,k}$ is closed under negating and identifying variables, a natural approach is to use Theorem 31; it would suffice to show that $\mathbf{I}[f] \leq O_k(1) \sqrt{n}$ for all $f \in \mathrm{PTF}_{n,k}$. In fact, such a total influence bound is also necessary; see the exercises. The desired total influence bound here is a very old conjecture of Gotsman and Linial:

Gotsman–Linial Conjecture Let $f \in \mathrm{PTF}_{n,k}$. Then $\mathbf{I}[f] \leq O_k(1) \sqrt{n}$. More strongly, $\mathbf{I}[f] \leq O(k) \sqrt{n}$. Most strongly, the $f \in \mathrm{PTF}_{n,k}$ of maximal total influence is the symmetric one $f(x) = \mathrm{sgn}(p(x_1 + \cdots + x_n))$, where $p$ is a degree-$k$ univariate polynomial which alternates sign on the $k+1$ values of $x_1 + \cdots + x_n$ closest to $0$.

The strongest form of the Gotsman–Linial Conjecture for $k = 1$ is true by Theorem 2.32. The best results towards the conjecture for higher $k$ are the upper bounds $2n^{1-1/2^k}$ (good for small $k$; see the exercises) and $2^{O(k)} n^{1 – 1/(Ck)}$ (better for large $k$), where $C$ is a fairly small universal constant. Note that the latter implies $\mathbf{NS}_{\delta}[f] \leq 2^{O(k)} \delta^{1/(Ck)}$ for all $f \in \mathrm{PTF}_{n,k}$, a bound which is at least independent of $n$.

There is an additional viewpoint if we think of $f$ as the indicator of a subset $A \subseteq \{-1,1\}^n$ and its noise sensitivity $\mathbf{NS}_{\delta}[f]$ as a notion of $A$’s “surface area”, or “noisy boundary size”. For nearly maximal noise rates — i.e., $\delta = \tfrac{1}{2} – \tfrac{1}{2} \rho$ where $\rho$ is small — we have that $A$’s noisy boundary size is “small” if and only if $\mathbf{W}^{1}[f]$ is “large” (vis-a-vis $A$’s measure). Two examples suggest themselves when thinking of subsets of the Hamming cube with small “boundary”: subcubes and Hamming balls.

Proposition 21 Let $f : {\mathbb F}_2^n \to \{0,1\}$ be the indicator of a subcube of codimension $k \geq 1$ (e.g., the $\mathrm{AND}_k$ function). Then $\mathop{\bf E}[f] = 2^{-k}$, $\mathbf{W}^{1}[f] = k 2^{-2k}$.

Proposition 22 Fix $t \in {\mathbb R}$. Consider the sequence of LTFs $f_n : \{-1,1\}^n \to \{0,1\}$ defined by $f_n(x) = 1$ if and only if $\sum_{i=1}^n \tfrac{1}{\sqrt{n}} x_i > t$. (I.e., $f_n$ is the indicator of the Hamming ball $\{x : \mathrm{Dist}(x, (1, \dots, 1)) < \frac{n}{2} – \frac{t}{2}\sqrt{n}\}$.) Then \[ \lim_{n \to \infty} \mathop{\bf E}[f_n] = \overline{\Phi}(t), \qquad \lim_{n \to \infty} \mathbf{W}^{1}[f_n] = \phi(t)^2. \]

You are asked to verify these facts in the exercises. Regarding Proposition 22, it’s natural for $\phi(t)$ to arise since $\mathbf{W}^{1}[f_n]$ is related to the influences of $f_n$, and coordinates are influential for $f_n$ if and only if $\sum_{i=1}^n \tfrac{1}{\sqrt{n}} x_i {\approx t}$. If we write $\alpha = \lim_{n \to \infty} \mathop{\bf E}[f_n]$ then this proposition can be thought of as saying that $\mathbf{W}^{1}[f_n] \to \mathcal{U}(\alpha)^2$, where $\mathcal{U}$ is defined as follows:

Definition 23 The Gaussian isoperimetric function $\mathcal{U} : [0,1] \to [0,\frac{1}{\sqrt{2\pi}}]$ is defined by $\mathcal{U} = \phi \circ \Phi^{-1}$. This function is symmetric about $1/2$; i.e., $\mathcal{U} = \phi \circ \overline{\Phi}{}^{-1}$.

The name of this function will be explained when we prove the Gaussian isoperimetric inequality in Chapter 11. For now we’ll just use the following fact:

Proposition 24 For $\alpha \to 0^+$, $\mathcal{U}(\alpha) \sim \alpha \sqrt{2 \ln(1/\alpha)}$.

Proof: Write $\alpha = \overline{\Phi}(t)$, where $t \to \infty$. We use the fact that $\overline{\Phi}(t) \sim \phi(t)/t$. Thus \begin{gather*} \alpha \sim \tfrac{1}{\sqrt{2\pi} t}\exp(-t^2/2) \quad \Rightarrow \quad t \sim \sqrt{2\ln (1/\alpha)} \\ \phi(t) \sim \overline{\Phi}(t) \cdot t \quad \Rightarrow \quad \mathcal{U}(\alpha) \sim \alpha \cdot t \sim \alpha \sqrt{2\ln(1/\alpha)}. \Box \end{gather*}

Given Propositions 21 and 22, let’s consider the degree-$1$ Fourier weight of subcubes and Hamming balls asymptotically as their “volume” $\alpha = \mathop{\bf E}[f]$ tends to $0$. For the subcubes we have $\mathbf{W}^{1}[f] = \alpha^2 \log(1/\alpha)$. For the Hamming balls we have $\mathbf{W}^{1}[f_n] \to \mathcal{U}(\alpha)^2 \sim 2\alpha^2 \ln(1/\alpha)$. So in both cases we have an upper bound of $O(\alpha^2 \log(1/\alpha))$.

You should think of this upper bound $O(\alpha^2 \log(1/\alpha))$ as being unusually small. The obvious a priori upper bound, given that $f : \{-1,1\}^n \to \{0,1\}$ has $\mathop{\bf E}[f] = \alpha$, is \[ \mathbf{W}^{1}[f] \leq \mathop{\bf Var}[f] = \alpha(1-\alpha) \sim \alpha. \] Yet subcubes and Hamming balls have degree-$1$ weight which is almost quadratically smaller. In fact the first theorem we will show in this section is the following:

Level-1 Inequality Let $f : \{-1,1\}^n \to \{0,1\}$ have mean $\mathop{\bf E}[f] = \alpha \leq 1/2$. Then \[ \mathbf{W}^{1}[f] \leq O(\alpha^2\log(1/\alpha)). \]

(For the case $\alpha \geq 1/2$, replace $f$ by $1-f$.) Thus all small subsets of $\{-1,1\}^n$ have unusually small $\mathbf{W}^{1}[f]$; or equivalently (in some sense), unusually large “noisy boundary”. This is another key illustration of the idea that the Hamming cube is a “small-set expander”.

Remark 25 The bound in the Level-1 Inequality has a sharp form, $\mathbf{W}^{1}[f] \leq (2+o_\alpha(1)) \alpha^2\ln(1/\alpha)$. Thus Hamming balls are in fact the “asymptotic maximizers” of $\mathbf{W}^{1}[f]$ among sets of small volume $\alpha$. Also, the inequality holds more generally for $f : \{-1,1\}^n \to [-1,1]$ with $\alpha = \mathop{\bf E}[|f|]$.

Remark 26 The name “Level-1 Inequality” is not completely standard; e.g., in additive combinatorics the result would be called Chang’s Inequality. We use this name because we will also generalize to “Level-$k$ Inequalities” in Chapter 10.

So far we considered maximizing degree-$1$ weight among subsets of the Hamming cube of a fixed small volume, $\alpha$. The second theorem in this section is concerned with what happens when there is no volume constraint. In this case, maximizing examples tend to have volume $\alpha = 1/2$; switching the notation to $f : \{-1,1\}^n \to \{-1,1\}$, this corresponds to $f$ being unbiased ($\mathop{\bf E}[f] = 0$). The unbiased Hamming ball is $\mathrm{Maj}_n$, which we know has $\mathbf{W}^{1}[\mathrm{Maj}_n] \to \tfrac{2}{\pi}$. This is quite large. But unbiased subcubes are just the dictators $\chi_i$ and their negations; these have $\mathbf{W}^{1}[\pm \chi_i] = 1$ which is obviously maximal.

Thus the question of which $f : \{-1,1\}^n \to \{-1,1\}$ maximizes $\mathbf{W}^{1}[f]$ has a trivial answer. But this answer is arguably unsatisfactory, since dictators (and their negations) are not “really” functions of $n$ bits. Indeed, when we studied social choice in Chapter 2 we were motivated to rule out functions $f$ having a coordinate with unfairly large influence. And in fact Proposition 2.57 showed that if all $\widehat{f}(i)$ are equal (and hence small) then $\mathbf{W}^{1}[f] \leq \frac{2}{\pi} + o_n(1)$. The second theorem of this section significantly generalizes Proposition 2.57:

The ${\frac{\mathbf 2}{\boldsymbol{\pi}}}$ Theorem Let $f : \{-1,1\}^n \to \{-1,1\}$ satisfy $|\widehat{f}(i)| \leq \epsilon$ for all $i \in [n]$. Then \begin{equation} \label{eqn:regular-W1-bound} \mathbf{W}^{1}[f] \leq \tfrac{2}{\pi} +O(\epsilon). \end{equation} Further, if $\mathbf{W}^{1}[f] \geq \tfrac{2}{\pi} – \epsilon$ then $f$ is $O(\sqrt{\epsilon})$-close to the LTF $\mathrm{sgn}(f^{=1})$.

Functions $f$ with $|\widehat{f}(i)| \leq \epsilon$ for all $i \in [n]$ are called $(\epsilon,1)$-regular; see Chapter 6. So the $\frac{2}{\pi}$ Theorem says (roughly speaking) that within the class of $(\epsilon,1)$-regular functions, the maximal degree-$1$ weight is $\frac{2}{\pi}$, and any function achieving this is an unbiased LTF. Further, from Theorem 14 we know that all unbiased LTFs which are $(\epsilon,1)$-regular achieve this.

Remark 27 Since we have $\mathbf{Stab}_\rho[f] \approx \mathbf{W}^{1}[f] \rho$ and $\frac{2}{\pi} \arcsin \rho \approx \frac{2}{\pi} \rho$ when $\rho$ is small, the $\frac{2}{\pi}$ Theorem gives the Majority Is Stablest Theorem in the limit $\rho \to 0^+$.

Let’s now discuss how we’ll prove our two theorems about degree-$1$ weight. Let $f : \{-1,1\}^n \to \{0,1\}$ and $\alpha = \mathop{\bf E}[f]$; we think of $\alpha$ as small for the Level-1 Inequality and $\alpha = 1/2$ for the $\frac{2}{\pi}$ Theorem. By Plancherel, $\mathbf{W}^{1}[f] = \mathop{\bf E}[f({\boldsymbol{x}}) L({\boldsymbol{x}})]$, where \[ L(x) = f^{=1}(x) = \widehat{f}(1)x_1 + \cdots + \widehat{f}(n) x_n. \] To upper-bound $\mathop{\bf E}[f({\boldsymbol{x}}) L({\boldsymbol{x}})]$, consider that as ${\boldsymbol{x}}$ varies the real number $L({\boldsymbol{x}})$ may be rather large or small, but $f({\boldsymbol{x}})$ is always $0$ or $1$. Given that $f({\boldsymbol{x}})$ is $1$ on only a $\alpha$ fraction of ${\boldsymbol{x}}$’s, the “worst case” for $\mathop{\bf E}[f({\boldsymbol{x}}) L({\boldsymbol{x}})]$ would be if $f(x)$ were $1$ precisely on the $\alpha$ fraction of $x$’s where $L(x)$ is largest. In other words, \begin{equation} \label{eqn:talagrand1} \mathbf{W}^{1}[f] = \mathop{\bf E}[f({\boldsymbol{x}}) L({\boldsymbol{x}})] \leq \mathop{\bf E}[\boldsymbol{1}_{\{L({\boldsymbol{x}}) \geq t\}} \cdot L({\boldsymbol{x}})], \end{equation} where $t$ is chosen so that \begin{equation} \label{eqn:what-is-t} \mathop{\bf Pr}[L({\boldsymbol{x}}) \geq t] \approx \alpha. \end{equation} But now we can analyze \eqref{eqn:talagrand1} quite effectively using tools such as Hoeffding’s bound and the Central Limit Theorem, since $L({\boldsymbol{x}})$ is just a linear combination of independent $\pm 1$ random bits. In particular $L({\boldsymbol{x}})$ has mean $0$ and standard deviation $\sigma = \sqrt{\mathbf{W}^{1}[f]}$ so by the CLT it acts like the Gaussian $\boldsymbol{Z} \sim \mathrm{N}(0,\sigma^2)$, at least if we assume all $|\widehat{f}(i)|$ are small. If we are thinking of $\alpha = 1/2$, then $t = 0$ and we get \[ \sigma^2 = \mathbf{W}^{1}[f] \leq \mathop{\bf E}[\boldsymbol{1}_{\{L({\boldsymbol{x}}) \geq 0\}} \cdot L({\boldsymbol{x}})] \approx \mathop{\bf E}[\boldsymbol{1}_{\{\boldsymbol{Z} \geq 0\}} \cdot \boldsymbol{Z}] = \tfrac{1}{\sqrt{2\pi}} \sigma; \] This implies $\sigma^2 \lessapprox \tfrac{1}{2\pi}$, as claimed in the $\frac{2}{\pi}$ Theorem (after adjusting $f$’s range to $\{-1,1\}$). If we are instead thinking of $\alpha$ as small then \eqref{eqn:what-is-t} suggest taking $t \sim \sigma \sqrt{2\ln(1/\alpha)}$ so that $\mathop{\bf Pr}[\boldsymbol{Z} \geq t] \approx \alpha$. Then a calculation akin to the one in Proposition 24 implies \[ \mathbf{W}^{1}[f] \leq \mathop{\bf E}[\boldsymbol{1}_{\{L({\boldsymbol{x}}) \geq t\}} \cdot L({\boldsymbol{x}})] \approx \alpha \cdot \sigma \sqrt{2\ln(1/\alpha)}, \] from which the Level-1 Inequality follows. In fact, we don’t even need all $|\widehat{f}(i)|$ small for this latter analysis; for large $t$ it’s possible to upper-bound \eqref{eqn:talagrand1} using only Hoeffding’s bound:

Lemma 28 Let $\ell(x) = a_1 x_1 + \cdots + a_n x_n$, where $\sum_{i} a_i^2 = 1$. Then for any $s \geq 1$, \[ \mathop{\bf E}[\boldsymbol{1}_{\{|\ell({\boldsymbol{x}})| > s\}} \cdot |\ell({\boldsymbol{x}})|] \leq (2s+2)\exp(-\tfrac{s^2}{2}). \]

Proof: We have \begin{align*} \mathop{\bf E}[\boldsymbol{1}_{\{|\ell({\boldsymbol{x}})| > s\}} \cdot |\ell({\boldsymbol{x}})|] &= s\mathop{\bf Pr}[|\ell({\boldsymbol{x}})| > s] + \int_{s}^\infty \mathop{\bf Pr}[|\ell({\boldsymbol{x}})| > u]\,du \\ &\leq 2s\exp(-\tfrac{s^2}{2}) + \int_{s}^\infty 2\exp(-\tfrac{u^2}{2})\,du, \end{align*} using Hoeffding’s bound. But for $s \geq 1$, \[ \int_{s}^\infty 2\exp(-\tfrac{u^2}{2})\,du \leq \int_{s}^\infty u \cdot 2\exp(-\tfrac{u^2}{2})\,du = 2\exp(-\tfrac{s^2}{2}). \Box \]

We now give formal proofs of the two theorems, commenting that rather than $L(x)$ it’s more convenient to work with \[ \ell(x) = \tfrac{1}{\sigma} f^{=1}(x) = \tfrac{\widehat{f}(1)}{\sigma}x_1 + \cdots + \tfrac{\widehat{f}(n)}{\sigma}x_n. \]

Proof of the Level-1 Inequality: Following Remark 25 we let $f : \{-1,1\}^n \to [-1,1]$ and $\alpha = \mathop{\bf E}[|f|]$. We may assume $\sigma = \sqrt{\mathbf{W}^{1}[f]} > 0$. Writing $\ell = \frac{1}{\sigma} f^{=1}$ we have $ \langle f, \ell \rangle = \tfrac{1}{\sigma} \langle f, f^{=1} \rangle = \tfrac{1}{\sigma} \mathbf{W}^{1}[f] = \sigma $ and hence \[ \sigma = \langle f, \ell \rangle = \mathop{\bf E}[\boldsymbol{1}_{\{|\ell({\boldsymbol{x}})| \leq s\}} \cdot f({\boldsymbol{x}}) \ell({\boldsymbol{x}})] + \mathop{\bf E}[\boldsymbol{1}_{\{|\ell({\boldsymbol{x}})| > s\}} \cdot f({\boldsymbol{x}}) \ell({\boldsymbol{x}})] \] holds for any $s \geq 1$. The first expectation above is at most $\mathop{\bf E}[s |f({\boldsymbol{x}})|] = \alpha s$, and the second is at most $(2+2s)\exp(-s^2/2) \leq 4s\exp(-s^2/2)$ by Lemma 28. Hence \[ \sigma \leq \alpha s + 4s \exp(-s^2/2). \] The optimal choice of $s$ is $s = (\sqrt{2} + o_\alpha(1)) \sqrt{\ln(1/\alpha)}$, yielding \[ \sigma \leq (\sqrt{2} + o(1)) \alpha\sqrt{\ln(1/\alpha)}. \] Squaring this establishes the claim $\sigma^2 \leq (2+o_\alpha(1)) \alpha^2\ln(1/\alpha)$. $\Box$

Proof of the $\frac{2}{\pi}$ Theorem: We may assume $\sigma = \sqrt{\mathbf{W}^{1}[f]} \geq 1/2$: for the theorem’s first statement this is because otherwise there is nothing to prove; for the theorem’s second statement this is because we may assume $\epsilon$ sufficiently small.

We start by proving \eqref{eqn:regular-W1-bound}. Let $\ell = \frac{1}{\sigma} f^{=1}$, so $\|\ell\|_2 = 1$ and $\widehat{\ell}(i) \leq 2\epsilon$ for all $i \in [n]$. We have \begin{equation} \label{eqn:ltf-test1} \sigma = \langle f, \ell \rangle \leq \mathop{\bf E}[|\ell|] \leq \sqrt{\tfrac{2}{\pi}} + C \epsilon \end{equation} for some constant $C$, where we used Theorem 13. Squaring this proves \eqref{eqn:regular-W1-bound}. We observe that \eqref{eqn:regular-W1-bound} therefore holds even for $f : \{-1,1\}^n \to [-1,1]$.

Now suppose we also have $\mathbf{W}^{1}[f] \geq \tfrac{2}{\pi} – \epsilon$; i.e., \[ \sigma \geq \sqrt{\tfrac{2}{\pi} - \epsilon} \geq \sqrt{\tfrac{2}{\pi}} - 2\epsilon. \] Thus the first inequality in \eqref{eqn:ltf-test1} must be close to tight; specifically, \begin{equation} \label{eqn:ltf-test-contra} (C+2)\epsilon \geq \mathop{\bf E}[|\ell|] – \langle f, \ell\rangle = \mathop{\bf E}[(\mathrm{sgn}(\ell({\boldsymbol{x}})) - f({\boldsymbol{x}})) \cdot \ell({\boldsymbol{x}})]. \end{equation} By the Berry–Esseen Theorem (and Remark 12 and an exercise), \[ \mathop{\bf Pr}[|\ell| \leq K\sqrt{\epsilon}] \leq \mathop{\bf Pr}[|\mathrm{N}(0,1)| \leq K\sqrt{\epsilon}] + .56 \cdot 2\epsilon \leq \tfrac{1}{\sqrt{2\pi}} \cdot 2K\sqrt{\epsilon} + 1.12 \epsilon \leq 2K\sqrt{\epsilon} \] for any constant $K \geq 1$. We therefore have the implication \begin{align*} \mathop{\bf Pr}[f \neq \mathrm{sgn}(\ell)] \geq 3K\sqrt{\epsilon} &\Rightarrow \mathop{\bf Pr}[f({\boldsymbol{x}}) \neq \mathrm{sgn}(\ell({\boldsymbol{x}}))\ \wedge\ |\ell({\boldsymbol{x}})| > K\sqrt{\epsilon}] \geq K \sqrt{\epsilon} \\ &\Rightarrow \mathop{\bf E}[(\mathrm{sgn}(\ell({\boldsymbol{x}})) - f({\boldsymbol{x}})) \cdot \ell({\boldsymbol{x}})] \geq K\sqrt{\epsilon} \cdot 2(K\sqrt{\epsilon}) = 2K^2 \epsilon. \end{align*} This contradicts \eqref{eqn:ltf-test-contra} for $K = \sqrt{C+2}$, say. Thus $\mathop{\bf Pr}[f \neq \mathrm{sgn}(\ell)] \leq 3\sqrt{C+2}\sqrt{\epsilon}$, completing the proof. $\Box$

For an interpolation between these two theorems, see the exercises.

We conclude this section with an application of the Level-1 Inequality. First, a quick corollary which we leave for the exercises:

Corollary 29 Let $f : \{-1,1\}^n \to \{-1,1\}$ have $|\mathop{\bf E}[f]| \geq 1 – \delta \geq 0$. Then $\mathbf{W}^{1}[f] \leq 4\delta^2 \log(2/\delta)$.

In Chapter 2.5 we stated the FKN Theorem, which says that if $f : \{-1,1\}^n \to \{-1,1\}$ has $\mathbf{W}^{1}[f] \geq 1 – \delta$ then it must be $O(\delta)$-close to a dictator or negated-dictator. The following theorem shows that once the FKN Theorem is proved, it can be strengthened to give an essentially optimal (see the exercises) closeness bound:

Theorem 30 Suppose the FKN Theorem holds with closeness bound $C\delta$, where $C \geq 1$ is a universal constant. Then in fact it holds with bound $\delta/4 + \eta$, where $\eta = 16C^2 \delta^2 \max(\log(1/C\delta),1)$.

Proof: Suppose $f : \{-1,1\}^n \to \{-1,1\}$ has $\mathbf{W}^{1}[f] \geq 1 – \delta \geq 0$. By assumption $f$ is $C\delta$-close to $\pm \chi_i$ for some $i \in [n]$, say $i = n$. Thus we have \[ |\widehat{f}(n)| \geq 1 - 2C\delta \] and our task is to show that in fact $|\widehat{f}(n)| \geq 1 – \delta/2 – 2\eta$. We may assume $\delta \leq \frac{1}{10C}$ as otherwise $1 – \delta/2 – 2\eta < 0$ (exercise) and there is nothing to prove. By employing the trick from Exercise 2.42 we may also assume $\mathop{\bf E}[f] = 0$.

Consider the restriction of $f$ given by fixing coordinate $n$ to $b \in \{-1,1\}$; i.e., $f_{[n-1] \mid b}$. For both choices of $b$ we have $|\mathop{\bf E}[f_{[n-1] \mid b}]| \geq 1 – 2C\delta$ and so Corollary 29 implies $\mathbf{W}^{1}[f_{[n-1] \mid b}] \leq 16C^2\delta^2 \log(1/C\delta)$. Thus \[ 16C^2\delta^2 \log(1/C\delta) \geq \mathop{\bf E}_{\boldsymbol{b}}[\mathbf{W}^{1}[f_{[n-1] \mid \boldsymbol{b}}]] = \sum_{j < n} (\widehat{f}(\{j\})^2 + \widehat{f}(\{j, n\})^2) \geq \sum_{j < n} \widehat{f}(j)^2, \] by Corollary 3.21. It follows that \[ \widehat{f}(n)^2 = \mathbf{W}^{1}[f] – \sum_{j<n}\widehat{f}(j)^2 \geq 1- \delta – 16C^2\delta^2 \log(1/C\delta), \] and the proof is completed by the fact that \[ 1- \delta - 16C^2\delta^2 \log(1/C\delta) \geq (1-\delta/2 - 2\eta)^2 \] when $\delta \leq \frac{1}{10C}$ (exercise). $\Box$

We begin with a reminder about the Central Limit Theorem. Suppose $\boldsymbol{X}_1, \dots, \boldsymbol{X}_n$ are independent random variables and $\boldsymbol{S} = \boldsymbol{X}_1 + \cdots + \boldsymbol{X}_n$. Roughly speaking, the CLT says that so long as no $\boldsymbol{X}_i$ is too dominant in terms of variance, the distribution of $\boldsymbol{S}$ is close to that of a Gaussian random variable with the same mean and variance. We give a precise statement below in the form of the Berry–Esseen Theorem. The CLT also extends to the multidimensional case (sums of independent random vectors); we give a precise statement in the exercises. In Chapter 13 we will show one way to prove such Central Limit Theorems.

Let’s see how we can use the CLT to obtain the estimate $\mathbf{I}[\mathrm{Maj}_n] \sim \sqrt{2/\pi}\sqrt{n}$. Recall the proof of Theorem 2.32, which shows that $\mathrm{Maj}_n$ maximizes $\sum_{i=1}^n \widehat{f}(i)$ among all $f : \{-1,1\}^n \to \{-1,1\}$. In it we saw that \begin{equation} \label{eqn:sum-deg-1-maj} \mathbf{I}[\mathrm{Maj}_n] = \sum_{i=1}^n \widehat{\mathrm{Maj}_n}(i) = \mathop{\bf E}_{{\boldsymbol{x}}}[\mathrm{Maj}_n({\boldsymbol{x}})(\mathop{{\textstyle \sum}}_i {\boldsymbol{x}}_i)] = \mathop{\bf E}_{{\boldsymbol{x}}}[|\mathop{{\textstyle \sum}}_i {\boldsymbol{x}}_i|]. \end{equation} When using the Central Limit Theorem, it’s convenient to define majority (equivalently) as \[ \mathrm{Maj}_n(x) = \mathrm{sgn}\Bigl(\mathop{{\textstyle \sum}}_{i=1}^n \tfrac{1}{\sqrt{n}} x_i\Bigr). \] This motivates writing \eqref{eqn:sum-deg-1-maj} as \begin{equation} \label{eqn:sum-deg-1-maj2} \mathbf{I}[\mathrm{Maj}_n] = \sqrt{n} \cdot \mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[|\mathop{{\textstyle \sum}}_i \tfrac{1}{\sqrt{n}}{\boldsymbol{x}}_i|]. \end{equation} If we introduce $\boldsymbol{S} = \sum_{i=1}^n \tfrac{1}{\sqrt{n}} {\boldsymbol{x}}_i$, then $\boldsymbol{S}$ has mean $0$ and variance $\sum_i (1/\sqrt{n})^2 = 1$. Thus the CLT tells us that the distribution of $\boldsymbol{S}$ is close (for large $n$) to that of a standard Gaussian, $\boldsymbol{Z} \sim \mathrm{N}(0,1)$. So as $n \to \infty$ we have \begin{equation} \label{eqn:abs-first-moment-gaussian} \mathop{\bf E}_{{\boldsymbol{x}}}[|\boldsymbol{S}|] \sim \mathop{\bf E}_{\boldsymbol{Z} \sim \mathrm{N}(0,1)}[|\boldsymbol{Z}|] = 2\int_{0}^\infty z \cdot \tfrac{1}{\sqrt{2\pi}} e^{-z^2/2}\,dz = -\sqrt{2/\pi} e^{-z^2/2}\Bigm|_{0}^\infty = \sqrt{2/\pi}, \end{equation} which when combined with \eqref{eqn:sum-deg-1-maj2} gives us the estimate $\mathbf{I}[\mathrm{Maj}_n] \sim \sqrt{2/\pi} \sqrt{n}$. To make this kind of estimate more precise we state the Berry–Esseen Theorem, which is a strong version of the CLT giving explicit error bounds rather than just limiting statements.

Berry–Esseen (Central Limit) Theorem Let $\boldsymbol{X}_1, \dots, \boldsymbol{X}_n$ be independent random variables with $\mathop{\bf E}[\boldsymbol{X}_i] = 0$ and $\mathop{\bf Var}[\boldsymbol{X}_i] = \sigma_i^2$, and assume $\sum_{i=1}^n \sigma_i^2 = 1$. Let $\boldsymbol{S} = \sum_{i=1}^n \boldsymbol{X}_i$ and let $\boldsymbol{Z} \sim \mathrm{N}(0,1)$ be a standard Gaussian. Then for all $u \in {\mathbb R}$, \[ |\mathop{\bf Pr}[\boldsymbol{S} \leq u] – \mathop{\bf Pr}[\boldsymbol{Z} \leq u]| \leq B \beta, \] where \[ \beta = \sum_{i=1}^n \|\boldsymbol{X}_i\|_3^3 \] and $B$ is a universal constant. (For definiteness, $B = .56$ is acceptable.)

Remark 12 If all of the $\boldsymbol{X}_i$’s satisfy $|\boldsymbol{X}_i| \leq \epsilon$ with probability $1$ then we can use the bound \[ \beta = \sum_{i=1}^n \mathop{\bf E}[|\boldsymbol{X}_i|^3] \leq \epsilon \cdot \sum_{i=1}^n \mathop{\bf E}[|\boldsymbol{X}_i|^2] = \epsilon \cdot \sum_{i=1}^n \sigma_i^2 = \epsilon. \]

The exercises contain additional observations about this theorem.

Our most frequent use of the Berry–Esseen Theorem will be in analyzing random sums \[ \boldsymbol{S} = \sum_{i=1}^n a_i {\boldsymbol{x}}_i, \] where ${\boldsymbol{x}} \sim \{-1,1\}^n$ and the constants $a_i \in {\mathbb R}$ are normalized so that $\sum_i a_i^2 = 1$. For majority, all of the $a_i$’s were equal to $\tfrac{1}{\sqrt{n}}$. But from Remark 12 we see that $\boldsymbol{S}$ is close in distribution to a standard Gaussian so long as each $|a_i|$ is small. For example, in the exercises you are asked to show the following:

Theorem 13 Let $a_1, \dots, a_n \in {\mathbb R}$ satisfy $\sum_i a_i^2 = 1$ and $|a_i| \leq \epsilon$ for all $i$. Then \[ \left|\mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[|\mathop{{\textstyle \sum}}_i a_i {\boldsymbol{x}}_i|] – \sqrt{2/\pi}\right| \leq C \epsilon, \] where $C$ is a universal constant.

Theorem 13 justifies \eqref{eqn:abs-first-moment-gaussian} with an error bound of $O(1/\sqrt{n})$, yielding the more precise estimate $\mathbf{I}[\mathrm{Maj}_n] = \sqrt{2/\pi}\sqrt{n} \pm O(1)$ (cf. Exercise 2.18 which gives an even better error bound).

Now let’s turn to the noise stability of majority. Theorem 2.44 stated the formula \begin{equation} \label{eqn:re-maj-stab} \lim_{n \to \infty} \mathbf{Stab}_\rho[\mathrm{Maj}_n] = \tfrac{2}{\pi} \arcsin \rho. \end{equation} Let’s now spend some time justifying this using the multidimensional CLT. (For complete details, see the exercises.) By definition, \begin{equation} \label{eqn:stab-maj-justify1} \mathbf{Stab}_\rho[\mathrm{Maj}_n] = \mathop{\bf E}_{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ {\text{ $\rho$-correlated}}}}[\mathrm{Maj}_n({\boldsymbol{x}}) \cdot \mathrm{Maj}_n(\boldsymbol{y})] = \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ {\text{ $\rho$-correlated}}}}}[\mathrm{sgn}(\mathop{{\textstyle \sum}}_i \tfrac{1}{\sqrt{n}} {\boldsymbol{x}}_i) \cdot \mathrm{sgn}(\mathop{{\textstyle \sum}}_i \tfrac{1}{\sqrt{n}} \boldsymbol{y}_i)]. \end{equation} For each $i \in [n]$ let’s stack $\tfrac{1}{\sqrt{n}} {\boldsymbol{x}}_i$ and $\tfrac{1}{\sqrt{n}} \boldsymbol{y}_i$ into a $2$-dimensional vector and then write \begin{equation} \label{eqn:Svec-cov} \vec{\boldsymbol{S}} = \sum_{i=1}^n \begin{bmatrix} \tfrac{1}{\sqrt{n}}{\boldsymbol{x}}_i \\ \tfrac{1}{\sqrt{n}}\boldsymbol{y}_i \end{bmatrix} \in {\mathbb R}^2. \end{equation} We are summing $n$ independent random vectors, so the multidimensional Central Limit Theorem tells us that the distribution of $\vec{\boldsymbol{S}}$ is close to that of a $2$-dimensional Gaussian $\vec{\boldsymbol{Z}}$ with the same mean and covariance matrix, namely \[ \vec{\boldsymbol{Z}} \sim \mathrm{N}\left(\begin{bmatrix} 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 & \rho \\ \rho & 1 \end{bmatrix}\right). \] Continuing from \eqref{eqn:stab-maj-justify1}, \begin{align*} \mathbf{Stab}_\rho[\mathrm{Maj}_n] &= \mathop{\bf E}[\mathrm{sgn}(\vec{\boldsymbol{S}}_1)\cdot \mathrm{sgn}(\vec{\boldsymbol{S}}_2)] \\ &= \mathop{\bf Pr}[\mathrm{sgn}(\vec{\boldsymbol{S}}_1) = \mathrm{sgn}(\vec{\boldsymbol{S}}_2)] – \mathop{\bf Pr}[\mathrm{sgn}(\vec{\boldsymbol{S}}_1) \neq \mathrm{sgn}(\vec{\boldsymbol{S}}_2)] \\ &= 2\mathop{\bf Pr}[\mathrm{sgn}(\vec{\boldsymbol{S}}_1) = \mathrm{sgn}(\vec{\boldsymbol{S}}_2)] – 1 = 4\mathop{\bf Pr}[\vec{\boldsymbol{S}} \in Q_{++}] – 1, \end{align*} where $Q_{++}$ denotes the upper-right quadrant of ${\mathbb R}^2$ and the last step uses the symmetry $\mathop{\bf Pr}[\vec{\boldsymbol{S}} \in Q_{++}] = \mathop{\bf Pr}[\vec{\boldsymbol{S}} \in Q_{--}]$. The $2$-dimensional Central Limit Theorem lets us deduce \[ \lim_{n \to \infty} \mathop{\bf Pr}[\vec{\boldsymbol{S}} \in Q_{++}] = \mathop{\bf Pr}[\vec{\boldsymbol{Z}} \in Q_{++}]. \] So to justify the noise stability formula \eqref{eqn:re-maj-stab} for majority, it remains to verify \[ 4\mathop{\bf Pr}[\vec{\boldsymbol{Z}} \in Q_{++}] – 1 = \tfrac{2}{\pi} \arcsin \rho \quad\Leftrightarrow\quad \mathop{\bf Pr}[\vec{\boldsymbol{Z}} \in Q_{++}] = \tfrac14 + \tfrac{1}{2\pi} \arcsin \rho. \] And this is turn is an old identity known as Sheppard’s Formula (which you are asked to prove in the exercises).

Sheppard’s Formula Let $\boldsymbol{z}_1$, $\boldsymbol{z}_2$ be standard Gaussian random variables with correlation $\mathop{\bf E}[\boldsymbol{z}_1 \boldsymbol{z}_2] = \rho \in [-1,1]$. Then \[ \mathop{\bf Pr}[\boldsymbol{z}_1 > 0, \boldsymbol{z}_2 > 0] = \tfrac14 + \tfrac{1}{2\pi} \arcsin \rho. \]

This completes the justification of the formula $\mathbf{Stab}_\rho[\mathrm{Maj}_n] \to \tfrac{2}{\pi} \arcsin \rho$. You may have noticed that once we applied the $2$-dimensional Central Limit Theorem to \eqref{eqn:stab-maj-justify1}, the remainder of the derivation had nothing to do with majority. In fact, the same analysis works for any linear threshold function $\mathrm{sgn}(a_1 x_1 + \cdots + a_n x_n)$, the only difference being the “error term” arising from the CLT. As in Theorem 13, this error is small so long as no coefficient $a_i$ is too dominant:

Theorem 14 Let $f : \{-1,1\}^n \to \{-1,1\}$ be an unbiased LTF, $f(x) = \mathrm{sgn}(a_1 x_1 + \cdots + a_n x_n)$ with $\sum_i a_i^2 = 1$ and $|a_i| \leq \epsilon$ for all $i$. Then for any $\rho \in (-1,1)$, \[ \Bigl|\mathbf{Stab}_\rho[f] – \tfrac{2}{\pi} \arcsin \rho\Bigr| \leq O\Bigl(\tfrac{\epsilon}{\sqrt{1-\rho^2}}\Bigr). \]

You are asked to prove Theorem 14 in the exercises. In the particular case of $\mathrm{Maj}_n$ where $a_i = \tfrac{1}{\sqrt{n}}$ for all $i$ we can make a slightly stronger claim (again, see the exercises):

Theorem 15 For any $\rho \in [0,1)$, $\mathbf{Stab}_\rho[\mathrm{Maj}_n]$ is a decreasing function of $n$, with \[ \tfrac{2}{\pi} \arcsin \rho \leq \mathbf{Stab}_\rho[\mathrm{Maj}_n] \leq \tfrac{2}{\pi} \arcsin \rho + O\Bigl(\tfrac{1}{\sqrt{1-\rho^2}\sqrt{n}}\Bigr). \]

We end this section by mentioning another way in which the majority function is extremal — among all unbiased functions with small influences, it has (essentially) the largest noise stability:

Majority Is Stablest Theorem (simplified) Fix $\rho \in (0,1)$. Then for any $f : \{-1,1\}^n \to \{-1,1\}$ with $\mathop{\bf E}[f] = 0$ and $\mathbf{MaxInf}[f] \leq \tau$, \[ \mathbf{Stab}_\rho[f] \leq \tfrac{2}{\pi} \arcsin \rho + o_\tau(1). \]

For sufficiently small $\rho$, we’ll prove this in Section 4 of this chapter. The proof of the full Majority Is Stablest Theorem will have to wait until Chapter 13.