Computing Poisson probabilities

ABSTRACT

We propose an algorithm to compute the set of individual (nonnegligible) Poisson probabilities, rigorously bound truncation error, and guarantee no overflow or underflow. Work and space requirements are modest, both proportional to the square root of the Poisson parameter. Our algorithm appears numerically stable. We know no other algorithm with all these (good) features. Our algorithm speeds generation of truncated Poisson variates and the computation of expected terminal reward in continuous-time, uniformizable Markov chains. More generally, our algorithm can be used to evaluate formulas involving Poisson probabilities.

REFERENCES

• 1: Abramowitz, M., and Stegun, I.E. Handbook of Mathematical Functions. U.S. Dept. of Commerce, National Bureau of Standards Appl. Math. Series #55, 1972.
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: Feller, W. An Introduction to Probability Theory and Its Applications, 1. Wiley, New York, 1968.
• 4: Fox. B.L. Numerical methods for transient Markov chains. Technical report, Cornel} University, 1987.
• 5: Fox, B.L. and Glynn, P.W. Gonditional confidence intervals. Technical report, Gornell University, 1988.
• 6: Gill, P.E., Murray, W., and Wright, M.H. Practical Optimization. Academic Press, London, 1981.
• 7: Glynn, P.W. Upper bounds on Poisson tail probabilities. Operations Research Letters 6, 1 (March, 1987}, 9-14.
• 8: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 9: Gross, D., and Miller, D.R. The randomization technique as a modeling tool and solution procedure for transient Markov processes. Operations Research 32, 2 (March-April, 1984), 343-361.
• 10: Leo Knüsel, Computation of the chi square and Poisson distribution, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.1022-1036, July 1986 [doi>10.1137/0907069]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms