Ratio of uniforms as a convenient method for sampling from classical discrete distributions

ABSTRACT

Many computer methods for generating variates from classical discrete distributions are available; some of them are simple and others are very fast. However, simple or convenient procedures are slow when the means μ are large. Very fast algorithms are rather involved, so that most users will not go to the trouble of implementing them. Fortunately, algorithms having the advantage of being simple and fast are obtained by applying the ratio of uniforms method to discrete distributions in a skilful way. We discuss several issues of this approach with respect to Poisson, binomial and hypergeometric distributions.

REFERENCES

• 1: Ahrens, J. H. and Dieter, U. (1982). Computer generation of Poisson deviates from modified normal distributions. ACM Transactions on Mathematical Software 8, 163--179.
• 2: Ahrens, J. H. and Dieter, U. (1989). A convenient sampling method with bounded computation times for Poisson distributions. American Journal of Mathematical and Management Sciences (to appear).
• 3: Ahrens, J. H. and Kohrt, K. D. (1981). Computer methods for efficient sampling from largely arbitrary statistical distributions. Computing 26, 19--31.
• 4: Chen, H. C. and Asau, Y. (1974). On generating random variates from an empirical distribution. AIIE Transactions 6, 163--166.
• 5: Devroye, L. (1986). Non-uniform random variate generation. Springer, New York.
• 6: Kachitvichyanukul V. and Schmeiser, B. W. (1985). Computer generation of hypergeometric random variates. Journal of Statistical Computation and Simulation 22, 127--145.
• 7: Kachitvichyanukul, V. and Schmeiser, B. W. (1988). Binomial random variate generation. Communications of the ACM 31, 216--222.
• 9: Kinderman, A. J. and Monahan, J. F. (1977). Computer generation of random variables using the ratio of uniform deviates. ACM Transactions on Mathematical Software 3, 257--260.
• 10: Kinderman, A. J. and Monahan, J. F. (1980). New methods for generating Student's t and gamma variables. Computing 25, 369--377.
• 11: Monahan, J. F. (1987). An algorithm for generating chi random variables. ACM Transactions on Mathematical Software 13, 168--172.
• 12: Schmeiser, B. W. and Kachitvichyanukul (1981). Poisson random variate generation. Research Memorandum 81-4. School of Industrial Engineering, Purdue University, West Lafayette, Indiana.
• 13: Stadlober, E. (1989a). Binomial random variate generation: A method based on ratio of uniforms. American Journal of Mathematical Management Sciences (to appear).
• 14: Stadlober, E. (1989b). Sampling from Poisson, binomial and hypergeometric distributions: Ratio of uniforms as a simple and fast alternative. Mathematisch-Statistische Sektion 303. Forschungsgesellschaft Joanneum, Graz, Austria.
• 15: Walker, A. J. (1977). An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software 3, 253--256.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design