Non-uniform random variate generation

Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers (PRN) that follow a given probability distribution. Methods are typically based on the availability of a uniformly distributed PRN generator. Computational algorithms are then used to manipulate a single random variate, X, or often several such variates, into a new random variate Y such that these values have the required distribution. The first methods were developed for Monte-Carlo simulations in the Manhattan project,[citation needed] published by John von Neumann in the early 1950s.[1]

Finite discrete distributions

edit

For a discrete probability distribution with a finite number n of indices at which the probability mass function f takes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided in n intervals [0, f(1)), [f(1), f(1) + f(2)), ... The width of interval i equals the probability f(i). One draws a uniformly distributed pseudo-random number X, and searches for the index i of the corresponding interval. The so determined i will have the distribution f(i).

Formalizing this idea becomes easier by using the cumulative distribution function

 

It is convenient to set F(0) = 0. The n intervals are then simply [F(0), F(1)), [F(1), F(2)), ..., [F(n − 1), F(n)). The main computational task is then to determine i for which F(i − 1) ≤ X < F(i).

This can be done by different algorithms:

Continuous distributions

edit

Generic methods for generating independent samples:

Generic methods for generating correlated samples (often necessary for unusually-shaped or high-dimensional distributions):

For generating a normal distribution:

For generating a Poisson distribution:

Software libraries

edit

GNU Scientific Library has a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.[5]

See also

edit

Footnotes

edit
  1. ^ Von Neumann, John (1951). "Various Techniques Used in Connection with Random Digits" (PDF). In Householder, A. S.; Forsythe, G. E.; Germond, H. H. (eds.). Monte Carlo Methods. National Bureau of Standards Applied Mathematics Series. Vol. 12. US Government Printing Office. pp. 36–38. Any one who considers arithmetical methods of producing random digits is of course, in a state of sin. Also online is a low-quality scan of the original publication.
  2. ^ Ripley (1987) [page needed]
  3. ^ Fishman (1996) [page needed]
  4. ^ Fishman (1996) [page needed]
  5. ^ "Random Number Distributions - GSL 2.7 documentation". The GNU Operating System and the Free Software Movement. Retrieved 2022-08-18.

Literature

edit