97-02-03.wh-der
An Automatic Generator for a Large Class
of Unimodal Discrete Distributions
Abstract
The automatic Algorithm ARI developed in this paper can generate
variates from a large class of unimodal discrete distributions. It is only
necessary to know the mode of the distribution and to have a subprogram available
that can evaluate the probabilities. In a set up step the algorithm constructs
a table mountain shaped hat function. Then rejection inversion, a new variant
of the rejection method for discrete distributions that needs only one uniform
random number per iteration, is used to sample from the desired distribution.
It is shown that the expeceted number of iterations is uniformly bounded for all
T-concave discrete distributions.
Utilizing a simple squeeze or an auxiliary table of moderate size, which is
initialized during generation and not in the set up, Algorithm ARI is
fast, at least as fast as the fastest known methods designed for the Poisson,
binomial
and hypergeometric distributions. The set up time of the algorithm is not affected
by the size of the domain of the distribution and is about ten times longer
than the generation of one variate.
Compared with the very fast and well known alias and indexed search methods
the set up of Algorithm ARI is much faster
but the generation time is about two times slower. More important than the
speed is the fact that Algorithm ARI is the first automatic algorithm
that can generate samples from discrete distributions with heavy tails.
Mathematics Subject Classification:
65C10 (Random Number Generation)
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
General Terms:
Algorithms
Key Words:
random variate generation, discrete distributions,
universal generator, T-concave
Download Preprint
Wolfgang.Hoermann@statistik.wu-wien.ac.at