Efficient table-free sampling methods for the exponential, Cauchy, and normal distributions

ABSTRACT

Three algorithms for sampling from exponential, Cauchy and normal distributions are developed. They are based on the "exact approximation" method, and their expected numbers of consumed uniform deviates are less than 1.04 per sample from the target distributions. The algorithms are simple and easily implemented in any desired precision. They require no space for long tables of auxiliary vectors, merely a few constants are needed. Nevertheless, their speed compares well with the performance of much more complex and table-aided sampling procedures.

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. Extensions of Forsythe's method for random sampling from the normal distribution. Math. Cornp. 27, 124 (Oct. 1973), 927-937.
• 3: Ahrens, J.H., and Dieter, U. Computer methods for sampling from gamma, beta, Poisson and binomial distributions. Computing 12, (1974), 223-246.
• 4: Ahrens, J.H., and Dieter, U. Sampling from binomiai and Poisson distributions: a method with bounded computation times. Computing 25, (1980), 193-208.
• 5: J. H. Ahrens , U. Dieter, Generating gamma variates by a modified rejection technique, Communications of the ACM, v.25 n.1, p.47-54, Jan. 1982 [doi>10.1145/358315.358390]
• 6: 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]
• 7: Box, G.E.P., and Muller, M.E. A note on the generation of random normal deviates. Ann. Math. Stat. 29, 2 (1958), 610-611.
• 8: Devroye, L. Non-Uniform Random Variate Generation. Springer-Verlag, New York, New York, 1986.
• 9: 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]
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: G. Marsaglia , M. D. MacLaren , T. A. Bray, A fast procedure for generating normal random variables, Communications of the ACM, v.7 n.1, p.4-10, Jan. 1964 [doi>10.1145/363872.363883]
• 12: Marsaglia, G. Generating exponential random variables. Ann. Math. Stat. 32, 3 (1961), 899-902.
• 13: Marsaglia, G. The exact-approximation method for generating random variables in a computer. J. Arner. Slat. Assn. 79, 385 (Mar. 1984), 218-221.
• 14: von Neumann, ~. Various techniques in connection with random digits. Monte Carlo methods. Nat. Bureau Standards, AMS 12, (1951), 36-38.
• 15: Sibuya, M. Exponential and other random variable generators. Ann. Inst. Star. Math. 13, (1961/62), 231-237.

INDEX TERMS

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

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

General Terms:
Algorithms