# (Borel) Normal number problem

Problem: Given an integer $$b \ge 2$$, a number $$x \in [0,1)$$ is (Borel) normal base-b, if its b-ary representation as a sequence $$(\sigma_1,\sigma_2,...)$$-where $$\sigma_i \in \{0,1,...,b-1\}$$ are such that $$x=\sum_{i \ge 1} \sigma_i b^{-i}$$-obeys the following: For eaach $$r \ge 1$$ and each $$\overline{\sigma_1},...,\overline{\sigma_r} \in \{0,1,...,b-1\}, \frac{1}{n}\#\{k=1,...,n:(\sigma_{k+1},...,\sigma_{k+r})=(\overline{\sigma_1},...,\overline{\sigma_r})\}$$ converges to $$b^{-r}$$ as $$n \rightarrow \infty$$. A number x is absolutely normal if it is normal base b for every integer $$b \ge 2$$. Prove if $$\mathcal{U}=\textbf{Uniform}([0,1])$$, then $$\mathcal{U}$$ is absolutely normal almost surely.

Theorem 1: Almost every real number is absolutely normal.

Proof: A number $$x \in (0,1)$$ is not absolutely normal if there exist $$b \ge 2$$, $$L \in \mathbf{N}$$ and $$a_1,...,a_L \in \{0,...,b-1\}$$ such that if $$x=\sum_{n=1}^{\infty} \frac{c_n}{b^n}$$ then $$\textbf{lim inf}_{n \rightarrow \infty} \frac{\# \{n \le N-L |c_{n+i}=a_i,i=1,...,L\}}{N}<\frac{1}{b^L}$$. Then there exists $$s \in \{0,...,L-1\}$$ such that $$\textbf{lim inf}_{n \rightarrow \infty} \frac{\# \{n \le N-L, n \equiv s (\textbf{mod L}) |c_{n+i}=a_i,i=1,...,L\}}{N}<\frac{1}{Lb^L}$$. Hence for some rational $$\beta<\frac{1}{Lb^L}$$, $$\textbf{lim inf}_{n \rightarrow \infty} \frac{\# \{n \le N-L, n \equiv s (\textbf{mod L}) |c_{n+i}=a_i,i=1,...,L\}}{N} \le \beta$$. Denote by $$R_{b,La,s,\beta}$$ the set of all $$x=\sum_{n=1}^{\infty} \frac{c_n}{b^n}$$ satisfying $$\textbf{lim inf}_{n \rightarrow \infty} \frac{\# \{n \le N-L, n \equiv s (\textbf{mod L}) |c_{n+i}=a_i,i=1,...,L\}}{N} \le \beta$$ . The result of the prvious paragraph is that the set of not absolutely normal number is a subset of $$\bigcup_{b=2}^{\infty} \bigcup_{L=1}^{\infty} \bigcup_{a_1,...,a_L}^{b-1} \bigcup_{s=0}^{L-1} \bigcup_{\beta \in (0, \frac{1}{Lb^L}\cap \mathcal{Q}} R_{b,L,a,s,\beta}$$. It is sufficient to prove every set $$R_{b,L,a,s,\beta}$$ has zero measure. Then the set of not absolutely normal numbers is a subset of a countable union of null sets, hence it is a null set.

Let $$b \ge 2, L \in \mathcal{N}, a_1,...,a_L \in \{0,...,b-1\}, s \in \{0,...,L-1\}$$ and $$\beta \in (0,\frac{1}{Lb^L}$$. Put $$A=a_1b^{L-1}+a_2b^{L-2}+...+a_L$$. Let $$x=\sum_{n=1}^{\infty} \frac{c_n}{b^n}=\sum_{n=1}^s \frac{d_n}{b^n}+\frac{1}{b^s}\sum_{n=1}^{\infty} \frac{d_{s+n}}{b^{Ln}} \in R_{b,L,a,s\beta}$$. Then obviously $$\# \{n \le N-L,n \equiv s(\textbf{mod L})|c_{n+i}=a_i,i=1,...,L\}=\# \{s. Hence $$\textbf{lim inf}_{M \rightarrow \infty} \frac{\# \{s. From this we obtain $$R_{b,L,a,s\beta} \subseteq P$$, where $$P=\{x=\sum_{n=1}^s \frac{d_n}{b^n}+\frac{1}{b^s}\sum_{n=1}^{\infty} \frac{d_{s+n}}{b^{Ln}}|\textbf{lim inf}_{N \rightarrow \infty} \frac{\# \{s. Then it is sufficient to prove that the set P has zero measure.

The complete version of the proof is found here. An elementary proof that almost all real numbers are normal

My question is how am I supposed to mimic the proof to solve the problem? Thanks a lot!

• "If $\mathcal U = {\bf Uniform}([0,1])$, then $\mathcal U$ is $X$ almost surely" means the same as "Almost every member of $[0,1]$ is $X$". Nov 13, 2020 at 5:03
• @r.e.s. Thanks, fixed it. Nov 13, 2020 at 17:31

I found [5] in the article you mentioned particularly useful. We only need to prove a simpler version of theorem 8.1 (and corollary 8.2) in the book. So here is my answer:

Suppose $$X\sim U(0,1)$$. Given $$b\geq 2$$, and fixed $$r\geq 1$$. Consider the $$b-$$ary expansion of $$x = \sum_{i=1}^\infty \sigma_ibi^{-1}$$. We are interested in the probability of a given string: $$(\bar{a}_1,\bar{a}_2,...\bar{a}_r)$$, where $$a_i = 0,1,...b-1$$.

If the target string matches $$x$$ at index $$m$$, we can rewrite $$x$$ by replacing the digits from index $$m$$ to $$m+r-1$$: $$\begin{split} x &= \sum^\infty_1 \frac{\sigma_i}{b_i}\\ &= \sum^{m-1}_{1} \frac{\sigma_i}{b^i} + \sum^{m+r-1}_{m} \frac{a_i}{b^i} + \sum_{m+r}^\infty \frac{\sigma_i}{b^i} \end{split}$$ Multiply both sides by $$b^{m-1}$$: $$b^{m-1}x = (b^{m-1}\sum^{m-1}_{1} \frac{\sigma_i}{b^i}) + \frac{a_mb^{r-1}+a_{m+1}b^{r-2}+ ...a_{m+r-1}}{b^r} + \sum_{r+1}^\infty \frac{\sigma_{m+i-1}}{b^i}$$ The fractional part $$\{b^{m-1}x\}$$ doesn't contain $$(b^{m-1}\sum^{m-1}_{1} \frac{\sigma_i}{b^i})$$, and we have $$\sum_{r+1}^\infty \frac{\sigma_{m+i-1}}{b^i}< 1b^{-r}$$ since they are the trailing digits of this expansion. Therefore, $$\{b^{m-1}x\}\in [\frac{a_mb^{r-1}+a_{m+1}b^{r-2}+ ...a_{m+r-1}}{b^r}, \frac{a_mb^{r-1}+a_{m+1}b^{r-2}+ ...a_{m+r-1} + 1}{b^r}) = I_r$$ Whenever there is a matching sequence, we have $$\{b^{m-1}x\}\in I_r$$.

Since $$X\sim U(0,1)$$, we have that $$\{b^{m-1}X\}\sim U(0,1)$$ because any fractional part is uniformly distributed across each interval $$[n,n+1)$$, where $$n = 0,1,...b^{m-1}-1$$. Since $$b^{m-1}X$$ is uniform, each interval has probability $$1/b^{m-1}$$ and therefore the marginal distribution of $$\{b^{m-1}X\}$$ is uniform $$(0,1)$$.

Given the first $$N$$ digits of the expansion of $$x$$, we need to check $$N-r+1$$ possible starting point of the desired sequence $$b_1b_2...b_r$$ and this is equivalent to $$\sum^{N-r+1}_1X1_{I_r}$$, where $$X\sim U(0,1)$$. Hence by SLLN, $$\lim_n \frac{\{\# k = 1,2,...n: (\sigma_k...\sigma_{k+r}) = (b_1,b_2...b_r)\}}{n} = \lim \frac{\sum^{n-r+1}_1X1_{I_r}}{n-r+1}\frac{n-r+1}{n}\xrightarrow[]{}\frac{1}{b^r}$$ almost surely.

This is true for any $$r\geq 1$$, so $$X$$ is normal almost surely. We can do the same for every $$b\geq 2$$, and then take the countable intersection of the above events so that $$X$$ is normal with respect to every base $$b\geq 2$$ with probability 1. We are done.

See theorem 8.1 in https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf