Sampling from the Multinomial Distribution on a Computer.
Abstract
This paper describes algorithms to effect multinomial sampling on a computer in ways that protect the sampler against an excess computing cost per sample. Section 2 presents the multinomial model together with an equivalent representation in terms of a series of binomial sampling experiments. The binomial representation is further discussed in Section 4. Sections 3 and 5 demonstrate the danger of using too simplistic a sampling scheme if execution time is a concern. Section 6 describes how a normal approximation to the binomial distribution can make execution time virtually independent of n. A criterion of acceptability is described. Section 7 describes an acceptance-rejection technique that, when used with a Poisson sample, allows the desired binomial sampling exactly. Using a normal approximation to the Poisson distribution, one can again generate multinomial samples virtually independent of n. Section 8 describes a procedure for binomial sampling based on the inverse transform method. Section 9 describes the ordering of the serial binomial experiments in response to alternative objectives. Section 10 describes algorithm M3 which puts all the suggestions of earlier sections together.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1978
- Accession Number
- ADA061651
Entities
People
- George S. Fishman
Organizations
- University of North Carolina at Chapel Hill