Ratio of uniforms
The ratio of uniforms is a method initially proposed by Kinderman and Monahan in 1977 for pseudo-random number sampling, that is, for drawing random samples from a statistical distribution. Like rejection sampling and inverse transform sampling, it is an exact simulation method. The basic idea of the method is to use a change of variables to create a bounded set, which can then be sampled uniformly to generate random variables following the original distribution. One feature of this method is that the distribution to sample is only required to be known up to an unknown multiplicative factor, a common situation in computational statistics and statistical physics. Motivation 

A convenient technique to sample a statistical distribution is rejection sampling. When the probability density function of the distribution is bounded and has finite support, one can define a bounding box around it (a uniform proposal distribution), draw uniform samples in the box and return only the x coordinates of the points that fall below the function (see graph). As a direct consequence of the fundamental theorem of simulation, the returned samples are distributed according to the original distribution. When the support of the distribution is infinite, it is impossible to draw a rectangular bounding box containing the graph of the function. One can still use rejection sampling, but with a non-uniform proposal distribution. It can be delicate to choose an appropriate proposal distribution, and one also has to know how to efficiently sample this proposal distribution. The method of the ratio of uniforms offers a solution to this problem, by essentially using as proposal distribution the distribution created by the ratio of two uniform random variables. Statement 
The statement and the proof are adapted from the presentation by Gobet

Complements

Rejection sampling in  
The above statement does not specify how one should perform the uniform sampling in . However, the interest of this method is that under mild conditions on  (namely that  and  for all  are bounded),  is bounded. One can define the rectangular bounding box  such thatThis allows to sample uniformly the set  by rejection sampling inside . The parameter  can be adjusted to change the shape of  and maximize the acceptance ratio of this sampling. Parametric description of the boundary of  
The definition of  is already convenient for the rejection sampling step. For illustration purposes, it can be interesting to draw the set, in which case it can be useful to know the parametric description of its boundary:or for the common case where  is a 1-dimensional variable, . Generalized ratio of uniforms 

Here parameterized only with , the ratio of uniforms can be described with a more general class of transformations. In the 1-dimensional case, if  is a strictly increasing and differentiable function such that , then we can define  such that

 

If  is a random variable uniformly distributed in , then  is distributed with the density . Examples

The exponential distribution 

Assume that we want to sample the exponential distribution,  with the ratio of uniforms method. We will take here . We can start constructing the set :

 

The condition  is equivalent, after computation, to , which allows us to plot the shape of the set (see graph). This inequality also allows us to determine the rectangular bounding box  where  is included. Indeed, with , we have  and , from where . From here, we can draw pairs of uniform random variables  and  until , and when that happens, we return , which is exponentially distributed. A mixture of normal distributions 

Consider the mixture of two normal distributions . To apply the method of the ratio of uniforms, with a given , one should first determine the boundaries of the rectangular bounding box  enclosing the set . This can be done numerically, by computing the minimum and maximum of  and  on a grid of values of . Then, one can draw uniform samples , only keep those that fall inside the set  and return them as . It is possible to optimize the acceptance ratio by adjusting the value of , as seen on the graphs. Software 

 The rust and Runuran contributed packages in R.

See also 

 Rejection sampling
 Inverse transform sampling

References 

Pseudorandom number generators
Non-uniform random numbers