- 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)$.
- Verify that Definition 1 indeed defines a real inner product space. (Where is the fact that $\pi$ has full support used?)
- Verify the formula for $\widehat{f}(\alpha)$ in Definition 14.
- 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.
- Verify the Fourier expansion in Example 15.
- Complete the proof of Proposition 16.
- 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.
- 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$.
- 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 2$, 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$.)
- Assume $|\Omega| = m$ and let $\pi$ denote the uniform distribution on $\Omega$.
- 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$).
- 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.)
- 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}$.
- Show that when $\boldsymbol{y} \sim N_{-\frac{1}{m-1}}(x)$, each $\boldsymbol{y}_i$ is uniformly distributed on $\Omega \setminus \{x_i\}$.
- 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$.)
- 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$.
- Prove explicitly that condition (v) holds in Theorem 35.
- Prove that condition 35 must hold in Theorem 35 directly from the uniqueness statement (i.e., without appealing to the explicit construction).
- 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.
- 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.
- 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$.)
- 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$.)
- 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*}
- 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$.
- Explicitly verify that Proposition 36 holds for the function in Examples 15, 37.
- 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}]$.
- 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.
- 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)$.
- Let $f : \{-1,1\}^n \to {\mathbb R}$ and consider the general product distribution setting of the previous exercise.
- 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}$.
- 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). \]
- Show that $\hat{\lVert} f^{(p)} \hat{\rVert}_\infty \leq \prod_{i \in S} \sigma_i \cdot \|f\|_\infty$.
- 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.)
In 9½ there is a typo $1\leq p\leq 1$
I think that for $p>2$ we can have $2^{p-2}$ in place of $2^p$
You’re probably right about $2^{p-2}$ — didn’t have a chance to think about it yet…