Generating gamma variates by a modified rejection technique

ABSTRACT

A suitable square root transformation of a gamma random variable with mean a ≥ 1 yields a probability density close to the standard normal density. A modification of the rejection technique then begins by sampling from the normal distribution, being able to accept and transform the initial normal observation quickly at least 85 percent of the time (95 percent if a ≥ 4). When used with efficient subroutines for sampling from the normal and exponential distributions, the resulting accurate method is significantly faster than competing algorithms.

REFERENCES

• 1: J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
• 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. Extensions of Forsythe's method for random sampling from the normal distribution. Math. Comput. 27, 124 (Oct. 1973), 927-937.
• 4: Ahrens, J,H., and Dieter, U. Sampling from standard gamma distributions. Submitted to A CM Trans. Math. Softw.
• 5: Ahrens, J,H., and Kohrt, K.D. Computer methods for efficient sampling from largely arbitrary statistical distributions. Computing 26 (1981), 19-31.
• 6: Atkinson, A.C. An easily programmed algorithm for generating gamma random variables. J. Roy. Stat. Soc. A 140 (1977), 232-234.
• 7: Atkinson, A.C., and Pearce, M.C. The computer generation of beta, gamma and normal random variables. J. Roy. Stat Soc, A 139 (1976), 431--461.
• 8: Best, D.J. A new method for the computer generation of gamma or chi-squared pseudo-random variables. To appear in J. Amer. Stat. Assoc.
• 9: Best, D.J. Letter to the editors. Appl. Star. 27 (1978), 181.
• 10: Cheng, R.C.H. The generation of gamma variables with nonintegral shape parameter. Appl. Stat. 26 (1977), 71-75.
• 11: R. C. H. Cheng , G. M. Feast, Gamma variate generators with increased shape parameter range, Communications of the ACM, v.23 n.7, p.389-395, July 1980 [doi>10.1145/358886.358893]
• 12: Cheng, R.C.H., and Feast, G.M. Some simple gamma variate generators. Appl. Stat. 28 (1979), 290-295.
• 13: Dieter, U. Optimal acceptance-rejection envelopes for sampling from various distributions. Submitted to Math. Comput. (1981).
• 14: Dieter, U., and Ahrens, J.H. Acceptance-rejection techniques for sampling from the gamma and beta distributions. Tech. Rep. 83, Dep. Statistics, Stanford University, Stanford, CA, 1974.
• 15: George S. Fishman, Discrete-event simulation, Springer-Verlag, London, 2001
• 16: George S. Fishman, Sampling from the gamma distribution on a computer, Communications of the ACM, v.19 n.7, p.407-409, July 1976 [doi>10.1145/360248.360256]
• 17: Greenwood, A.J. A fast generator for gamma distributed random variables. COMPSTAT(1974), 19-27.
• 18: A. J. Kinderman , J. F. Monahan, Computer Generation of Random Variables Using the Ratio of Uniform Deviates, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.257-260, Sept. 1977 [doi>10.1145/355744.355750]
• 19: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 20: Marsaglia, G. The squeeze method for generating gamma variates. Comput, Math. Appl. 3 (1977), 321-325.
• 21: yon Neumann, J. Various techniques used in connection with random digits. Collected Works, Vol. 5, 768-770. Pergamon Press, New York, 1963.
• 22: Pandu R. Tadikamalla , Mark E. Johnson, A survey of methods for sampling from the gamma distribution, Proceedings of the 10th conference on Winter simulation, p.131-134, December 04-06, 1978, Miami Beach, FL
• 23: Pandu R. Tadikamalla, Computer generation of gamma random variables—II, Communications of the ACM, v.21 n.11, p.925-928, Nov. 1978 [doi>10.1145/359642.359648]
• 24: Vaduva, I. On computer generation of gamma random variables by rejection and composition procedures. Math. Oper.-forsehung und Stat., Set. Star. 4 (1977), 545-576.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
acceptance—rejection method, gamma distribution, random numbers