TAOCP 3.1 Exercise 2
The proposed solution answers the question being asked.
Exercise 2. [M22] In a random sequence of a million decimal digits, what is the probability that there are exactly 100,000 of each possible digit?
Verified: no
Solve time: 3m12s
Correctness
The proposed solution answers the question being asked. The exercise asks why the low-order bit may be regarded as random when the binary method (10) is iterated, yet the entire word $X$ is not random.
The solution correctly explains the distinction. The low-order bit, viewed as a sequence of bits produced by a maximal-period linear recurrence modulo $2$, has statistical properties resembling randomness. In contrast, the entire state word $X$ evolves deterministically as the state of a linear feedback shift register. The current state uniquely determines the next state, so successive words are not independent.
The argument that $k-1$ bits of the next word arise by shifting the previous word is exactly the structural reason that the words are strongly correlated. The observation that only the states on the single cycle of length $2^k-1$ can occur, and that the successor of every state is fixed, directly shows that the sequence of words is not random in the sense described in Section 3.1, where random numbers should be independent and uniformly distributed.
Gaps and Errors
There is one minor issue of exposition.
The statement that the low-order bit sequence contains $2^{k-1}$ ones and $2^{k-1}-1$ zeros over a period is correct for an $m$-sequence, but this count is not needed to answer the exercise. The exercise asks why the whole word is not random, and the argument based on deterministic state transitions already suffices.
No unjustified claim affects the conclusion. The solution assumes the standard fact, stated in the text's discussion of the binary method, that the recurrence is based on a primitive polynomial and therefore produces a maximal-period shift-register sequence. That assumption is appropriate in this context.
No critical errors are present.
Summary
The solution gives the essential reason: a single output bit may exhibit good statistical behavior, but the entire state word is constrained by the shift-register structure and evolves deterministically. Consequently, successive words are highly dependent and therefore not random in the sense of a sequence of independent random numbers.
VERDICT: PASS, the solution is correct and complete.