TAOCP 3.5 Exercise 1

Exercise 1. [10] Can a periodic sequence be equidistributed?

Verified: yes
Solve time: 1m12s

No. Let the sequence have period $p$, so that $U_{n+p}=U_n$ for all $n$. Then the sequence contains only the $p$ values $U_0,U_1,\ldots,U_{p-1}$ repeated indefinitely.

For any interval $[u,v)$, the quantity $\nu(n)/n$ approaches the fraction of these $p$ values that lie in $[u,v)$. Hence every limiting frequency is of the form $m/p$, where $m$ is an integer. If the sequence were equidistributed, Definition A would require

$$ \Pr(u\le U_n<v)=v-u $$

for every interval $[u,v)$. Choosing an interval whose length is not of the form $m/p$, for example $v-u=\frac1{p+1}$, gives a contradiction, since $\frac1{p+1}\ne m/p$ for every integer $m$.

Therefore no periodic sequence can be equidistributed. $\boxed{\text{No periodic sequence is equidistributed.}}$