92-04-07.wh
The Generation of Binomial Random Variates
Abstract
The transformed rejection method, a combination of inversion and
rejection, which can be applied to various continuous
distributions, is well suited to generate binomial random variates as
well. The resulting algorithms are simple and fast, and need
only a short set-up. Among
the many possible variants two algorithms are described and tested:
BTRS a short but nevertheless fast rejection algorithm and BTRD which
is more complicated as the idea of decomposition is utilized. For BTRD
the average number of uniforms required to return one binomial deviate
lies between 2.5 and 1.4 which is considerably lower than for any of
the known uniformly fast algorithms. Timings for a C-implementation
show that for the case that the parameters of the binomial
distribution vary from call to call BTRD is faster than the current
state of the art algorithms. Depending on the computer, the speed
of the uniform generator used and the binomial parameters the savings
are between 5 and 40 percent.
Mathematics Subject Classification:
65C10 (Random Number Generation)
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
Key Words:
random numbers, binomial distribution, transformed rejection method, simulation
Download Preprint
Wolfgang.Hoermann@statistik.wu-wien.ac.at