Binomial random variate generation

ABSTRACT

Existing binomial random-variate generators are surveyed, and a new generator designed for moderate and large means is developed. The new algorithm, BTPE, has fixed memory requirements and is faster than other such algorithms, both when single, or when many variates are needed.

REFERENCES

• 1: Abramowitz, M., and Stegun, I.A. Handbook of Mathematical Functions, National Bureau of Standards, Applied Mathematics Series 55, June 1964.
• 2: Ahrens, J.H., and Dieter, U. Computer methods for sampling from gamma, beta, poisson and binomial distributions, Computing 12, (1974), 223-246.
• 3: Ahrens, J.H., and Dieter, U. Sampling from binomial and poisson distributions: A method with bounded computation times, Computing 25, 1980, 193-208.
• 4: J. H. Ahrens , U. Dieter, Computer Generation of Poisson Deviates from Modified Normal Distributions, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.163-179, June 1982 [doi>10.1145/355993.355997]
• 5: Atkinson, A.C. The computer generation of poisson random variables, Applied Statistics 28, 1, 1979, 29-35.
• 6: Atkinson, A.C. Recent developments in the computer generation of poisson random variables, Applied Statistics 28, 3, 1979, 260-263.
• 7: Paul Bratley , Bennett L Fox , Linus E Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1986
• 8: Chen, H.C., and Asau, Y. On generating random variates from an empirical distribution, AIIE Transactions 6, 1974, 163-166.
• 9: R. C. H. Cheng, Generating beta variates with nonintegral shape parameters, Communications of the ACM, v.21 n.4, p.317-322, April 1978 [doi>10.1145/359460.359482]
• 10: Devroye, L. The computer generation of poisson random variables, Computing 26, 1981, 197-207.
• 11: Devroye, L. "The Computer Generation of Binomial Random Variables,'' Technical Report, McGill University, Montreal, Quebec, Canada, 1980.
• 12: Devroye, L. Generating the maximum of independent identically distributed random variables, Computers and Mathematics with Applications 6, 1980, 305-315.
• 13: Devroye, L., and Naderisamani, A. "Binomial Random Variate Generator,'' Technical Report, McGill University, Montreal, Quebec, Canada, 1980.
• 14: Feller, W. An Introduction to Probability Theory and Its Applications, Volume 1, Wiley, New York, 1968.
• 15: Fishman, G.S. Sampling from the poisson distribution on a computer, Computing 17, 1976, 147-156.
• 16: George S. Fishman, Principles of Discrete Event Simulation, John Wiley & Sons, Inc., New York, NY, 1978
• 17: Fishman, G.S. Sampling from the binomial distribution on a computer, Journal of the American Statistical Association 74, 366, 1979, 418-423.
• 18: Fishman, G.S., and Moore, L.R. Sampling from a discrete distribution while preserving monotonicity, The American Statistician 38, 3 1984, 219-223.
• 19: Kachitvichyanukul, V., and Schmeiser, B.W. "Binomial Random Variate Generation," Technical Report 83-9, Industrial and Management Engineering, The University of Iowa, 1983.
• 20: Kinderman, A.J., and Ramage, J.G. Computer generation of normal random variables, Journal of the American Statistical Association 71, 356, 1976, 893-896.
• 21: Kronmal, R.A., and Peterson, A.V., Jr. On the alias method for generating random varaibles from a discrete distribution, American Statistician 33, 1979, 214-218.
• 22: Relies, D.A. A simple algorithm for generating binomial random variables when N is large. Journal of the American Statistical Association 67, 1972, 612-613.
• 23: Schmeiser, B.W. "Random Variate Generation: A Survey." In Simulation with Discrete Models: A State-of-the-Art View, T.I. Oren, C.M. Shub, and P.F. Roth (eds.). In Proceedings of the 1980 Winter Simulation Conference, IEEE, 1980, 79-104.
• 24: Bruce Schmeiser, Random variate generation, Proceedings of the 13th conference on Winter simulation, p.227-242, December 09-11, 1981, Atlanta, Georgia
• 25: Schmeiser, B.W,, and Babu, A.J.G. Beta variate generation via exponential majorizing functions, Operations Research 28, 4, 1980, 917-926.
• 26: Schmeiser, B.W., and Kachitvichyanukul, V. "Poisson Random Varlate Generation," Research Memorandum 81-4, Purdue University, 1981.
• 27: Bruce Schmeiser , Varatas Kachitvichyanukul, Correlation induction without the inverse transformation, Proceedings of the 18th conference on Winter simulation, p.266-274, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318445]
• 28: Alastair J. Walker, An Efficient Method for Generating Discrete Random Variables with General Distributions, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.253-256, Sept. 1977 [doi>10.1145/355744.355749]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms