Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Short universal generators via generalized ratio-of-uniforms method

Author: Josef Leydold
Journal: Math. Comp. 72 (2003), 1453-1471
MSC (2000): Primary 65C10; Secondary 65U05
Published electronically: March 26, 2003
MathSciNet review: 1972746
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We use inequalities to design short universal algorithms that can be used to generate random variates from large classes of univariate continuous or discrete distributions (including all log-concave distributions). The expected time is uniformly bounded over all these distributions for a particular generator. The algorithms can be implemented in a few lines of high level language code.

References [Enhancements On Off] (What's this?)

  • 1. Ahrens, J. H. (1993).
    Sampling from general distributions by suboptimal division of domains.
    Grazer Math. Berichte 319, 20 pp.
  • 2. Ahrens, J. H. (1995).
    A one-table method for sampling from continuous and discrete distributions.
    Computing 54(2), 127-146. MR 96a:65011
  • 3. Derflinger, G. (2000).
    private communication.
  • 4. Derflinger, G., W. Hörmann, and J. Leydold (2002).
    Universal methods of nonuniform random variate generation.
    in preparation.
  • 5. Devroye, L. (1984a).
    On the use of probability inequalities in random variate generation.
    J. Stat. Comput. Simulation 20, 91-100. MR 87g:65009
  • 6. Devroye, L. (1984b).
    A simple algorithm for generating random variates with a log-concave density.
    Computing 33(3-4), 247-257. MR 86d:65019
  • 7. Devroye, L. (1986).
    NonUniform Random Variate Generation.
    New-York: Springer-Verlag. MR 87i:65012
  • 8. Devroye, L. (1987).
    A simple generator for discrete log-concave distributions.
    Computing 39, 87-91. MR 89f:65007
  • 9. Dieter, U. (1989).
    Mathematical aspects of various methods for sampling from classical distributions.
    In E. A. Mc Nair, K. J. Musselman, and P. Heidelberger (Eds.), Proc. 1989 Winter Simulation Conf., pp. 477-483.
  • 10. Evans, M. and T. Swartz (1998).
    Random variable generation using concavity properties of transformed densities.
    Journal of Computational and Graphical Statistics 7(4), 514-528.
  • 11. Gilks, W. R. and P. Wild (1992).
    Adaptive rejection sampling for Gibbs sampling.
    Applied Statistics 41(2), 337-348.
  • 12. Gradshteyn, I. S. and I. M. Ryzhnik (1994).
    Table of Integrals, Series, and Products (5th ed.).
    Academic Press. MR 94g:00008
  • 13. Hörmann, W. (1995).
    A rejection technique for sampling from T-concave distributions.
    ACM Trans. Math. Software 21(2), 182-193. MR 96b:65018
  • 14. Hörmann, W. and G. Derflinger (1996).
    Rejection-inversion to generate variates from monotone discrete distributions.
    ACM TOMACS 6(3), 169-184.
  • 15. Hörmann, W. and G. Derflinger (1997).
    An automatic generator for a large class of unimodal discrete distributions.
    In A. R. Kaylan and A. Lehmann (Eds.), ESM 97, pp. 139-144.
  • 16. Kinderman, A. J. and F. J. Monahan (1977).
    Computer generation of random variables using the ratio of uniform deviates.
    ACM Trans. Math. Software 3(3), 257-260.
  • 17. Leydold, J. (2000a).
    Automatic sampling with the ratio-of-uniforms method.
    ACM Trans. Math. Software 26(1), 78-98.
  • 18. Leydold, J. (2000b).
    A note on transformed density rejection.
    Computing 65(2), 187-192. MR 2002e:65016
  • 19. Leydold, J. (2001).
    A simple universal generator for continuous and discrete univariate T-concave distributions.
    ACM Trans. Math. Software 27(1), 66-82.
  • 20. Stadlober, E. (1989).
    Sampling from Poisson, binomial and hypergeometric distributions: Ratio of uniforms as a simple and fast alternative.
    Number 303 in Bericht der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum-Graz. MR 91b:65008
  • 21. Wakefield, J. C., A. E. Gelfand, and A. F. M. Smith (1991).
    Efficient generation of random variates via the ratio-of-uniforms method.
    Statist. Comput. 1(2), 129-133.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65C10, 65U05

Retrieve articles in all journals with MSC (2000): 65C10, 65U05

Additional Information

Josef Leydold
Affiliation: University of Economics and Business Administration, Department for Applied Statistics and Data Processing, Augasse 2-6, A-1090 Vienna, Austria

Keywords: Nonuniform random variates, universal method, ratio-of-uniforms method, transformed density rejection, discrete distributions, continuous distributions, log-concave distributions, $T$-concave distributions
Received by editor(s): August 8, 2000
Published electronically: March 26, 2003
Additional Notes: This work was supported by the Austrian Science Foundation (FWF), project no. P12805-MAT
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society