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