# Proof of inequality in Weierstrass approximation theorem proof through probability

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.