Automatic sampling with the ratio-of-uniforms method.
Applying the ratio-of-uniforms method for generating random variates results in very efficient, fast, and easy-to-implement algorithms. However parameters for every particular type of density must be precalculated analytically. In this article we show, that the ratio-of-uniforms method is also useful for the design of a black-box algorithm suitable for a large class of distributions, including all with log-concave densities. Using polygonal envelopes and squeezes results in an algorithm that is extremely fast. In opposition to any other ratio-of-uniforms algorithm the expected number of uniform random numbers is less than two. Furthermore, we show that this method is in some sense equivalent to transformed density rejection.
Introduction
There exists a large literature on generation methods for standard continuous
distributions; see, for example, Devroye (1986). These algorithms are often especially
designed for a particular distribution and tailored to the features of each
density. However in many situations the application of standard distributions is not
adequate for a Monte-Carlo simulation. Besides sheer brute force inversion (that
is, tabulate the distribution function at many points), several universal methods
for large classes of distributions has been developed to avoid the design of special
algorithms for these cases. Some of these methods are either very slow (e.g. Devroye
(1984)) or need a slow set-up step and large tables (e.g. Ahrens and Kohrt (1981),
Marsaglia and Tsang (1984), and Devroye (1986, chap. VII)).
Recently two more efficient methods have been proposed. The transformed
density rejection by Gilks and Wild (1992) and H-ormann (1995) is an accep-
tance/rejection technique that uses the concavity of the transformed density to
generate a hat function automatically. The user only needs to provide the probability
density function and perhaps the (approximate) location of the mode. A
table method by Ahrens (1995) also is an acceptance/rejection method, but uses a
piecewise constant hat such that the area below each piece is the same. A region of
immediate acceptance makes the algorithm fast when a large number of constant
pieces is used. The tail region of the distribution is treated separately.
The ratio-of-uniforms method introduced by Kinderman and Monahan (1977)
is another flexible method that can be adjusted to a large variety of distributions.
It has become a popular transformation method to generate non-uniform random
variates, since it results in exact, efficient, fast and easy to implement algorithms.
Typically these algorithms have only a few lines of code (e.g. Barabesi (1993) gives
a survey and examples of FORTRAN codes for several standard distributions). It
is based on the following theorem.
1991 Mathematics Subject Classification. Primary: 65C10 random number generation, Sec-
ondary: 65U05 Numerical methods in probability and statistics; 11K45 Pseudo-random numbers,
Monte Carlo methods.
Key words and phrases. non-uniform random variates, ratio-of-uniforms, universal method,
adaptive method, patchwork rejection, continuous distributions, log-concave distributions,
concave distributions, transformed density rejection.
Theorem 1 (Kinderman and Monahan 1977). Let X be a random variable with
density function
R
g(x)dx, where g(x) is a positive integrable function
with support necessarily finite. If (V; U) is uniformly distributed in
For sampling random points uniformly distributed in A g rejection from a convenient
enveloping region R g is used. The basic form of the ratio-of-uniforms method
is given by algorithm rou.
Algorithm rou
Require: density f(x); enveloping region R
1: repeat
2: Generate random point (V; U) uniformly distributed in R.
3: X / V=U .
4: until U 2 - f(X).
5: return X .
Usually the input in rou is prepared by the designer of the algorithm for each
particular distribution. To reduce the number of evaluations of the density function
in step 4, squeezes are used. It is obvious that the performance of this simple
algorithm depends on the rejection constant, i.e. on the ration jRj=jAj, where jRj
denotes the area of region R. Kinderman and Monahan (1977) and others use
rejection from the minimal bounding rectangle, i.e. the smallest possible rectangle
g. This basic algorithm has been improved in several
fitting enclosing region decreases the rejection constant. Possible
choices are parallelograms (e.g. Cheng and Feast (1979)) or quadratic bounding
curves (e.g. Leva (1992)). Often it is convenient to decompose A into a countable
set of non-overlapping subregions ("composite ratio-of-uniforms method", Robertson
and Walls (1980) give a simple example). Dagpunar (1988, p. 65) considers the
possibility of an enclosing polygon.
In this paper we develop a new algorithm that uses polygonal envelopes and
squeezes. Random variates inside the squeeze are generated by mere inversion and
therefore in opposite to any other ratio-of-uniforms method less than two uniform
random numbers are required. For a large class of distributions, including all log-concave
distributions, it is possible to construct envelope and squeeze automatically.
Moreover we show that the new algorithm is in some sense equivalent to transformed
density rejection.
The new method has several advantages:
ffl Envelopes and squeezes are constructed automatically. Only the probability density
function is necessary.
Only random numbers are necessary, where % ? 0 can be made arbitrarily
small.
ffl For small % the method is close to inversion and thus the resulting random variates
can be used for variance reduction techniques. Moreover the structure of the
resulting random variates is similar to the that of the underlying random uniform
random number generator. Hence the non-uniform random variates inherit its
quality properties.
1 Moreover the method has been extended: Wakefield, Gelfand, and Smith (1991) replaces the
function by a more general strictly increasing differentiable function q(u).
Stadlober (1989, 1990) gives a modification for discrete distributions.
Jones and Lunn (1996) embeds this method into a "general random variate generation framework".
Wakefield et al. (1991) and Stef-anescu and V-aduva (1987) apply this method to the generation
of multivariate distributions.
ffl It avoids some possible defects in the quality of the resulting pseudo-random
variates that have been reported for the ratio-of-uniforms method (see H-ormann
1994a; H-ormann 1994b).
ffl It is the first ratio-of-uniforms method and the first implementation of transformed
density rejection that requires less than two random numbers.
In section 2 we give an outline of this new approach and in section 4 we discuss
the problem of getting a proper envelope for the region R. Section 5 describes
the algorithm in detail. Section 3 shows that this algorithm is applicable for all T -
concave densities, with T
x. Remarks on the quality of random numbers
generated with the new algorithm are given in section 6.
2. The method
Enveloping polygons. We are given a distribution with probability density function
R
g(x)dx with convex set A g . Notice that g must be continuous
and bounded since otherwise A g were not convex. To simplify the development
of our method we first assume unbounded support for g. (This restriction will be
dropped later.)
For such a distribution it is easy to make an enveloping polygon: Select a couple
of points c i , the boundary of A and use the tangents at these
points as edges of the enclosing polygon P e (see figure 1). We denote the vertices
of P e by m i . These are simply the intersection points of the tangents. Obviously
our choice of the construction points of the tangents has to result in a bounded
polygon P e . The procedure even works if the tangents are not unique for a point
(v; u), i.e. if g(x) is not differentiable in Furthermore it is very simple to
construct squeezes: Take the inside of the polygon P s with vertices c i .
construction points
tangent

