Weierstrass Approximation Theorem

Theorem.

The set of polynomials is dense in $C^0([0,1],\mathbb{R})$, i.e. for any continuous $f:[0,1]\to \mathbb{R}$ and any $\epsilon >0$, there exists a polynomial $p(x)$ such that $|f(x)-p(x)|<\epsilon$ for all $x\in [0,1]$.

Remark.

Proving this theorem with just the tools of analysis is possible, but quite cumbersome. Borrowing some ideas from probability makes the proof much simpler and provides better motivations for the seemingly arbitrary tools used.

Proof.

Let $f:[0,1]\to \mathbb{R}$ be some arbitrary continuous function. We start by observing that because $f$ is continuous function on a compact domain, it must be uniformly continuous (Continuous on compact domain implies uniformly continuous). Recall that $f$ is uniformly continuous if for all $\epsilon >0$, there exists a universal $\delta >0$ such that for any two points in $[0,1]$ of distance less than $\delta$, their images are of distance less than $\epsilon$, i.e.

$$|s-t|<\delta ⟹|f(s)-f(t)|<\epsilon .$$

Uniform continuity is one of the main engines of the proof.

The first tool we borrow from probability is the binomial random variable. Let $X\sim \text{Binomial}(n,x)$ where $x$ is some arbitrary real number in $[0,1]$. Recall that $P(X=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k(1-x{)}^{n-k}$ , $\mathbb{E}\left(\frac{X}{n}\right)=x$, $\text{Var}\left(\frac{X}{n}\right)=\frac{1}{n^2}\text{Var}(X)=\frac{nx(1-x)}{n^2}=\frac{x(1-x)}{n}$, and that Chebyshev’s Inequality states that

$$P\left(\left|\frac{X}{n}-\mathbb{E}\left(\frac{X}{n}\right)\right|\ge l\sqrt{\text{Var}\left(\frac{X}{n}\right)}\right)=P\left(\left|\frac{X}{n}-x\right|\ge l\sqrt{\frac{x(1-x)}{n}}\right)\le \frac{1}{l^2}.$$

Chebyshev’s Inequality is the second tool we borrow from probability and is the other main engine of the proof.

Let us define the following polynomial (a.k.a. the Bernstein polynomial):

$$b_n(x):=\sum _{k=0}^{n}P(X=k)f(\frac{k}{n})=\sum _{k=0}^n\frac{n!}{k!(n-k)!}{x}^k(1-x{)}^{n-k}f(\frac{k}{n}).$$

Clearly this is in fact a polynomial with respect to $x$. We will show that for all $\epsilon >0$, there exists $n$ large enough such that for all $x\in [0,1]$, $|f(x)-b_n(x)|<\epsilon$.

We proceed by examining $|f(x)-b_n(x)|=|b_n(x)-f(x)|$:

$$|b_n(x)-f(x)|=\left|\sum _{k=0}^{n}P(X=k)f\left(\frac{k}{n}\right)-f(x)\sum _{k=0}^{n}P(X=k)\right|$$

where we used the fact that ${\sum }_{k=0}^{n}P(X=k)=1$ (since probabilities are normalized). Then,

$$\left|\sum _{k=0}^{n}P(X=k)f(\frac{k}{n})-f(x)\sum _{k=0}^{n}P(X=k)\right|=\left|\sum _{k=0}^{n}P(X=k)f(\frac{k}{n})-f(x)\right|,$$

and by $n$ applications of the Triangle Inequality,

$$\left|\sum _{k=0}^{n}P(X=k)f(\frac{k}{n})-f(x)\right|\le \sum _{k=0}^{n}P(X=k)\left|f(\frac{k}{n})-f(x)\right|.$$

In order to use our two inequalities (one from uniform continuity and the other from Chebyshev), we split the sum into two. We do this by splitting the indices $\{0,1,\dots ,n\}$ into two sets based on some parameter $\eta >0$ that we will set later:

$$S_l=\left\{k\in \{0,1,\dots ,n\}:\left|\frac{k}{n}-x\right|<\eta \right\}$$

and

$$S_g=\left\{k\in \{0,1,\dots ,n\}:\left|\frac{k}{n}-x\right|\ge \eta \right\}.$$

Then, by the triangle inequality,

$$\sum _{k=0}^{n}P(X=k)\left|f(\frac{k}{n})-f(x)\right|\le \sum _{k\in S_l}P(X=k)\left|f(\frac{k}{n})-f(x)\right|+\sum _{k\in S_g}P(X=k)\left|f(\frac{k}{n})-f(x)\right|.$$

We will bound both terms above by $\frac{\epsilon }{2}$.

For the first term, we leverage uniform continuity. We know that given $\frac{\epsilon }{2}>0$, there exists $\delta >0$ such that for any $x\in [0,1]$ and any $k\in \{0,1,\dots ,n\}$ (which means $\frac{k}{n}\in [0,1]$), $|\frac{k}{n}-x|<\delta ⟹|f\left(\frac{k}{n}\right)-f(x)|<\frac{\epsilon }{2}$. We will set our parameter $\eta$ to the $\delta$ obtained here. Then,

$$\sum _{k\in S_l}P(X=k)\left|f\left(\frac{k}{n}\right)-f(x)\right|<\frac{\epsilon }{2}\sum _{k\in S_l}P(X=k)\le \frac{\epsilon }{2},$$

where we used the fact that ${\sum }_{k\in S_l}P(X=k)\le 1$.

For the second term, we will leverage Chebyshev’s Inequality. We first observe that since $f$ is continuous on a compact domain, it will have a compact image. This means its image will be bounded, i.e. there exists $M\in \mathbb{R}$ such that for all $x\in [0,1]$, $f(x)\le M$. Thus,

$$\sum _{k\in S_g}P(X=k)\left|f(\frac{k}{n})-f(x)\right|\le 2M\sum _{k\in S_g}P(X=k).$$

We then observe that ${\sum }_{k\in S_g}P(X=k)=P\left(|\frac{X}{n}-x|\ge \eta \right)$. This is because $S_g$ is exactly the set of elements $k$ in the sample space such that $|\frac{k}{n}-x|\ge \eta$. If $\eta =l\sqrt{\text{Var}\left(\frac{X}{n}\right)}$, then $\frac{1}{l^2}=\frac{\text{Var}\left(\frac{X}{n}\right)}{{\eta }^2}$. So, by Chebyshev,

$$2M\sum _{k\in S_g}P(X=k)=2M\cdot P\left(\left|\frac{X}{n}-x\right|\ge \eta \right)\le 2M\cdot \frac{1}{l^2}=2M\cdot \frac{\text{Var}\left(\frac{X}{n}\right)}{{\eta }^2}=2M\cdot \frac{x(1-x)}{n{\eta }^2}.$$

Observe that $\frac{x(1-x)}{n{\eta }^2}\to 0$ as $n\to \infty$. So, for large enough $n$, $\frac{x(1-x)}{n{\eta }^2}<\frac{\epsilon }{4M}$ is true such that

$$\sum _{k\in S_g}P(X=k)\left|f\left(\frac{k}{n}\right)-f(x)\right|<2M\cdot \frac{\epsilon }{4M}=\frac{\epsilon }{2}.$$

We have successfully bounded both terms we had set out to bound. Thus, we have obtained our desired bound:

$$\sum _{k=0}^{n}P(X=k)\left|f\left(\frac{k}{n}\right)-f(x)\right|<\frac{\epsilon }{2}+\frac{\epsilon }{2}=\epsilon .\square$$

References: Koralov, L.; Sinai, Y. (2007). ""Probabilistic proof of the Weierstrass theorem"". Theory of probability and random processes (2nd ed.). Springer. p. 29.