Chapter 8 exercises

1. Explain how to generalize the definitions and results in Sections 1, 2 to general finite product spaces $L^2(\Omega_1 \times \cdots \times \Omega_n, \pi_1 \times \cdots \times \pi_n)$.
2. Verify that Definition 1 indeed defines a real inner product space. (Where is the fact that $\pi$ has full support used?)
3. Verify the formula for $\widehat{f}(\alpha)$ in Definition 14.
4. Verify that $\phi_0, \phi_1, \phi_2$ from Example 10 indeed constitute a Fourier basis for $\Omega = \{a,b,c\}$ with the uniform distribution.
5. Verify the Fourier expansion in Example 15.
6. Complete the proof of Proposition 16.
7. Prove that the expectation over $I$ operator, $\mathrm{E}_I$, is a linear operator on $L^2(\Omega^n, \pi^{\otimes n})$ (i.e., $\mathrm{E}_I (f+g) = \mathrm{E}_I f + \mathrm{E}_I g$), a projection (i.e., $\mathrm{E}_I \circ \mathrm{E}_I = \mathrm{E}_I$), and self-adjoint (i.e., $\langle f, \mathrm{E}_I g \rangle = \langle \mathrm{E}_I f, g \rangle$). Deduce that $\mathrm{T}_\rho$ is also self-adjoint.
8. Show for any $f,g \in L^2(\Omega^n, \pi^{\otimes n})$ and $j \in [n]$ that $f = \mathrm{E}_j f + \mathrm{L}_j f$ and that $\langle f, g \rangle = \langle \mathrm{E}_j f, \mathrm{E}_j g \rangle + \langle \mathrm{L}_j f, \mathrm{L}_j g \rangle$.
9. Prove Proposition 24.

    9½. Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ have range $\{-1,1\}$. Proposition 24 tells us that $\|\mathrm{L}_i f\|_1 = \|\mathrm{L}_i f\|_2^2 = \mathbf{Inf}_i[f]$. Show that $\|\mathrm{L}_i f\|_p^p \leq 2^p \mathbf{Inf}_i[f]$ for any $p \geq 1$. Further, in case $1 \leq p \leq 1$, show that in fact $\|\mathrm{L}_i f\|_p^p \leq \mathbf{Inf}_i[f]$. (Hint: use the general form of Hölder’s inequality to bound $\|\mathrm{L}_i f\|_p$ in terms of $\|\mathrm{L}_i f\|_1$ and $\|\mathrm{L}_i f\|_2$.)

10. Assume $|\Omega| = m$ and let $\pi$ denote the uniform distribution on $\Omega$.
    1. For $x \in \Omega^n$ and $\boldsymbol{y} \sim N_\rho(x)$, write a formula for $\mathop{\bf Pr}[\boldsymbol{y}_i = \omega]$ in terms of $\rho$ (there are two cases depending on whether or not $x_i = \omega$).
    2. Verify that your formula defines a valid probability distribution on $\Omega$ even when $-\frac{1}{m-1} \leq \rho < 0$. We may therefore extend the definition of $N_\rho$ to this case. (Cf. the second half of Definition 2.39.)
    3. Verify that for ${\boldsymbol{x}} \sim \pi^{\otimes n}$ and $\boldsymbol{y} \sim N_\rho({\boldsymbol{x}})$, the distribution of $({\boldsymbol{x}},\boldsymbol{y})$ is symmetric in ${\boldsymbol{x}}$ and $\boldsymbol{y}$.
    4. Show that when $\boldsymbol{y} \sim N_{-\frac{1}{m-1}}(x)$, each $\boldsymbol{y}_i$ is uniformly distributed on $\Omega \setminus \{x_i\}$.
    5. Verify that the formula for $\mathrm{T}_\rho$ from Proposition 28 continues to hold for $-\frac{1}{m-1} \leq \rho < 0$. (Hint: use the fact that it holds for $\rho \in [0,1]$ and that the formula in part 7 is a polynomial in $\rho$.)
