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 <*u*^{2}<=*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).

**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