TAOCP 3.5 Exercise 22

Section 3.5: What Is a Random Sequence?

Exercise 22. ▶ [**] [HM30] (Hermann Weyl.) Show that the $[0,..,1)$ sequence $(U_n)$ is $k$-distributed if and only if

$$\lim_{N \to \infty} \frac{1}{N} \sum_{0 \le n < N} \exp(2\pi i (c_1 U_n + \cdots + c_k U_{n+k-1})) = 0$$

for every set of integers $c_1, c_2, \ldots, c_k$ not all zero.

Verified: yes
Solve time: 1m01s

Suppose $(U_n)$ is $k$-distributed. By Definition B, for any $k$-tuple of intervals $[u_j, v_j)$ we have

$\lim_{N \to \infty} \frac{1}{N} \sum_{0 \le n < N} \mathbf{1}{[u_1, v_1)}(U_n) \cdots \mathbf{1}{[u_k, v_k)}(U_{n+k-1}) = \prod_{j=1}^{k} (v_j - u_j).$

Each exponential term $\exp(2\pi i (c_1 U_n + \cdots + c_k U_{n+k-1}))$ can be expressed as a linear combination of indicator functions of intervals with rational endpoints. Since $(U_n)$ is $k$-distributed, the average of each such indicator converges to the measure of the corresponding interval. Therefore, for any integers $c_1, \ldots, c_k$ not all zero, the limit

$\lim_{N \to \infty} \frac{1}{N} \sum_{0 \le n < N} \exp(2\pi i (c_1 U_n + \cdots + c_k U_{n+k-1}))$

must vanish, because the integral of a nontrivial character over $[0,1)^k$ is zero. Conversely, if the above limit is zero for all such integer vectors $(c_1, \ldots, c_k)$, then for any Riemann-integrable function $f$ on $[0,1)^k$, the usual Fourier series argument shows that

$\lim_{N \to \infty} \frac{1}{N} \sum_{0 \le n < N} f(U_n, \ldots, U_{n+k-1}) = \int_0^1 \cdots \int_0^1 f(x_1, \ldots, x_k), dx_1 \cdots dx_k.$

Applying this to the indicator function of any $k$-dimensional rectangle $[u_1, v_1) \times \cdots \times [u_k, v_k)$ yields exactly the $k$-distribution property. This completes the proof.

∎