Canonical base-b expansions and normal numbers

Fix an integer $b\ge 2$. For $x\in [0,1)$, its canonical base-$b$ digits are

$d_j^{(b)}(x)=\lfloor b{D}_b^{j-1}x\rfloor \in \{0,\dots ,b-1\},j\ge 1,$

where $D_b(x)=\{bx\}$ is the integer-base circle map from Integer-base maps and b-adic circle intervals and the floor is supplied by Integer part: for every real $x$ there is exactly one integer $m$ with $m\le x<m+1$. Thus

$D_b^{j}x=b{D}_b^{j-1}x-d_j^{(b)}(x)\mathrm{.}$

Iterating this recurrence gives

$x={\sum }_{j=1}^n{d}_j^{(b)}(x)b^{-j}+b^{-n}{D}_b^{n}x\mathrm{.}$

Since $0\le D_b^{n}x<1$, the remainder tends to zero. Hence the digit string represents $x$:

$x=0.d_1^{(b)}(x)d_2^{(b)}(x)\cdots {}_b={\sum }_{j=1}^{\mathrm{\infty }}{d}_j^{(b)}(x)b^{-j}\mathrm{.}$

At a $b$-adic rational the recurrence chooses the expansion that eventually has only zero digits, called the terminating expansion. Equivalently, the canonical expansion is the expansion that is not eventually equal to $b-1$. Indeed, an eventually-$(b-1)$ tail represents the same number as incrementing the last preceding digit and then appending zeros; conversely, if the greedy digits were all $b-1$ after some place, the displayed remainder identity would force the corresponding iterate $D_b^{N}x$ to be $1$, contrary to $D_b^{N}x\in [0,1)$.

For a word $w=(w_1,\dots ,w_{\mathrm{\ell }})\in \{0,\dots ,b-1{\}}^{\mathrm{\ell }}$ and $n\ge 1$, write

$N_n(w,x)=\mathrm{\#}\{0\le k<n:(d_{k+1}^{(b)}(x),\dots ,d_{k+\mathrm{\ell }}^{(b)}(x))=w\}\mathrm{.}$

The number $x$ is normal in base $b$ if, for every length $\mathrm{\ell }\ge 1$ and every such word $w$,

$\frac{N_n(w,x)}{n}⟶b^{-\mathrm{\ell }}\mathrm{.}$

It is normal if it is normal in every integer base $b\ge 2$.