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:
- Linear search, computational time linear in n.
- Binary search, computational time goes with log n.
- Indexed search,[2] also called the cutpoint method.[3]
- Alias method, computational time is constant, using some pre-computed tables.
- There are other methods that cost constant time.[4]
Continuous distributions
[edit]Generic methods for generating independent samples:
- Rejection sampling for arbitrary density functions
- Inverse transform sampling for distributions whose CDF is known
- Ratio of uniforms, combining a change of variables and rejection sampling
- Slice sampling
- Ziggurat algorithm, for monotonically decreasing density functions as well as symmetric unimodal distributions
- Convolution random number generator, not a sampling method in itself: it describes the use of arithmetics on top of one or more existing sampling methods to generate more involved distributions.
Generic methods for generating correlated samples (often necessary for unusually-shaped or high-dimensional distributions):
- Markov chain Monte Carlo, the general principle
- Metropolis–Hastings algorithm
- Gibbs sampling
- Slice sampling
- Reversible-jump Markov chain Monte Carlo, when the number of dimensions is not fixed (e.g. when estimating a mixture model and simultaneously estimating the number of mixture components)
- Particle filters, when the observed data is connected in a Markov chain and should be processed sequentially
For generating a normal distribution:
For generating a Poisson distribution:
Software libraries
[edit]| Distribution | NumPy | GNU Scientific Library[5] |
|---|---|---|
| Beta | Yes | Yes |
| Binomial | Yes | Yes |
| Cauchy | Yes | Yes |
| Chi-squared | Yes | Yes |
| Dirichlet | Yes | Yes |
| Exponential | Yes | Yes |
| F | Yes | Yes |
| Gamma | Yes | Yes |
| Geometric | Yes | Yes |
| Gumbel | Yes | Yes |
| Hypergeometric | Yes | Yes |
| Laplace | Yes | Yes |
| Logistic | Yes | Yes |
| Log-normal | Yes | Yes |
| Logarithmic | Yes | Yes |
| Multinomial | Yes | Yes |
| Multivariate hypergeometric | Yes | No |
| Multivariate normal | Yes | Yes |
| Negative binomial | Yes | Yes |
| Noncentral chi-squared | Yes | No |
| Noncentral F | Yes | No |
| Normal | Yes | Yes |
| Pareto | Yes | Yes |
| Poisson | Yes | Yes |
| Power | Yes | ? |
| Rayleigh | Yes | Yes |
| Students's t | Yes | Yes |
| Triangular | Yes | No |
| von Mises | Yes | No |
| Wald | Yes | No |
| Zeta | Yes | No |
See also
[edit]- Beta distribution#Random variate generation
- Dirichlet distribution#Random variate generation
- Exponential distribution#Random variate generation
- Gamma distribution#Random variate generation
- Geometric distribution#Random variate generation
- Gumbel distribution#Random variate generation
- Laplace distribution#Random variate generation
- Multinomial distribution#Random variate distribution
- Pareto distribution#Random variate generation
- Poisson distribution#Random variate generation
Footnotes
[edit]- ↑ 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. Archived from the original (PDF) on 2022-09-10. Retrieved 2018-04-06.
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. - ↑ Ripley (1987) [page needed]
- ↑ Fishman (1996) [page needed]
- ↑ Fishman (1996) [page needed]
- ↑ "Random Number Distributions - GSL 2.7 documentation". The GNU Operating System and the Free Software Movement. Retrieved 2022-08-18.
Literature
[edit]- Devroye, L. (1986) Non-Uniform Random Variate Generation. New York: Springer
- Fishman, G.S. (1996) Monte Carlo. Concepts, Algorithms, and Applications. New York: Springer
- Hörmann, W.; J Leydold, G Derflinger (2004,2011) Automatic Nonuniform Random Variate Generation. Berlin: Springer.
- Knuth, D.E. (1997) The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, Chapter 3.4.1 (3rd edition).
- Ripley, B.D. (1987) Stochastic Simulation. Wiley.