Non-Uniform Random Variate Generation

Random number generatlon has intrigued sclentists for a few decades, and a lot of effort has been spent on the creation of randomness on a deterministic (non-random) machlne, that is, on the design of computer algorithms that are able to produce ‘random’ sequences of integers.

This is a difficult task. Such algorithms are called generators, and all generators have flaws because all of them construct the n-th number in the sequence in function of the n-1 numbers preceding it, initialized wlth a nonrandom seed. Numerous quantities have been invented over the years that measure just how ‘random’ a sequence is, and most well-known generators have been subjected to rigorous statistical testing. However, for every generator, it is always possible to and a statistical test of a (possibly odd) property to make the generator flunk.

The mathematical tools that are needed to design and analyze these generators are largely number theoretic and combinatorial. These tools differ drastically from those needed when we want to generate sequences of integers with certain non-uniform distributions, given that a perfect uniform random number generator is available. The reader should be aware that we provide him with only half the story (the second half). The assumption that a perfect uniform random number generator is available is now quite unrealistic, but, with time, it should become less so. Having made the assumption, we can build quite a powerful theory of non-uniform random variate generation.