View source for Non-uniform random variate generation

{{Use American English|date = March 2019}}
{{Short description|Generating pseudo-random numbers that follow a probability distribution}}

'''Non-uniform random variate generation''' or '''pseudo-random number sampling''' is the [[Numerical analysis|numerical]] practice of generating [[pseudo-random number]]s (PRN) that follow a given [[probability distribution]].
Methods are typically based on the availability of a [[Uniform distribution (continuous)|uniformly distributed]] [[pseudo-random number generator|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 method|Monte-Carlo simulations]] in the [[Manhattan project]],{{Citation needed|date=June 2011}} published by [[John von Neumann]] in the early 1950s.<ref>{{cite book |chapter=Various Techniques Used in Connection with Random Digits |first=John |last=Von Neumann |authorlink=John von Neumann |year=1951 |editor1=Householder, A. S. |editor2=Forsythe, G. E. |editor3=Germond, H. H. |title=Monte Carlo Methods |series=National Bureau of Standards Applied Mathematics Series |volume=12 |pages=36–38 |publisher=US Government Printing Office |chapter-url=https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf |quote=Any one who considers arithmetical methods of producing random digits is of course, in a state of sin.}}  Also online is a [https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf low-quality scan of the original publication].</ref>

== Finite discrete distributions ==

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 <nowiki>[</nowiki>0,&nbsp;1<nowiki>)</nowiki> is divided in ''n'' intervals [0,&nbsp;''f''(1)), [''f''(1),&nbsp;''f''(1)&nbsp;+&nbsp;''f''(2)),&nbsp;... The width of interval ''i'' equals the probability&nbsp;''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&nbsp;''f''(''i'').

Formalizing this idea becomes easier by using the cumulative distribution function
:<math>F(i)=\sum_{j=1}^i f(j).</math>
It is convenient to set ''F''(0)&nbsp;=&nbsp;0.  The ''n'' intervals are then simply [''F''(0),&nbsp;''F''(1)), [''F''(1),&nbsp;''F''(2)), ..., [''F''(''n''&nbsp;&minus;&nbsp;1),&nbsp;''F''(''n'')). The main computational task is then to determine ''i'' for which ''F''(''i''&nbsp;&minus;&nbsp;1)&nbsp;≤&nbsp;''X''&nbsp;<&nbsp;''F''(''i'').

This can be done by different algorithms:
* [[Linear search]], computational time linear in&nbsp;''n''.
* [[Binary search]], computational time goes with&nbsp;log&nbsp;''n''.
* [[Indexed search]],<ref>Ripley (1987) {{Page needed|date=June 2011}}</ref> also called the ''cutpoint method''.<ref>Fishman (1996) {{Page needed|date=June 2011}}</ref>
* [[Alias method]], computational time is constant, using some pre-computed tables.
* There are other methods that cost constant time.<ref>Fishman (1996) {{Page needed|date=June 2011}}</ref>

== Continuous distributions ==

Generic methods for generating [[statistical independence|independent]] samples:
* [[Rejection sampling]] for arbitrary density functions
* [[Inverse transform sampling]] for distributions whose [[Cumulative distribution function|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 filter]]s, when the observed data is connected in a [[Markov chain]] and should be processed sequentially

For generating a [[normal distribution]]:
* [[Box–Muller transform]]
* [[Marsaglia polar method]]

For generating a [[Poisson distribution]]:
* See [[Poisson distribution#Generating Poisson-distributed random variables]]

== Software libraries ==

[[GNU Scientific Library]] has a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.<ref name="The GNU Operating System and the Free Software Movement">{{cite web | title=Random Number Distributions - GSL 2.7 documentation | website=The GNU Operating System and the Free Software Movement | url=https://www.gnu.org/software/gsl/doc/html/randist.html | access-date=2022-08-18}}</ref>

== See also ==
*[[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 ==
{{reflist}}

== Literature ==

* Devroye, L. (1986) ''[https://www.proquest.com/openview/84d724fc612fbfb1b7c6b7976198e5ff/1?pq-origsite=gscholar&cbl=30748 Non-Uniform Random Variate Generation].'' New York: Springer
* Fishman, G.S. (1996) ''[https://books.google.com/books?id=dogHCAAAQBAJ Monte Carlo. Concepts, Algorithms, and Applications].'' New York: Springer
* Hörmann, W.; J Leydold, G Derflinger (2004,2011) ''[https://books.google.com/books?id=tiTyCAAAQBAJ Automatic Nonuniform Random Variate Generation].'' Berlin: Springer.
* [[Donald Knuth|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.

{{DEFAULTSORT:Pseudo-Random Number Sampling}}
[[Category:Pseudorandom number generators]]
[[Category:Non-uniform random numbers]]