An Efficient Two-Stage Procedure for Generating Random Variates from the Multinomial Distribution

A two-stage procedure is proposed for the generation of random variates from a multinomial distribution.In the first stage we propose that cell frequencies be generated as random deviates from a Poisson distribution with parameters proportional to the probabilities of the multinomial.When the sum of the frequencies generated in the first stage is less than the total sample size of the multinomial distribution, the remaining observations are generated in a second stage from the multinomial distribution.An optimal or near-optimal set of Poisson parameters in the first stage, used in conjunction with the alias method, can reduce the amount of computation required to generate the multinomial variates to less than 10% of that required by using simple random sampling to obtain the individual observations.