TAOCP 3.5 Exercise 25

Section 3.5: What Is a Random Sequence?

Exercise 25. [**] [HM20] A sequence is called a "white sequence" if all serial correlations are zero; that is, if the equation in Corollary S is true for all $k \ge 1$. (By Corollary S, an $\infty$-distributed sequence is white.) Show that if a ${0..1}$ sequence is equidistributed, it is white if and only if

$$\lim_{n \to \infty} \frac{1}{n} \sum_{0 \le j < n} (U_j - \tfrac{1}{2})(U_{j+k} - \tfrac{1}{2}) = 0, \qquad \text{for all } k \ge 1.$$

Verified: yes
Solve time: 1m02s

Let

$C_k(n)=\frac1n\sum_{0\le j<n}\left(U_j-\frac12\right)\left(U_{j+k}-\frac12\right).$

Since $(U_n)$ is a ${0,1}$ sequence, $U_j^2=U_j$, and

$$ =U_jU_{j+k}-\frac12(U_j+U_{j+k})+\frac14. $$

Because the sequence is equidistributed,

$$ \qquad \lim_{n\to\infty}\frac1n\sum_{0\le j<n}U_{j+k}=\frac12, $$

the second limit following from the fact that deleting or adding finitely many terms does not affect the limiting frequency. Hence

$$= \lim_{n\to\infty}\frac1n\sum_{0\le j<n}U_jU_{j+k} -\frac14.$$

Now $U_jU_{j+k}=1$ exactly when $U_j=U_{j+k}=1$, so

$$$$

is the frequency of the event $U_n=1$ and $U_{n+k}=1$. Therefore

$$$$

if and only if

$$$$

For a binary equidistributed sequence, $\Pr(U_n=1)=\Pr(U_n=0)=\frac12$. Hence

$$ =\frac12-\Pr(U_n=1,\ U_{n+k}=1), $$

and similarly for the other three pairs. Thus the condition

$$$$

holds if and only if each of the four pairs $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ occurs with probability $1/4$. This is exactly the statement that the serial correlation at lag $k$ is zero, namely the equation of Corollary S.

Therefore an equidistributed ${0,1}$ sequence is white if and only if

$$ \lim_{n\to\infty} \frac1n\sum_{0\le j<n} \left(U_j-\frac12\right) \left(U_{j+k}-\frac12\right) =0 \qquad (k\ge1). $$

This completes the proof.

∎