Random number generator with discrete probability distribution

Question

Is there a general algorithm for implementing a PRNG with a probability distribution?

Answer 1

Use the Mersenne Twister (https://en.wikipedia.org/wiki/Mersenne_twister) to generate uniformly distributed random numbers first. It has a very long period and other great properties. Alternatively, you could use another uniformly distributed random number generator instead.

Suppose now you have generated a random number $x$ this way and that the probability density you want to sample from is $\phi$. You need to find $y$ s.t. $$ x=\int_{-\infty}^{y}\phi\left(s\right)ds. $$ In other words, if $\Phi$ is the cumulative distribution, you need to find $$ y=\Phi^{-1}\left(x\right). $$ There are special cases in which you can make very fast algorithms to do this. For example, for normally distributed random numbers, there exists two methods:

• Box-Muller: https://en.wikipedia.org/wiki/Box_muller
• Ziggurat (arguably better): https://en.wikipedia.org/wiki/Ziggurat_algorithm

Answer 2

I presume you are talking about sampling a non-uniform discrete random variable.

The general method for univariate random variables is the inverse transform sampling.

Alternatively, one can use a rejection method.

For certain classes of univariate probability mass functions one can automatically build a hat distribution. See the book "Automatic non-uniform random variate generation"

Also the book by J.E. Gentle "Random Number Generation and Monte Carlo Methods" contains many algorithms for standard discrete distributions.

I would be amiss if I did not mention the freely available monograph by L. Devroye "Non-uniform random number generation".

Hope this helps.

Answer 3

One of the best resources for random variate generation is Luc Devroye's book Non-Uniform Random Variate Generation which he provides for free as a set of PDFs here.