11. Show that Definition 30 extends by continuity to \[ \mathbf{Inf}_i^{(0)}[f] = \sum_{\substack{\#\alpha = 1 \\ \alpha_i \neq 0}} \widehat{f}(\alpha)^2. \] Extend also Proposition 31 to the case of $\delta = 1$.
12. Prove explicitly that condition (v) holds in Theorem 35.
13. Prove that condition 35 must hold in Theorem 35 directly from the uniqueness statement (i.e., without appealing to the explicit construction).
14. Let $f \in L^2(\Omega^n, \pi^{\otimes n})$. Prove directly from the defining Theorem 35 that $(f^{=S})^{\subseteq T}$ is equal to $f^{=S}$ if $S \subseteq T$ and is equal to $0$ otherwise.
15. Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ and let ${\boldsymbol{x}} \sim \pi^{\otimes n}$. In this exercise you should think about how the (conditional) expectation of $f$ changes as the random variables ${\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_n$ are revealed one at a time.
    1. Recalling that $f^{\subseteq [t]}({\boldsymbol{x}})$ depends only on ${\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_t$, show that the sequence of random variables $(f^{\subseteq [t]}({\boldsymbol{x}}))_{t = 0 \dots n}$ is a martingale (where $f^{\subseteq [0]}$ denotes $f^\emptyset$); i.e., \[ \mathop{\bf E}[f^{\subseteq [t]}({\boldsymbol{x}}) \mid f^{\subseteq [0]}({\boldsymbol{x}}), \dots, f^{\subseteq [t-1]}({\boldsymbol{x}})] = f^{\subseteq [t-1]}({\boldsymbol{x}}) \quad \forall t \in [n]. \] (This is the Doob martingale for $f$.)
    2. For each $t \in [n]$ define \[ \mathrm{d}_{t}{f} = f^{\subseteq [t]} – f^{\subseteq [t-1]} = \sum_{\substack{S \subseteq [n] \\ \max(S) = t}} f^{=S}. \] Show that $\mathop{\bf E}[\mathrm{d}_{t}{f}({\boldsymbol{x}}) \mid f^{\subseteq [0]}({\boldsymbol{x}}), \dots, f^{\subseteq [t-1]}({\boldsymbol{x}})] = 0$. (Here $(\mathrm{d}_{t}{f})_{t = 1 \dots n}$ is the martingale difference sequence for $f$.)
16. For $f, g \in L^2(\Omega^n, \pi^{\otimes n})$, prove the following directly from Theorem 35: \begin{gather*} \langle f, g \rangle = \sum_{S \subseteq [n]} \langle f^{=S}, g^{=S} \rangle\\ \mathbf{Inf}_i[f] = \sum_{S \ni i} \|f^{=S}\|_2^2 \\ \mathbf{I}[f] = \sum_{k=0}^n k \cdot \mathbf{W}^{k}[f] \\ \mathrm{T}_\rho (f^{=S}) = (\mathrm{T}_\rho f)^{=S} = \rho^k f^{=S} \\ \mathbf{Stab}_\rho[f] = \sum_{k=0}^n \rho^k \cdot \mathbf{W}^{k}[f] \end{gather*}
17. Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ and let $S \subseteq [n]$. Show that $\|f^{=S}\|_\infty \leq 2^{|S|} \|f\|_\infty$.
18. Explicitly verify that Proposition 36 holds for the function in Examples 15, 37.
19. Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ be a symmetric function. Show that if $1 \leq |S| \leq |T| \leq n$ then $\frac{1}{|S|} \mathop{\bf Var}[f^{\subseteq S}] \leq \frac{1}{|T|} \mathop{\bf Var}[f^{\subseteq T}]$.
20. Prove the sharp threshold statement about the majority function made in Examples 48. (Hint: Chernoff bound.) In the social choice literature, this fact is known as the Condorcet Jury Theorem.
21. Let $p_1, \dots, p_n \in (0,1)$ and let $\pi = \pi_{p_1} \otimes \cdots \pi_{p_n}$ be the associated product distribution on $\{-1,1\}^n$. Write $\mu_i = 1 – 2p_i$ and $\sigma_i = 2\sqrt{p_i}\sqrt{1-p_i}$. Generalize Proposition 45 to the setting of $L^2(\{-1,1\}^n, \pi)$.
22. Let $f : \{-1,1\}^n \to {\mathbb R}$ and consider the general product distribution setting of the previous exercise.
    1. For $S = \{i_1, \dots, i_k\} \subseteq [n]$, write $\mathrm{D}_{\phi_S}$ for $\mathrm{D}_{\phi_{i_1}} \circ \cdots \circ \mathrm{D}_{\phi_{i_k}}$ and similarly $\mathrm{D}_{x_S}$. Show that $\mathrm{D}_{\phi_S} = \prod_{i \in S} \sigma_i \cdot \mathrm{D}_{x_S}$.
    2. Writing $f^{(\mu)}$ for the function $f$ viewed as an element of $L^2(\{-1,1\}^n, \pi)$, show that \[ \widehat{f^{(p)}}(S) = \prod_{i \in S} \sigma_i \cdot \mathrm{D}_{x_S} f(\mu_1, \dots, \mu_n). \]
    3. Show that $\hat{\lVert} f^{(p)} \hat{\rVert}_\infty \leq \prod_{i \in S} \sigma_i \cdot \|f\|_\infty$.
23. Fix any $\alpha \in (0,1)$. Let $f : \{\mathsf{True}, \mathsf{False}\}^n \to \{\mathsf{True}, \mathsf{False}\}$ be a nonconstant monotone function. Show that there exists $p \in (0,1)$ such that $\mathop{\bf Pr}_{\pi_p}[f({\boldsymbol{x}}) = \mathsf{True}] = \alpha$. (Hint: Intermediate Value Theorem.)