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

Question

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 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$. The sequence $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 that paper 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. That is, how can I show the every block of equal length appears with equal frequency when the sequence is known to be normal? 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.

Answer 1

Earlier, I gave the following sketch:

Evenly distributed blocks implies evenly distributed sequences:

Estimate the upper and lower densities of a sequence of length $k$ from the frequencies of blocks of length $L$ much greater than $k$. The difference between the upper and lower estimates is from the sequences which cross the ends of the blocks. As $L$ increases, the difference drops to $0$.

However, you wanted the other direction.

Evenly distributed sequences implies evenly distributed blocks:

For sufficiently large $L$ much greater than $k$, most sequences of length $L$ contain about the right number of copies of each subsequence of length $k$ offset by each class mod $k$, so that any translate of $S$ contains about the right number of blocks of each type. That is, we can choose $L_\epsilon$ so that a random sequence of length $L_\epsilon$ has probability over $1-\epsilon$ of being $\epsilon$-good, having at least $(1-\epsilon) L_\epsilon/(k b^k)$ and at most $(1+\epsilon)L_\epsilon/(k b^k)$ copies of each block with each offset mod $k$. (A weakly dependent law of large numbers suffices.)

That the sequences of length $L_\epsilon$ are evenly distributed means that for each sequence $B$ of length $k$, the lower density is at least $(1-\epsilon)^2\times$average of pairs of an $\epsilon$-good sequence of length $L_\epsilon$ and a block it contains with pattern $B$. Thus, the lower density of blocks of pattern $B$ is at least $(1-\epsilon)^2\times$average. Since this is true for all $\epsilon\gt 0$, the density is $1/b^k$.