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<n \le [\frac{N-s}{L}]|d_n=A\}$$. Hence $$\textbf{lim inf}_{M \rightarrow \infty} \frac{\# \{s<n \le M| d_m=A}{M}=\textbf{lim inf}_{N \rightarrow \infty} \frac{\# \{s<n \le [\frac{N-s}{L}]|d_n=A\}}{[\frac{N-s}{L}]} \le L\beta$$. 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<n \le N |d_n=A\}}{N} \le L \beta\}$$. 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!
Best Answer
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