3
$\begingroup$

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!

$\endgroup$
2
  • 2
    $\begingroup$ "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$". $\endgroup$ Nov 13, 2020 at 5:03
  • $\begingroup$ @r.e.s. Thanks, fixed it. $\endgroup$
    – neveryield
    Nov 13, 2020 at 17:31

1 Answer 1

1
+100
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.