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 Free Access

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. J. H. Ahrens, A one-table method for sampling from continuous and discrete distributions, Computing 54 (1995), no. 2, 127–146 (English, with English and German summaries). MR 1318330,
  • 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. Luc Devroye, On the use of probability inequalities in random variate generation, J. Statist. Comput. Simulation 20 (1984), no. 2, 91–100. MR 775472,
  • 6. L. Devroye, A simple algorithm for generating random variates with a log-concave density, Computing 33 (1984), no. 3-4, 247–257 (English, with German summary). MR 773927,
  • 7. Luc Devroye, Nonuniform random variate generation, Springer-Verlag, New York, 1986. MR 836973
  • 8. L. Devroye, A simple generator for discrete log-concave distributions, Computing 39 (1987), no. 1, 87–91 (English, with German summary). MR 908559,
  • 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. I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 5th ed., Academic Press, Inc., Boston, MA, 1994. Translation edited and with a preface by Alan Jeffrey. MR 1243179
  • 13. Wolfgang Hörmann, A rejection technique for sampling from 𝑇-concave distributions, ACM Trans. Math. Software 21 (1995), no. 2, 182–193. MR 1342355,
  • 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. J. Leydold, A note on transformed density rejection, Computing 65 (2000), no. 2, 187–192. MR 1807716,
  • 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. Ernst Stadlober, Sampling from Poisson, binomial and hypergeometric distributions: ratio of uniforms as a simple and fast alternative, Berichte der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum [Reports of the Mathematical-Statistical Section of the Research Society Joanneum], vol. 303, Forschungszentrum Graz, Mathematisch-Statistische Sektion, Graz, 1989. MR 996245
  • 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