Expected time analysis of a simple recursive Poisson random variate generator (Q2277745): Difference between revisions

The well-known recursive procedure for generating Poisson random variables with parameter \(\lambda\) is considered. It is shown how it can be manipulated to produce random variables at an expected time cost of O(log log \(\lambda\)). The expected time is not uniformly bounded in \(\lambda\), but the algorithm should prove useful for extremely large value of \(\lambda\) because virtually all numerical problems associated with the evaluation of the factorial function are eliminated. The probabilistic analysis presented in the paper may be applied in other situations as well in which there are a random number of levels of recursion. Recommendations about the choice of the constant p which is used in the algorithm are given.