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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.