# Paper 2, Section II, F

(a) Let $Y$ and $Z$ be independent discrete random variables taking values in sets $S_{1}$ and $S_{2}$ respectively, and let $F: S_{1} \times S_{2} \rightarrow \mathbb{R}$ be a function.

Let $E(z)=\mathbb{E} F(Y, z)$. Show that

$\mathbb{E} E(Z)=\mathbb{E} F(Y, Z) .$

Let $V(z)=\mathbb{E}\left(F(Y, z)^{2}\right)-(\mathbb{E} F(Y, z))^{2}$. Show that

$\operatorname{Var} F(Y, Z)=\mathbb{E} V(Z)+\operatorname{Var} E(Z)$

(b) Let $X_{1}, \ldots, X_{n}$ be independent Bernoulli $(p)$ random variables. For any function $F:\{0,1\} \rightarrow \mathbb{R}$, show that

$\operatorname{Var} F\left(X_{1}\right)=p(1-p)(F(1)-F(0))^{2}$

Let $\{0,1\}^{n}$ denote the set of all $0-1$ sequences of length $n$. By induction, or otherwise, show that for any function $F:\{0,1\}^{n} \rightarrow \mathbb{R}$,

$\operatorname{Var} F(X) \leqslant p(1-p) \sum_{i=1}^{n} \mathbb{E}\left(\left(F(X)-F\left(X^{i}\right)\right)^{2}\right)$

where $X=\left(X_{1}, \ldots, X_{n}\right)$ and $X^{i}=\left(X_{1}, \ldots, X_{i-1}, 1-X_{i}, X_{i+1}, \ldots, X_{n}\right)$.