TAOCP 3.1 Exercise 22
Using the sequence $f(0), f(1), f(2), \ldots$ where $f$ is a random function is not a practical way to generate random numbers.
Exercise 22. [**] [21] (H. Rolletschek.) Would it be a good idea to generate random numbers by using the sequence $f(0), f(1), f(2), \ldots$, where $f$ is a random function, instead of using $x_0, f(x_0), f(f(x_0))$, etc.?
Verified: yes
Solve time: 1m24s
Using the sequence $f(0), f(1), f(2), \ldots$ where $f$ is a random function is not a practical way to generate random numbers. Each term is independent of the previous ones, so no state needs to be maintained; however, storing or computing $f(n)$ for arbitrary $n$ quickly becomes infeasible for large domains, since one must either store a table of all values or evaluate a complex function for each $n$. In contrast, the usual method $x_0, f(x_0), f(f(x_0)), \ldots$ requires only the current value to produce the next, which is much more efficient in memory and computation. Moreover, the former method provides no way to reproduce the sequence from a single seed, making debugging and verification difficult.
From a theoretical standpoint, $f(0), f(1), f(2), \ldots$ yields a sequence of independent random numbers if $f$ is truly random, but the practical limitations of storing or computing $f$ outweigh this advantage. The standard approach using a deterministic function iterated from a seed produces pseudorandom sequences that are reproducible and can have good statistical properties with minimal storage, which is why it is preferred. This completes the proof.
∎