Figure

1. Polygonal envelope and squeeze for convex set A g .
Sampling from the enveloping polygon. Notice that the origin (0; 0) is always
contained in the polygon P e . Moreover every straight line through the origin
corresponds to an thus its intersection with A is always connected.
Therefore we use c for the first construction point and the v-axis as its
tangent. To sample uniformly from the enclosing polygon we triangulate P e and
making segments S i , illustrates the
situation. Segment S i has the vertices c 0 , c for the
last segment. Each segment is divided into the triangle S s
inside the squeeze (dark
Sn

Figure

2. Triangulation of enveloping polygon
shaded) and a triangle S
outside (light shaded). Notice that the segments S 0 and
Sn have only three vertices and no triangles S s
0 and S s
n .
To generate a random point uniformly distributed in P e , we first have to sample
from the discrete distribution with probability vector proportional to (jS 0 j; jS 1 j;
to select a segment and further a triangle S
i or S s
i . This can be done by
Algorithm get segment
Require: list of segments
1: Generate R - U(0; 1).
2: Find the smallest k, such that
i-k
3: if P
4: return triangle S s
k .
5: else
return triangle S
k .
For step 2 indexed search (or guide tables) is an appropriate method (Chen and
Asau (1974), see also Devroye (1986, xIII.2.4)).
Uniformly distributed points in a triangle (v can be generated by the
following simple algorithm (Devroye 1986, p. 570):
Algorithm triangle
Require: triangle (v
1: Generate R 1
2: if R 1
3: return (1
For sampling from S s
this algorithm can be much improved. Every point in such
a triangle can immediately be accepted without evaluating the probability density
function and thus we are only interested in the ratio of the components. Since the
i has vertex c we arrive at
(R
(R
where c i;j is the j-th component of vertex c i , and R again is a (0; 1)-
uniform random variate by the ration-of-uniforms theorem, since 0 - R 2
(Kinderman and Monahan 1977). Notice that we save one uniform random number
in the domain P s by this method. Furthermore we can reuse the random number
R from routine get segment by R
risk. We
find
i-k
i-k
Sampling from P s can then be seen as inversion from the cumulated distribution
function defined by the boundary of the squeeze polygon. Thus for a ratio jP s j=jP e j
close to 1 we have almost inversion for generating random variates. The inversion
method has two advantages and is thus favored by the simulation community (see
Bratley, Fox, and Schrage (1983)): (1) The structure of the generator is simple and
can easily be investigated (see section 6). (2) These random variates can be used
for variance reduction techniques.
Expected number of uniform random numbers. Let
j. Then we need (1
for generating one ratio v=u. Since we have to reject this ratio if (v; u) 62 A and
we find for the expected number of uniform random numbers per generated
non-uniform Notice that by a proper choice of the
construction points, % can be made arbitrarily small.
Bounded domain for g. If x than the situation is nearly the
same. We have to distinguish between two cases:
exists for the limit point x i . We then use x i as construction
point and the respective triangular segment S 0 or Sn is not necessary.
(2) Otherwise we can restrict the triangular segment S 0 or Sn , i.e. we use the
tangent line instead of the v-axis. Notice
that we then have different tangent lines at c 0 for S 0 and Sn .
Adding a construction point. To add a new point for a given ratio
we need (c on the "outer boundary" of A and the tangent line of A at this
point. These are given by positive root of u and the total differential of
tangent: a
where a
3. Ratio-of-uniforms and transformed density rejection
Transformed density rejection. One of the most efficient universal methods is
transformed density rejection, introduced in Devroye (1986) and under a different
name in Gilks and Wild (1992), and generalized in H-ormann (1995). This accep-
tance/rejection technique uses the concavity of the transformed density to generate
a hat function and squeezes automatically by means of tangents and secants. The
user only needs to provide the density function and perhaps the (approximate) location
of the mode. It can be utilized for any density f where a strictly increasing,
differentiable transformation T exists, such that T (f(x)) is concave (see H-ormann
(1995) for details). Such a density is called log-concave densities are an
example with T log(x). Figure 3 illustrates the situation for the standard normal
distribution and the transformation T log(x). The left hand side shows
the transformed density with three tangents. The right hand side shows the density
function with the resulting hat. Squeezes are drawn as dashed lines. Evans and
Swartz (1998) has shown that this technique is even suitable for arbitrary densities
provided that the inflection points of the transformed density are known.
6 JOSEF LEYDOLD

Figure

3. Construction of a hat function for the normal density
utilizing transformed density rejection.
Densities with convex region A. Stadlober (1989) and Dieter (1989) have
clarified the relationship of the ratio-of-uniforms method to the ordinary accep-
tance/rejection method. But there is also a deeper connection to the transformed
density rejection, that gives us a useful characterization for densities with convex
region A g . We first provide a proof of theorem 1.
Proof of theorem 1. Consider the transformation
R \Theta (0; 1)
Since the Jacobian of this transformation is 2, the joint density probability function
of X and Y is given by w(x;
otherwise. Thus X has marginal density w 1
R g(x)
Consequently
R
g(x)dx and w 1
probability density function f(x).
Transformation (5) maps A g one-to-one onto B
i.e. the set of points between the graph of g(x) and the x-axis. Moreover
the "outer boundary" of A g , f(v; u) :
mapped onto the graph of g(x).
Theorem 2. A g is convex if and only if g(x) is T -concave with transformation
x.
Proof. Since
x is strictly monotonically increasing, the transformation
one-to-one onto C
i.e. the region below the transformed density. Hence by T
R \Theta (0; 1)
maps A g one-to-one onto C g . Notice that g is T -concave if and only if C g is con-
vex. Thus it remains to show that A g is convex if and only if C g is convex, and
consequently that straight lines remain straight lines under transformation (6).
Let a x+b y = d be a straight line in C g . Then a
i.e. a straight line in A g . Analogously we find for a straight line a
the line a x .
Remark 3. By theorem 2 the new universal ratio-of-uniforms method is in some
sense equivalent to transformed density rejection. It is a different method to generate
points uniformly distributed in the region below the hat function. But in
opposite to the new method transformed density rejection always needs more than
two uniform random numbers. A similar approach for the transform density re-
jection, i.e. decomposing the hat function into the squeeze (region of immediate
acceptance) and the region between squeeze and hat, does not work well. Sampling
from the second part is very awkward and prone to numerical errors (H-ormann
1999).
Since every log-concave density is T -concave with T
x (H-ormann
1995), our algorithm can be applied to a large class of distributions. Examples are
given in table 1. The given conditions on the parameters imply T -concavity on the
support of the densities. However the densities are T -concave for a wider range
of their parameters on a subset of their support. E.g. the density of the gamma
distribution with -concave for all a ? 0 and x -
Distribution Density Support T -concave for
Normal e \Gammax 2 =2 R
Log-normal 1=x exp(\Gamma
pExponential - e \Gamma- x [0;
Beta x
Weibull x
Perks 1=(e x
Gen. inv. Gaussian x
Pearson VI x
Planck x a =(e
Burr x
Snedecor's F x

Table

1. T -concave densities (normalization constants omitted)
4. Construction points
The performance of the new algorithm depends on a small ratio of
and thus on the choice of the constructions points for the tangents of
the enveloping polygon. There are three possible solutions: (1) simply choose
equidistributed points, (2) use an adaptive method, or (3) use optimal points. It
is obvious that setup time is increasing and marginal generation time is decreasing
from (1) to (3) for a given number of construction points.
Equidistributed points. The simplest method is to choose points x
equidistributed angles:
If the density function has bounded domain, (7) has to be modified to
where tan(' l ) and tan(' r ) are the left and right boundary of the domain (see also
section 2).
Numerical simulations with several density functions have shown that this is an
acceptable good choice for construction points for several distributions where the
ratio of length and width of the minimal bounding rectangle is not too far from
one.
Adaptive rejection sampling. Gilks and Wild (1992) introduces the ingenious
concept of adaptive rejection sampling for the problem of finding appropriate construction
points for the tangents for the transformed density rejection method.
Adopted to our situation it works in the following way: Start with (at least) two
points on both sides of the mode and sample points from the enveloping polygon
P e . Add a new construction point at
stopping criterion is fulfilled, e.g. the maximal number of
construction points or the aimed ratio jP s j=jP e j is reached. To ensure that the
starting polygon P e is bounded, a construction point at (or at least close to) the
mode should be used as a third starting point.
Sampling a point in the domain P e n P s is much more expensive than sampling
from the squeeze region. Firstly the generation of a random point requires more
random numbers and multiplications; secondly we have to evaluate the density
and check the acceptance condition. Thus we have to minimize the ratio
which is done perfectly well by adaptive rejection sample, since by
this method the region A is automatically approximated by envelope and squeeze
polygon. The probability for adding a new point in a segment S i depends on
the ratio jS
i.e. from the probability to fall into S
. Hence the adaptive
algorithm tends to insert a new construction point where it is "more necessary".
Obviously the ratio %n is a random variable that converges to 0 almost surely
when the number construction points n tends to infinity. A simple consideration
(Leydold and H-ormann 1998). Figure 4 shows the result of a
simulation for the standard normal distribution with (non optimal) starting points
at samples). %n is plotted against the number n of construction
points. The range of %n is given by the light shaded area, 90%- and 50%-percentiles
are given by dark shaded areas, median by the solid line.
1:0

Figure

4. Convergence of the ratio for the
standard normal distribution with starting points at
(50 000 samples)
We have run simulations with other distributions and starting values and have
made the observation that convergence is even faster for other (non-normal) dis-
tributions. However analytical investigations are interesting. Upper bounds for
expected value of %n are an open problem.
Optimal construction points. By theorem 2 the area between hat and squeeze
of the transformed density rejection method is mapped one-to-one and onto the
AUTOMATIC SAMPLING WITH THE RATIO-OF-UNIFORMS METHOD 9
Thus we can use methods for computing optimal construction points for
transformed density rejection for finding optimal envelopes for the new algorithm.
If only three construction points are used, see H-ormann (1995). If more points are
required, Derflinger and H-ormann (1998) describe a very efficient method. However
some modification are necessary. Improvements over adaptive rejection sampling
are rather small and can be seen in figure 4 (The lower boundary of the range gives
a good estimate for the optimal choice of construction points.
5. The Algorithm
Algorithm arou consists of three main parts:
(1) Construct the starting enveloping polygon P e and squeeze polygon P s in routine
arou start. Here we have to take care about a possibly bounded domain
and the two cases described in section 2. The starting points must be provided
(e.g. by using equidistributed points as describes in section 4).
(2) Sample from the given distribution in routine arou sample.
(3) Add a new construction point with routine arou add whenever we fall into
We store the envelope into a list of segments (object 1). When using this algorithm
we first have to initialize the generator by calling arou start. Then sampling can
be done by calling arou sample.
object 1 segment
parameter variable definition / remark
left construction point c i
right construction point c i+1 pointer, stored in next segment
tangent at left point a
tangent at right point a i+1 pointer, stored in next segment
intersection point m i
area inside/outside squeeze A in
, A out
accumulated area A cum
fast inversion
Algorithm arou start
Require: density f(x), derivative f 0 (x);
domain
2: a 0 / (cos(arctan(x tangent line for So
3: a k+1 / (cos(arctan(x k tangent line for S k
4: for
5: if f(x
7: a i;v / \Gammaf 0
8: add S i to list of segments.
cannot be used as construction point
9: for all segments S i do
10: insert c i+1 and a i+1 . =  already stored in next segment in list
12: compute A in
i and A cum
13: check if polygon P e is bounded.
14: return list of segments.
Algorithm arou sample
Require: density f(x), list of segments S i .
1: loop
2: generate R - U(0; 1).
3: find smallest i such that A cum
use guide table
4: R / A cum
5: if R - A in
return
7:
9: generate R 2 - U(0; 1).
10: if R 1
14: if number of segments ! maximum then
15: call arou add with X , S i .
17: return X .
Algorithm arou add
Require: density f(x), derivative f 0 (x); new construction point xn ; segment S r .
1: if f(xn
cannot add this point
2: return
3: c n;2 /
4: a n;v / \Gammaf 0
5: insert Sn into list of segments. =  Take care about c i+1 and a
remove old segment S r from list.
7: compute mn .
8: compute A in
and A out
9: for all segments S i do
10: compute A cum
11: return new list of segments.
To implement this algorithm, a linked list of segments is necessary. Whenever
A cum
are (re-)calculated, a guide table has to be made. Using linear search might
be a good method for finding S i when only a few random variates are sampled.
Special care is necessary when m i is computed in arou start and arou add.
There are three possible cases for numerical problems when solving the corresponding
linear equation:
(1) The vertices c i and c i+1 are very close and (consequently) jS i j is very small.
Here we simply reject c i+1 as new construction point.
are very close to c very small.
(3) The boundary of A between c i and c i+1 is almost a straight line and A out
is
(almost) 0. In this case we set m
A possible way to define "very small" is to compare such numbers with the smallest
positive " with (M in the used programming language. M denotes the
magnitude of the maximum of the density function. (In ANSI C for
defined by the macro DBL EPSILON.)
It is important to check whether m i is on the outer side of the secant through
c i and c i+1 . This condition is violated in arou start when the polygon P e is
unbounded. It may be violated in arou start and arou add when A is not convex.
A C implementation. A test version of algorithm arou is coded in C and available
by anonymous ftp (Leydold 1999) or by email request from the author.
6. A note on the quality of random numbers
The new algorithm is a composition method, similar to the acceptance-complement
method (see Devroye (1986, x II.5)). We have
s (x) is the distribution defined by the squeeze region and g
By theorem 1 the algorithm is exact, i.e. the generated random variates have the
required distribution. However defects in underlying uniform random number generators
may result in poor quality of the non-uniform random variate. Moreover
the transformation into the non-uniform random variate itself may cause further
deficiencies.
Although there is only little literature on this topic, the ratio-of-uniforms method
in combination with any linear congruental generator (LCG) was reported to have
defects (H-ormann 1994a; H-ormann 1994b). Due to the lattice structure of random
pairs generated by an LCG there is always a hole without a point with probability
of order 1=
is the modulus of the LCG.
Random variates generated by the inversion inherit the structure of the underlying
uniform random numbers and consequently their quality. We consider this
as a great advantage of this method, since generators whose structural properties
are well understood and precisely described may look less random, but those that
are more complicated and less understood are not necessarily better. They may
hide strong correlations or other important defects. should avoid generators
without convincing theoretical support. This statement by L'Ecuyer (1998) on
building uniform random number generator is also valid for non-uniform distribu-
tions. Other methods may have some hidden inferences, which make a prediction
of the quality of the resulting non-uniform random numbers impossible (Leydold,
Leeb, and H-ormann 1999).
Notice that a random variate with density g s (x) is generated by inversion. Thus
as ratio % tends to 0, most of the random variates are generated by inversion by the
new algorithm. As an immediate consequence for small % the new generator avoids
the defects of the basic ratio-of-uniforms method. Figure 5 shows scatter plots
of all overlapping tuples using the "baby" generator
(a) shows the underlying generator. (b)-(f) show
the tuples (\Phi(u 0 different number
of construction points using the equidistribution method (\Phi denotes the cumulated
distribution function of the standard normal distribution).
We have made an empirical investigation using M-Tupel tests (Good 1953;
Marsaglia 1985) in the setup of Leydold, Leeb, and H-ormann (1999) with the standard
normal distribution and various numbers of construction points. We have
used a linear congruential generator fish by Fishman and Moore (1986), an explicit
inversive congruential generator (Eichenauer-Herrmann 1993), and a twisted
GFSR generator (tt800 by Matsumoto and Kurita (1994)); at last the infamous
randu (again an LCG) as an example of a generator with bad lattice structure (see
Park and Miller (1988)). These tests have demonstrated that for small ratio %,
the quality of the normal generators are strongly correlated with the quality of the
underlying uniform random number generator. Especially, using randu results in
normal generator of bad quality. Notice however that this correlation does not exist,
if % is not close to 0. Indeed, using only 2 or 4 construction points results in a normal
generator which might be better (e.g. fish in our tests) or worse (e.g. randu)
than the underlying generator.
(a) uniform (b)
(c) r

Figure

5. Scatter plots of "baby" generator
mod 1024 (a) and of normal variates using algorithm arou with 2,
4, 6, 29 and 75 equidistributed construction points (b-f).
7. Possible Variants
Non-convex region. The algorithm can be modified to work with non-convex
region A f . Adapting the idea of Evans and Swartz (1998) we have to partition A f
into segments using the inflection points of the transformed density with transformation
x. In each segment of A f where T (f(x)) is not concave, we
have to use secants for the boundary of the enveloping polygon P e and tangents for
the squeeze P s . Notice that the squeeze region in such a segment is a quadrangle
and has to be triangulated.
Multivariate distributions. Wakefield, Gelfand, and Smith (1991) and Stef-anescu
and V-aduva (1987) have generalized the ratio-of-uniforms method to multivariate
distributions. Both use rejection from an enclosing multidimensional rectangle.
However the acceptance probability decreases very fast for higher dimension. For
multivariate normal distribution in four dimension it is below 1%. Using polyhedral
envelopes similar to Leydold and H-ormann (1998) or Leydold (1998) is possible
and increases the acceptance probability. However this requires some additional re-search

Acknowledgements

The author wishes to thank Hannes Leeb for helpful discussions on the quality
of random number generators.



--R


Computer methods for efficient sampling from largely arbitrary statistical distributions.
Random variate generation by using the ratio-of-uniforms method
A Guide to Simulation.
On generating random variates from an empirical distribution.
Some simple gamma variate generators.

Principles of Random Variate Generation.
The optimal selection of hat functions for rejection algorithms.
A simple algorithm for generating random variates with a log-concave density

Mathematical aspects of various methods for sampling from classical distributions.
Statistical independence of a new class of inversive congruential pseudorandom numbers.
Random variable generation using concavity properties of transformed densities.

see erratum
Adaptive rejection sampling for Gibbs sampling.
Applied Statistics
The serial test for sampling numbers and other tests for randomness.


A rejection technique for sampling from T-concave distri- butions
private communication.
Transformations and random variate gen- eration: Generalised ratio-of-uniforms methods
Computer generation of random variables using the ratio of uniform deviates.
Random number generation.
A fast normal random number generator.
A rejection technique for sampling from log-concave multi-variate distributions
AROU user manual.
A sweep-plane algorithm for generating random tuples in simple polytopes
Higher dimensional properties of non-uniform pseudo-random variates
A current view of random number generators.


Twisted GFSR generators II.
Random number generators: good ones are hard to find.
Random number generation for the normal and gamma distributions using the ratio of uniforms method.

The ratio of uniforms approach for generating discrete random variates.
On computer generation of random vectors by transformations of uniformly distributed vectors.
Efficient generation of random variates via the ratio-of-uniforms method
University of Economics and Business Administration
--TR
An exhaustive analysis of multiplicative congruential random number generators with modulus 2<supscrpt>31</>-1
A guide to simulation (2nd ed.)
On computer generation of random vectors by transformation of uniformly distributed vectors
Random number generators: good ones are hard to find
Mathematical aspects of various methods for sampling from classical distributions
The ratio of uniforms approach for generating discrete random variates
A fast normal random number generator
A note on the quality of random variates generated by the ratio of uniforms method
Twisted GFSR generators II
A rejection technique for sampling from <italic>T</italic>-concave distributions
A rejection technique for sampling from log-concave multivariate distributions
A sweep-plane algorithm for generating random tuples in simple polytopes
Computer Generation of Random Variables Using the Ratio of Uniform Deviates

--CTR
Leydold , Gerhard Derflinger , Gnter Tirler , Wolfgang Hrmann, An automatic code generator for nonuniform random variate generation, Mathematics and Computers in Simulation, v.62 n.3-6, p.405-412, 3 March
John T. Kent , Patrick D. L. Constable , Fikret Er, Simulation for the complex Bingham distribution, Statistics and Computing, v.14 n.1, p.53-57, January 2004
Josef Leydold, Short universal generators via generalized ratio-of-uniforms method, Mathematics of Computation, v.72 n.243, p.1453-1471, July
Josef Leydold, A simple universal generator for continuous and discrete univariate T-concave distributions, ACM Transactions on Mathematical Software (TOMS), v.27 n.1, p.66-82, March 2001
Wolfgang Hrmann , Josef Leydold, Continuous random variate generation by fast numerical inversion, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.347-362, October
W. Hrmann , J. Leydold, Random-number and random-variate generation: automatic random variate generation for simulation input, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
Dong-U Lee , Wayne Luk , John D. Villasenor , Peter Y. K. Cheung, A Gaussian Noise Generator for Hardware-Based Simulations, IEEE Transactions on Computers, v.53 n.12, p.1523-1534, December 2004
t-concave;rejection method;ratio of uniforms;universal method;nonuniform;adaptive method;random-number generation;log-concave