# Random number generator with discrete probability distribution

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

-

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:

-
There is an improvement on the Box-Muller algorithm by George Marsaglia called the Marsaglia Polar Method. However,the Ziggurat algorithm is even more efficient. – robjohn Aug 22 '13 at 21:47

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.

-

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.

-