A composition-search algorithm for low-parameter poisson generation

Abstract

The paper addresses the problem of generating Poisson pseudorandom variables for small values ( < 30 say) of the parameter λ, where λ may vary from call to call. A new algorithm is developed; this separates the distribution into three components and searches these as necessary. Timings for a FORTRAN 77 implementation demonstrate the superiority of the algorithm compared with the usual search-from-the-origin algorithm. These results show that Poisson generation procedures which currently switch to search-from-the-origin for small values of λ should switch instead to the new algorithm.

Keywords:

• Composition-search algorithm
• approximate probabilities
• sums of probabilities
• computer generation
• poisson pseudorandom variables