I found this exercise in my probability theory book. The problem guides you through a proof of the Weierstrass Approximation Theorem through probability theory. My question is only about part b, so any help or hint is much appreciated. I can make the exercise, except for part $b$, and I show all my workings below. I understand that you might want to see my workings for $b$, but I have really no idea. First I quote Chebyshev's inequality, because apparently we need this.
Thus: my question is only about part b, my work for the other parts can be found below.
$\bf{Chebyshev's \ inequality}$ If $Y$ is a random variable and $\mathbb{E}(Y^2)<\infty$, then $$\mathbb{P}(|Y|\geq t)\leq \frac{\mathbb{E}(Y^2)}{t^2}, \quad \mathrm{for \ } t>0.$$
I quote the exercise:
Let ($X_i$) be a sequence of i.i.d. Bernoulli$(p)$ variables, thus $\mathbb{P}(X_i=0)=1-p$ and $\mathbb{P}(X_i=1)=p$, for all $i\in\mathbb{N}$.
a) Let $f$ be a continuous function of $[0,1]$ and prove that $$B_n(p)=\mathbb{E}\left(f\left(\frac{\sum_{i=1}^nX_i}{n}\right)\right)$$ is a polynomial in $p$ of degree at most $n$.
b) Use Chebyshev's inequality to prove that for all $p$ such that $0\leq p\leq1$ and for any $\epsilon>0$, $$\sum_{k\in K}\binom{n}{k}p^k(1-p)^{n-k}\leq\frac{1}{4n\epsilon^2},$$ where $K=\{k:0\leq k\leq n, |k/n-p|>\epsilon\}$.
c) Using this and the fact that $f$ is bounded and uniformly continuous on $[0,1]$, prove the following version of the Weierstrass approximation theorem: $$\lim_{n\to\infty}\sup_{0\leq p\leq1}|f(p)-B_n(p)|=0.$$
For part $a$, if we let $Y_n:=\sum_{i=1}^nX_i$, then $Y_n\sim \mathrm{Bin}(n,p)$. Thus $$B_n(p)=\mathbb{E}\left(f\left(\frac{\sum_{i=1}^nX_i}{n}\right)\right)=\mathbb{E}\left(f\left(\frac{Y_n}{n}\right)\right)=\sum_{k=0}^n f\left(\frac{k}{n}\right)\binom{n}{k}p^k(1-p)^k$$ is a polynomial in $p$ of degree at most $n$. This follows directly from just writing out the expectation of the binomial distribution.
For part $c$, $f$ is continuous on the closed interval $[0,1]$, so $f$ is uniformly continuous and bounded on $[0,1]$, and assumes it's minimum and maximum on this interval. These are all basic real analysis results. Since $f$ is bounded on $[0,1]$, there exists an $M\in\mathbb{R}$ such that $|f(p)|\leq M$, for all $p\in[0,1]$.
From part $b$, we know that $0\leq p\leq1$ and for any $\epsilon>0$, $$\sum_{k\in K}\binom{n}{k}p^k(1-p)^{n-k}=\mathbb{P}(|k/n-p|\geq \epsilon)\leq\frac{1}{4n\epsilon^2},$$ where $K=\{k:0\leq k\leq n, |k/n-p|>\epsilon\}$. Thus we obtain the following: In equation 1, we take the limit of the result of part b; equation 2 follows because of uniform continuity of $f$; equation 4 follows because of linearity of expectation, part $a$ and because $f(p)$ is fixed; equation 5 follows from the partition theorem for expectations: $$\begin{align}
&\lim_{n\to\infty}\mathbb{P}(|\frac{k}{n}-p|\geq\epsilon) = 0 & (1)\\
&\lim_{n\to\infty}\mathbb{P}\left(|f\left(\frac{k}{n}\right)-f(p)|\geq\epsilon\right) = 0 & (2)\\
&\lim_{n\to\infty}\mathbb{E}\left(|f\left(\frac{k}{n}\right)-f(p)|\right) = & (3)\\
&\lim_{n\to\infty}|B_n(p)-f(p)|=& (4)\\
&\lim_{n\to\infty}\mathbb{E}\left(|f\left(k/n\right)-f(p)|\Bigg|k/n-p|\geq\epsilon\right)\cdot\mathbb{P}(|k/n-p|\geq\epsilon)+& \\
&\lim_{n\to\infty}\mathbb{E}\left(|f\left(k/n\right)-f(p)|\Bigg|\frac{k}{n}-p|<\epsilon\right)\cdot\mathbb{P}(|k/n-p|<\epsilon)=& (5)\\
& 0+0=0.& (6)\\
\end{align}$$
The first term is zero because $\mathbb{P}(|\frac{k}{n}-p|\geq\epsilon)$ goes to zero as $n$ goes to $\infty$, as shown in part $b$, and because the boundedness of $f$. The second term goes to zero because: (i) $f(k/n)-f(p)$ goes to zero as $n$ goes to infinity because $f$ is uniformly continuous, because $\lim_{n\to\infty}k/n=p$ because of the law of large numbers (remember that $k$ denotes the number of successes in a $\mathrm{Bin}(n,p)$ experiment); and (ii) because $\mathbb{P}(|k/n-p|<\epsilon)$ is bounded by definition of a probability measure.
Thus $\lim_{n\to\infty}|B_n(p)-f(p)|=0$, for any $p\in[0,1]$, which is the interval where $f$ is uniformly continuous, and thus $\lim_{n\to\infty}\sup_{0\leq p\leq1}|f(p)-B_n(p)|=0$. Thus any continuous function on $[0,1]$ can be uniformly approximated by polyinomials on $[0,1]$. Obvious rescaling proves the Weierstrass Approximation Theorem.
EDIT: Should I use for part $b$ that $\sum_{k\in K}\binom{n}{k}p^k(1-p)^{n-k}$, where $K=\{k:0\leq k\leq n, |k/n-p|>\epsilon\}$ equals $$\begin{eqnarray}\mathbb{P}(|k/n-p|\geq \epsilon) & = & \mathbb{P}(|k-np|\geq \epsilon n)\\&=& \mathbb{P}(|k-\mathbb{E}(Y_n)\tag{with $Y_n\sim\mathrm{Bin}(n,p)$}|\geq \epsilon n)\\ & \leq & \frac{1}{\epsilon^2n^2}\mathbb{E}((k-np)^2)\tag{Chebyshev's inequality}\\ &\leq& \frac{1}{\epsilon^2n^2}(\frac12\cdot\frac12\cdot n) \tag{variance is maximized if $p=\frac12$}\\&=& \frac{1}{4n\epsilon^2}\end{eqnarray}$$
I think this is correct, after posting I came a lot further through reading on wikipedia and the like.
Best Answer
I will present a full proof. Write $S_{n}:=\operatorname{Bin}(n, x)$. Note that $|f|$ is uniformly bounded by some $\mathrm{M}$ and uniformly continuous $-$ fix $\epsilon>0,$ and let $\delta$ be such that $|f(x)-f(y)|<\frac{\epsilon}{2}, \forall|x-y|<\delta.$ Then, $$ \begin{aligned} \mid B_{n}(x, f)-f(x) &|=| \mathbb{E}\left(f\left(\frac{S_{n}}{n}\right)-f(x)\right) \mid \\ &=\left|\mathbb{E}\left(f\left(\frac{S_{n}}{n}\right)-f(x)\right) \mathbb{I}\left(\left|\frac{S_{n}}{n}-x\right|<\delta\right)\right| \\ &+\left|\mathbb{E}\left(f\left(\frac{S_{n}}{n}\right)-f(x)\right) \mathbb{I}\left(\left|\frac{S_{n}}{n}-x\right| \geq \delta\right)\right| \leq \epsilon+2 M \cdot P\left(\left|\frac{S_{n}}{n}-x\right| \geq \delta\right) \\ & \leq \frac{\epsilon}{2}+2 M \frac{x(1-x)}{n \delta^{2}} \leq \frac{\epsilon}{2}+\frac{M}{2 n \delta^{2}} \end{aligned} $$ The theorem is proved