TAOCP 3.1 Exercise 5
Algorithm K, as described in Section 3.
Exercise 5. [15] Explain why, in any case, Algorithm K should not be expected to provide infinitely many random numbers, in the sense that (even if the coincidence given in Table 1 had not occurred) one knows in advance that any sequence generated by Algorithm K will eventually be periodic.
Verified: yes
Solve time: 1m03s
Solution
Algorithm K, as described in Section 3.1, generates a sequence of numbers deterministically by performing arithmetic operations on a current state $X$ to produce the next number in the sequence. Each value $X_n$ in the sequence is obtained from the preceding value $X_{n-1}$ by a fixed function $f$, say
$X_n = f(X_{n-1}).$
Since $f$ is a function from a finite set of possible $X$ values to itself, the sequence $(X_0, X_1, X_2, \dots)$ is a sequence in a finite set. Let $M$ denote the number of distinct states that $X$ can take, which is finite because $X$ is represented with a fixed number of decimal or binary digits. By the pigeonhole principle, after at most $M+1$ iterations, there must exist integers $i < j \le M$ such that $X_i = X_j$.
Once $X_i = X_j$, the sequence from $X_i$ onward repeats with period $j-i$, because the function $f$ is deterministic:
$X_{i+1} = f(X_i) = f(X_j) = X_{j+1}, \quad X_{i+2} = f(X_{i+1}) = X_{j+2}, \quad \text{and so on}.$
Hence the sequence is ultimately periodic. The argument does not depend on any particular numerical coincidences, such as those given in Table 1, and applies to any starting value $X_0$.
It follows that Algorithm K cannot produce infinitely many distinct random numbers. Even if the sequence initially appears random, it must eventually enter a cycle and repeat values indefinitely. Therefore, in the sense of generating truly nonrepeating random numbers, Algorithm K is fundamentally limited by the finiteness of the state space and the deterministic nature of its recurrence function.
This completes the proof.
∎