Alphabets:

The alphabet \(\Sigma\) is a finite set \(\lvert \Sigma \rvert = \alpha \geq 2\) and \(\Sigma = \{k\}_{k=0}^{\alpha-1} \subset \mathbb{N}\).

Simply normal sequence to base \(\alpha\):

A sequence \(X \in \Sigma^{\infty}\) is simply normal to base \(\alpha\) if:

\begin{equation} \forall k \in \Sigma, \lim_{n \to \infty} \frac{\mathcal{N}(X_n, k)}{n} = \frac{1}{\lvert \Sigma \rvert} \end{equation}

where \(\mathcal{N}(X_n,k)\) denotes the number of times the digit \(k \in \mathbb{Z}\) appears in the first \(n\) digits of the sequence \(X\).

Normal to base \(\alpha\):

Let \(\Sigma = \{k\}_{k=0}^{\alpha-1} \subset \mathbb{N}\), \(w\) be a finite string in \(\Sigma^*\) and \(\mathcal{N}(X_n,w)\) be the number of times the string \(w\) appears as a substring in the first \(n\) digits of the sequence \(X \in \Sigma^{\infty}\).

Given this definition, \(X \in \Sigma^{\infty}\) is said to be normal to base \(\alpha\) if for any finite string \(w \in \Sigma^n\) we have:

\begin{equation} \lim_{n \to \infty} \frac{\mathcal{N}(X_n, w)}{N-n+1} = \frac{1}{\lvert \Sigma^n \rvert} \end{equation}

In other words, \(X\) is normal if all strings of equal length occur with equal frequency.

Simply normal to base \(\alpha^k\):

Given \(\Lambda = \Sigma^k\), \(X \in \Lambda^{\infty}\) is simply normal to base \(\alpha^k\) if:

\begin{equation} \forall \lambda \in \Lambda, \lim_{n \to \infty} \frac{\mathcal{N}(X_n, \lambda)}{n} = \frac{1}{\lvert \Lambda \rvert} = \frac{1}{\alpha^k} \end{equation}

where \(\mathcal{N}(X_n,\lambda)\) denotes the number of times the string \(\lambda \in \Lambda\) appears in the first \(n\) digits of the sequence \(X\).

Lemma 1:

Given a finite alphabet \(\Sigma\), \(X \in \Sigma^{\infty}\) if and only if \(X \in \Lambda^{\infty}\) where \(\Lambda = \Sigma^n\) for any \(n \in \mathbb{N}\).

Lemma 2:

Given the set \(\Sigma \subset N\) where \(\lvert \Sigma \rvert = \alpha\), there is a bijective map from \(\Sigma^n\) to \(\Lambda = \{k\}_{k=0}^{\alpha^n -1}\)

Theorem:

A number is normal to base \(\alpha\) if and only if it is simply normal to base \(\alpha^k\) for any \(k \in \mathbb{N}\).

Proof:

Apply Lemma 1 and Lemma 2.

References:

  1. Davar Khoshnevisan. Normal Numbers are Normal

  2. Ferdinánd Filip & Jan Sustek. An elementary proof that almost all real numbers are normal. Acta Univ. Sapientiae, Mathematica. 2010.

  3. Copeland, A. H. and Erdős, P. “Note on Normal Numbers.” Bull. Amer. Math. Soc. 52, 857-860, 1946.