TAOCP 3.2.2 Exercise 6
In the binary method (10), the contents of $X$ form a shift-register sequence determined by a primitive polynomial modulo $2$.
Exercise 6. [10] In the binary method (10), the text states that the low-order bit of X is random, if the code is performed repeatedly. Why isn't the entire word X random?
Verified: no
Solve time: 2m11s
In the binary method (10), the contents of $X$ form a shift-register sequence determined by a primitive polynomial modulo $2$. If the word has $k$ bits, the nonzero states of $X$ run through a cycle of length $2^k-1$. Thus each individual state occurs exactly once per period, and the next state is completely determined by the present one.
The low-order bit of $X$, observed at successive times, is random in the sense that it passes through the same binary sequence as a maximal-period linear recurrence modulo $2$; over a full period it contains $2^{k-1}$ ones and $2^{k-1}-1$ zeros. But the entire word $X$ is not random, because its bits are highly constrained. At every step, $k-1$ bits of the new word are obtained merely by shifting the old word one position. Hence successive words satisfy fixed linear relations, and only $2^k-1$ of the $2^k$ possible words can ever occur. The state determines its successor uniquely, so consecutive words are far from independent.