# Paper 2, Section II, 12F

State and prove Chebyshev's inequality.

Let $\left(X_{i}\right)_{i \geqslant 1}$ be a sequence of independent, identically distributed random variables such that

$\mathbb{P}\left(X_{i}=0\right)=p \text { and } \mathbb{P}\left(X_{i}=1\right)=1-p$

for some $p \in[0,1]$, and let $f:[0,1] \rightarrow \mathbb{R}$ be a continuous function.

(i) Prove that

$B_{n}(p):=\mathbb{E}\left(f\left(\frac{X_{1}+\cdots+X_{n}}{n}\right)\right)$

is a polynomial function of $p$, for any natural number $n$.

(ii) Let $\delta>0$. Prove that

$\sum_{k \in K_{\delta}}\left(\begin{array}{l} n \\ k \end{array}\right) p^{k}(1-p)^{n-k} \leqslant \frac{1}{4 n \delta^{2}}$

where $K_{\delta}$ is the set of natural numbers $0 \leqslant k \leqslant n$ such that $|k / n-p|>\delta$.

(iii) Show that

$\sup _{p \in[0,1]}\left|f(p)-B_{n}(p)\right| \rightarrow 0$

as $n \rightarrow \infty$. [You may use without proof that, for any $\epsilon>0$, there is a $\delta>0$ such that $|f(x)-f(y)| \leqslant \epsilon$ for all $x, y \in[0,1]$ with $|x-y| \leqslant \delta$.]