Invariance principles - Analysis of Boolean Functions

Example. Let $X_{i}$ uniform on ${- 1, 1}$ , $Y_{i} \sim N (0, 1)$ . Then $\frac{1}{\sqrt{n}} (X_{1} + \dots + X_{n}) \approx \frac{1}{\sqrt{n}} (Y_{1} + \dots + Y_{n}) \sim N (0, 1)$ . Here, $\approx$ is meant to mean “has approximately the same distribution as”.

Here, we saw that replacing $X_{i}$ by another variable $Y_{i}$ with roughly similar properties (e.g. same mean and variance) didn’t affect the distribution of the sum by much.

How can we define “approximately same distribution”? You may have seen before that we can define it as $| ℙ [X \leq t] - ℙ [Y \leq t] | \leq 𝜀$ holding for all $t$ . This can be rephrased in terms of $𝔼 𝟙_{X \leq t}$ . We will instead use a notion of similar distribution where we use continuous functions (in fact we will even require stronger conditions than this).

Theorem 8.1 (Generalisation / modification of the Berry–Esseen Theorem). Let $X_{1}, \dots, X_{n}$ and $Y_{1}, \dots, Y_{n}$ be sequences of independent random variables. Suppose that $𝔼 X_{i} = 𝔼 Y_{i}$ and $𝔼 X_{i}^{2} = 𝔼 Y_{i}^{2}$ for each $i$ . Let $ψ : ℝ \to ℝ$ be such that $∥ ψ^{‴} ∥_{\infty} \leq C$ (bounded third derivative). Then

| 𝔼 ψ (X_{1} + \dots + X_{n} - 𝔼 ψ (Y_{1} + \dots + Y_{n}) | \leq \frac{1}{6} C (\sum_{i = 1}^{n} (∥ X_{i} ∥_{3}^{3} + ∥ Y_{i} ∥_{3}^{3})) .

Proof. By the triangle inequality, the quantity we wish to bound is at most

\sum_{i = 1}^{n} | 𝔼 ψ (Y_{1} + \dots + Y_{i - 1} + X_{i} + \dots + X_{n}) - 𝔼 ψ (Y_{1} + \dots + Y_{i - 1} + Y_{i} + X_{i + 1} + \dots + X_{n}) | Y_{|} .

Write $U_{i}$ for $Y_{1} + \dots + Y_{i - 1} + X_{i + 1} + \dots + X_{n}$ . So the above is

\sum_{i = 1}^{n} | 𝔼 ψ (U_{i} + X_{i}) - 𝔼 ψ (U_{i} + Y_{i}) | .

By Taylor’s Theorem,

\begin{array}{l} ψ (U_{i} + X_{i}) & = ψ (U_{i}) + X_{i} ψ^{'} (U_{i}) + \frac{X_{i}^{2}}{2} ψ^{″} (U_{i}) + \frac{X_{i}^{3}}{6} ψ^{‴} (V_{i}) \\ ψ (U_{i} + Y_{i}) & = ψ (U_{i}) + Y_{i} ψ^{'} (U_{i}) + \frac{Y_{i}^{2}}{2} ψ^{″} (U_{i}) + \frac{Y_{i}^{3}}{6} ψ^{‴} (W_{i}) \end{array}

where $V_{i}$ is between $U_{i}$ and $U_{i} + X_{i}$ , $W_{i}$ is between $U_{i}$ and $U_{i} + Y_{i}$ .

Taking expectations and subtracting, and using the fact that $𝔼 X_{i} = 𝔼 Y_{i}$ and $𝔼 X_{i}^{2} = 𝔼 Y_{i}^{2}$ and also that $X_{i}$ and $Y_{i}$ are independent of $U_{i}$ , we get

𝔼 (\frac{X_{i}^{3}}{6} ψ^{‴} (V_{i}) - \frac{Y_{i}^{3}}{6} ψ^{‴} (W_{i})),

which has size at most $\frac{C}{6} (𝔼 | X_{i} |^{3} + 𝔼 | Y_{i} |^{3}) = \frac{C}{6} (∥ X_{i} ∥^{3} + ∥ Y_{i} ∥_{3}^{3})$ .

Summing gives the result. □

Corollary 8.2. Let $X_{1}, \dots, X_{n}$ be independent with $𝔼 X_{i} = 0$ and $𝔼 X_{i}^{2} = σ_{i}^{2}$ with $\sum σ_{i}^{2} = 1$ . Let $ψ$ be such that $∥ ψ^{‴} ∥_{\infty} \leq C$ . Then

| 𝔼 ψ (\sum_{i = 1}^{n} X_{i}) - 𝔼 ψ (Y) | \leq \frac{C}{6} (\sum_{i = 1}^{n} ∥ X_{i} ∥_{3}^{3} + 2 \sum_{i = 1}^{n} σ_{i}^{3} \sqrt{\frac{2}{π}})

where $Y \sim N (0, 1)$ .

Proof. Let $Y_{1}, \dots, Y_{n}$ be normal with mean zero and $𝔼 Y_{i}^{2} = σ_{i}^{2}$ . Then $\sum_{i = 1}^{n} Y_{i} \sim N (0, 1)$ . By the previous theorem, we get a bound of

\frac{C}{6} (\sum_{i = 1}^{n} ∥ X_{i} ∥_{3}^{3} + \sum_{i = 1}^{n} σ_{i}^{3} 2 \sqrt{\frac{2}{π}}) . □

8 Invariance principles