Skip to main content
1 of 5
Zeyu
  • 537
  • 4
  • 15

How to show that an infinite sequence is normal if and only if every block of equal length appears with equal frequency

An infinite sequence is normal if all strings of equal length occur with equal asymptotic frequency.

Formally, let $\Sigma$ be a finite alphabet of $b$ digits. Let $S$ be an infinite sequence and $\omega$ a finite nonempty sequence, both over $\Sigma$, i.e., $S\in\Sigma^\infty$ and $\omega\in\Sigma^*$. Define $N_S(\omega, n)$ to be the number of times the string $\omega$ appears as a substring in the first $n$ digits of the sequence $S$. $S$ is normal if for all finite strings $\omega\in\Sigma^*$,

$$ \lim_{n\rightarrow\infty}{N_S(\omega,n)\over n}={1 \over b^{\left|\omega\right|}} $$

Or you can find the definition here: http://en.wikipedia.org/wiki/Normal_number

The webpage in wiki above also states a property of normal sequences: "A sequence is normal if and only if every block of equal length appears with equal frequency. (A block of length $k$ is a substring of length $k$ appearing at a position in the sequence that is a multiple of k: e.g. the first length-$k$ block in $S$ is $S[1..k]$, the second length-$k$ block is $S[k+1..2k]$, etc.)"

Wiki gives me the reference. More specifically, it says this result was made explicit in the work of Bourke, Hitchcock, and Vinodchandran (2005). But I cannot figure out which theorems in the reference imply this property and how they do.

This "block characterization of normality" seems a natural property and should be easy to prove, but so far I still have difficulties in proving the "only if" direction. On the other hand this result seems important as it implies several other properties (see wiki). One paper I read about the connections between normal sequences and finite automata also relies on this result.

So I will be grateful if someone can help.

Zeyu
  • 537
  • 4
  • 15