Skip to main content
2 of 2
Gave the other direction.
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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$.

Douglas Zare
  • 28k
  • 6
  • 90
  • 130