TAOCP 3.5 Exercise 8

Exercise 8. [M15] Prove (13).

Verified: yes
Solve time: 1m24s

Solution

Assume that the sequence $\langle U_n\rangle$ is $(m,k)$-distributed, and let $d$ be a divisor of $m$. Write

$$ m=rd. $$

We must prove that $\langle U_n\rangle$ is $(d,k)$-distributed.

Fix real numbers $u_t,v_t$ with $0\le u_t<v_t\le1$ for $1\le t\le k$, and fix an integer $j$ with $0\le j<d$. Let $S(n)$ be the statement

$$ u_1\le U_{dn+j}<v_1,; u_2\le U_{dn+j+1}<v_2,; \dots,; u_k\le U_{dn+j+k-1}<v_k . $$

To show $(d,k)$-distribution, we must prove that

$$ \Pr(S(n)) = (v_1-u_1)\cdots(v_k-u_k). $$

For each $s$ with $0\le s<r$, define $S_s(n)$ by

$$ u_1\le U_{m n+(sd+j)}<v_1,; \dots,; u_k\le U_{m n+(sd+j)+k-1}<v_k . $$

Since the sequence is $(m,k)$-distributed, Definition E gives

$$ \Pr(S_s(n)) = (v_1-u_1)\cdots(v_k-u_k) \qquad(0\le s<r). $$

Let $\nu(N)$ be the number of integers $n$, $0\le n<N$, for which $S(n)$ is true. Likewise let $\nu_s(N)$ count the integers $n$, $0\le n<N$, for which $S_s(n)$ is true.

Every index of the form $dn+j$ belongs to exactly one residue class $sd+j \pmod m$. Hence

$$ \nu(N) = \sum_{s=0}^{r-1}\nu_s!\left(\frac{N}{r}\right)+O(1). $$

Dividing by $N$ and letting $N\to\infty$,

$$ \lim_{N\to\infty}\frac{\nu(N)}{N} = \frac1r \sum_{s=0}^{r-1} \lim_{N\to\infty} \frac{\nu_s(N)}{N}. $$

Using the $(m,k)$-distribution property for each $s$,

$$ \lim_{N\to\infty}\frac{\nu(N)}{N} = \frac1r \sum_{s=0}^{r-1} (v_1-u_1)\cdots(v_k-u_k) = (v_1-u_1)\cdots(v_k-u_k). $$

Therefore

$$ \Pr(S(n)) = (v_1-u_1)\cdots(v_k-u_k). $$

Since this holds for every choice of $u_t,v_t$ and every $j$ with $0\le j<d$, the sequence is $(d,k)$-distributed.

Thus

$$ \boxed{\text{An $(m,k)$-distributed sequence is $(d,k)$-distributed for every divisor } d\mid m.} $$

This completes the proof.

∎