Rejection-Inversion to Generate Variates from Monotone Discrete Distributions
For discrete distributions a variant of rejection from a continuous
hat function is presented. The main advantage of the new method, called
rejection-inversion, is that no extra uniform random
number to decide between acceptance and rejection is required which means
that the expected number of uniform variates required is halved.
Using rejection-inversion and a squeeze, a simple universal method
for a large class of monotone discrete distributions is developed. It
can be used to generate variates from the tails of most
standard discrete distributions.
Rejection-inversion applied to the Zipf (or zeta) distribution results
in algorithms that are short and simple and at least twice as fast as
the fastest methods suggested in the literature.
Mathematics Subject Classification:
65C10 (Random Number Generation)
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
random number generation,
rejection method, Zipf distribution, tail of Poisson
distribution, universal algorithm, T-concave
© ACM, (1996). This is the author's version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in
Trans. Model. Comput. Simul. 6(3), 169-184.