Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

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:

share|improve this answer
1  
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.