2000-04.ley-wh

Black Box Algorithms for Generating Non-Uniform Continuous Random Variates

Josef Leydold and Wolfgang Hörmann


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:

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