Generating sums in constant average time

ABSTRACT

We derive an algorithm that requires uniformly bounded time to generate the sum of n iid uniform [0,1] random variables. The expected time spent on the computation of the density of the sum per generated random variate tends to zero as n →∞

REFERENCES

• 1: J.H. Ahrens and U. Dieter, "Sampling from binomial and Poisson distributions: a method with bounded computation times," Computing, vol. 25, pp. 193-208, 1980.
• 2: H. Chernoff, "A measure of asymptotic efficiency of tests of a hypothesis based on the sum of observations," Annals oj" Mathematical Statistics, vol. 23, pp. 493-507, 1952.
• 3: Luc Bevroye, An automatic method for generating random variates with a given characteristic function, SIAM Journal on Applied Mathematics, v.46 n.4, p.698-719, August 1986 [doi>10.1137/0146046]
• 4: L. Devroye, Non-Uniform Random Variate Generation, Springer-Verlag, New York, 1986.
• 5: G.S. Fishman, "Sampling from the binomial distribution on a computer," Journal of the American Statistical Association, vol. 74, pp. 418-423, 1979.
• 6: I.S. Gradshteyn and I.M. Ryzhik, Table of Integrals, Series and Products, Academic Press, New York, 1980.
• 7: V. Kachitvichyanukul, "Computer Generation of Poisson, Binomial, and Hypergeometric Random Variates," Ph.D. Dissertation, School of Industrial Engineering, Purdue Universiry, 1982.
• 8: M. Maejima, "The remainder term in the local limit theorem for independent random variables," Tokyo Journal of Mathematics, vol. 3, pp. 311-329, 1980.
• 9: J.K. Ord, Families of Frequency Distributions, Griffin, London, 1972.
• 10: V.V. Petrov, Sums of Independent Random Variables, Springer-Verlag, New York, 1975.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

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

General Terms:
Algorithms, Design, Performance, Theory, Verification