How Computers Generate Random Numbers - Chapter 10
The field of Information Theory is where we find a mathematical
understanding of what a random number generator really is. Our ideal
random number generator is a zero-memory information source with
maximum entropy. We think of a source as emitting a sequence of
symbols from a fixed finite set S = {s1, s2, ... sn}. Successive
symbols are selected according to some fixed probability law. For a
zero-memory source, the source remembers nothing about what previous
symbols have been emitted; each successive symbol emitted from the
source is completely independent of all previous output symbols.
Maximum entropy indicates that each symbol in the set S is
equally likely to occur. Any other probability distribution would
result in a lower entropy, with some symbols being more likely than
others. You may recall entropy is also used in thermodynamics to
measure the amount of "randomness" in a particular system.
A linear congruential random number generator is an example of a
first-order Markov process. The next value depends entirely on
the previous value. Even the Data Encryption Standard (DES) is nothing
more than a first-order Markov process. A first-order Markov source
can emulate a zero-memory source up to a point.
A higher order Markov process has a better chance of emulating a
zero-memory process. By shuffling the output, we have converted the
first-order Markov process to something like an Mth-order Markov
process where M is the size of the shuffling deck we use. In this
case M pieces of information about previous outputs are kept instead of
just 1 piece of information. Thus, because of the additional memory
used, the output can resemble more closely that of a zero-memory
source. And indeed it does do a much better job.
For further understanding of zero-memory information sources and Markov
information sources consult a good book on Information Theory. The
book by Abramson in the references below is an excellent one which also
gives an interesting account of how languages such as English, Spanish,
French, and German, can be synthesized using a low order Markov
process. (See The Structure of Language)
