The problem of polynomial approximation is one of the classical problems in numerical analysis: Suppose that we are given the values of an unknown function \(f\) at \(n+1\) points. How do we approximate \(f\) with a polynomial of degree \(n\)?

To be more precise, let \(f\) be continuous on \([0,1].\) Define the Bernstein polynomial \[f_n(x) :=\sum_{k = 0}^n \binom{n}{k} x^k (1 - x)^{n-k} f \biggl(\frac{k}{n}\biggr)\,.\] Then we claim that \(f_n\) converges to \(f\) uniformly on \([0,1].\)

To see why, take independent random variables \(X_1, \dots, X_n,\) each having a Bernoulli law with parameter \(p.\) Then \(S_n = X_1 + \cdots + X_n\) has binomial law (recall Exercise 2.2) \[\mathbb{P}(S_n = k) = \binom{n}{k} p^k (1 - p)^{n-k}\] and hence \[\tag{3.9} \mathbb{E}\biggl[f\biggl(\frac{S_n}{n}\biggr)\biggr] = f_n(p)\,.\] Then by the law of large numbers we have \(\frac{S_n}{n} \to p\) in \(L^2,\) so that we expect \(f_n(p) \to f(p).\) Let us carry out this argument carefully. Let \(\varepsilon> 0\) and choose \(\delta > 0\) such that \(\lvert x-y \rvert < \delta\) implies \(\lvert f(x) - f(y) \rvert < \varepsilon\) (since \(f\) is continuous, and hence uniformly continuous, on the compact interval \([0,1].\)) Then we partition \[1 = \mathbf 1_{\lvert S_n/n - p \rvert < \delta} + \mathbf 1_{\lvert S_n/n - p \rvert \geqslant\delta}\] and use this to estimate \[\begin{gathered} \biggl\lvert \mathbb{E}\biggl[f\biggl(\frac{S_n}{n}\biggr)\biggr] - f(p) \biggr\rvert \leqslant\varepsilon+ 2 \lVert f \rVert_{L^\infty} \mathbb{P}\biggl(\biggl\lvert \frac{S_n}{n} - p \biggr\rvert \geqslant\delta\biggr) \\ \leqslant\varepsilon+ 2 \lVert f \rVert_{L^\infty} \frac{\mathop{\mathrm{Var}}(S_n / n)}{\delta^2} = \varepsilon+ 2 \lVert f \rVert_{L^\infty} \frac{p(1-p)}{n \delta^2} \leqslant\varepsilon+ \lVert f \rVert_{L^\infty} \frac{1}{2 n \delta^2}\,, \end{gathered}\] where in the second step we used Chebyshev’s inequality. Recalling (3.9), we conclude the proof.

Let \(p \in \mathbb{N}^*\) and \(l \in \{1, \dots, p\}.\) Define \[Y^l_n :=(X_{(n-1)p + l}, \dots, X_{(n-1)p + l + p-1})\,.\] Explicitly, the sequence \(Y_1^l, Y_2^l, \dots\) is \[(X_{l}, \dots, X_{l + p-1}), (X_{p + l}, \dots, X_{p + l + p-1}), \dots\] By Example 3.20 and Remark 3.15, \((Y^l_n)_{n \in \mathbb{N}^*}\) is an independent family of random variables, for each \(l \in \{1, \dots, p\}.\) Hence, for any \(x = (x_1, \dots, x_p) \in \{0,1\}^p,\) applying Corollary 3.28 to the events \(A_n = \{Y^l_n = x\},\) we find that \[\frac{1}{n} \# \Bigl\{i \in \{1, \dots, n\} \,\colon Y^l_i = x\Bigr\} \overset{\text{a.s.}}{\longrightarrow} \frac{1}{2^p}\,.\] Since this holds for all \(l \in \{1, \dots, p\}\) we deduce that \[\frac{1}{n} \# \Bigl\{i \in \{1, \dots, n\} \,\colon(X_{i}, \dots, X_{i + p-1}) = x\Bigr\} \overset{\text{a.s.}}{\longrightarrow} \frac{1}{2^p}\,.\] Taking the countable union over \(p \in \mathbb{N}^*\) and \(x \in \{0,1\}^p,\) we conclude: almost surely, for all \(p \in \mathbb{N}^*,\) \(x \in \{0,1\}^p,\) \[\frac{1}{n} \# \Bigl\{i \in \{1, \dots, n\} \,\colon(X_{i}, \dots, X_{i + p-1}) = x\Bigr\} \longrightarrow \frac{1}{2^p}\,.\] In words: for almost every real number \(\omega \in [0,1),\) any finite sequence of length \(p\) appears with frequency \(2^{-p}\) in the binary digits of \(\omega.\)

Note that it is difficult to construct a number \(\omega\) with this rather striking property. The easiest way to show that such a number exists is the preceding probabilistic argument. Not only does it show that such a number exists, but it shows that almost all numbers have this property.