Accession Number:

ADA061651

Title:

Sampling from the Multinomial Distribution on a Computer.

Descriptive Note:

Technical rept.,

Corporate Author:

NORTH CAROLINA UNIV AT CHAPEL HILL

Personal Author(s):

Report Date:

1978-10-01

Pagination or Media Count:

32.0

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.

Subject Categories:

  • Statistics and Probability
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE