2000-04.ley-wh
Black Box Algorithms for Generating Non-Uniform Continuous Random Variates
Abstract
There exists a vast 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 probability density
function. The designing goals for these methods are fast generators
and/or simple code.
However in many simulation situations the application of standard
distributions is not adequate. Thus during the last decade
so called universal (or black box) algorithms have been developed
to avoid the design of special algorithms for these cases.
Black box methods require the knowledge of some data about the
desired distribution, like (a multiple of) the probability density
function, the (approximate) mode of the distribution, (approximate)
regions of monotonicity or log-concavity of the density function.
It depends on the particular method, which data are necessary and/or
useful.
The inversion method is the most general method for generation
non-uniform random variates. However computing the inverse of an
arbitrary cumulative distribution function requires numerical
algorithms. Thus these methods are very slow or have an expensive
setup step and are not exact.
The most efficient algorithms use acceptance/rejection techniques
where hat and squeezes are computed automatically. We
consider the following three methods:
- (TDR) Transformed density rejection
- uses the concavity of a transformed density to generate hat function
and squeezes by means of tangents and secants
(Devroye 1986, Gilks and Wild 1992, and Hörmann 1995).
It can be utilized for
any density f where a differentiable, strictly monotonically increasing
transformation T exists, such that T(f(x))
is concave (see Hörmann (1995) for details). Such a density is
called T-concave; log-concave densities are an example with
T(x)=log(x).
- (TABL) A table method
- introduced in Ahrens (1995) uses a
piecewise constant hat and squeeze, i.e., the density is covered by
vertical bars. It requires the knowledge of regions where the
density function is monotone. This method is extremely fast. However
the tails of the distribution have to be treated differently.
- (AROU) The ratio-of-uniforms method
- uses the fact that if
(V,U) is uniformly distributed on
A={(v,u): 0 < u2 <= f(v/u)},
then the ratio V/U has
probability density function f(x). For sampling random points
uniformly distributed in A rejection from a convenient enveloping
region is used. Since A is convex for a large class of
distributions, enveloping and squeezing polygons can be computed
automatically (see Leydold (1999) for details).
For the problem of finding appropriate construction points for the hat
function Gilks and Wild (1992) introduces the ingenious concept of
adaptive rejection sampling.
But there are other methods as well for providing construction points
during the setup.
We have implemented various versions of TDR, TABL and AROU (and some
others) in ANSI C. Our main goal was to get a portable, flexible and
robust program. Thus we have made some changes to the algorithms
described in literature. The resulting library is called UNURAN and is
available via anonymous ftp
(
ftp://statistik.wu-wien.ac.at/src/unuran/).
We have compared these black box algorithms to well known generators
for standard distributions. It is obvious that these methods require
some setup time and more memory than generators using e.g. the
Box-Muller method. However although originally motivated to generate
from non-standard distributions we have found several advantages even
for standard distributions:
-
Only one piece of code, well implemented and debugged only once,
is required.
-
By a simple parameter it is possible to choose between fast setup
with slow marginal generation time and vice versa.
-
The algorithms can be made as close to inversion as requested by the
user simply by choosing a rejection constant. Then:
-
The marginal generation time does not depend on the density function
and is faster than many of the specialized generators (even for
the normal distribution).
-
It can be used for variance reduction techniques
(Hörmann and Derflinger (1994) gives an example).
-
The quality of the generated random variates only depends on the
underlying uniform random number generator; in opposition to many
generators that produce random variates of
unpredictable quality (Leydold, Leeb, and Hörmann 2000).
Another feature of UNURAN will be the concept of
``automatic'' methods, where the setup step only produces a
source code (C, C++, FORTRAN, etc.) for the generator which then can
be included into the simulation program. The user gets a fast
generator for the desired distribution (standard or not), where
generation time and quality of the resulting random numbers does not
depend on the distribution.
References:
Ahrens, J.H. (1995).
A one-table method for sampling from continuous and discrete
distributions.
Computing, 54(2):127--146.
Devroye, L. (1986).
Non-Uniform Random Variate Generation.
New-York: Springer-Verlag.
Gilks, W.R. and Wild, P. (1992).
Adaptive rejection sampling for Gibbs sampling.
Applied Statistics, 41(2):337--348.
Hörmann, W. (1995).
A rejection technique for sampling from T-concave distributions.
ACM Trans. Math. Software, 21(2):182--193.
Hörmann, W. and Derflinger, G. (1994).
Universal generators for correlation induction.
In R.~Dutter and W.~Grossmann, editors, Compstat, Proceedings in
Computational Statistics, pages 52--57, Heidelberg: Physica-Verlag.
Leydold, J. (2000)
Automatic sampling with the ratio-of-uniforms method.
ACM Trans. Math. Software, 26(1).
to appear.
Leydold, J., Leeb H. and Hörmann, W. (2000).
Higher dimensional properties of non-uniform pseudo-random variates.
In H.~Niederreiter and J.~Spanier, editors, Monte Carlo and
Quasi-Monte Carlo Methods 1998, pages 341--355, Berlin, Heidelberg: Springer-Verlag.
Mathematics Subject Classification:
65C10 (Random Number Generation)
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
General Terms:
Algorithms
Key Words:
random number generation, rejection method, log-concave density,
transformed density rejection, ratio-of-uniforms, black-box algorithm,
universal method
Josef.Leydold@statistik.wu-wien.ac.at