An Analysis of an Open Source Binomial Random Variate Generation Algorithm

The binomial distribution is the probability distribution of the number of successes for a sequence of n independent trials with success probability p. Efficiently generating binomial random variates is important in many modeling and simulation applications, such as in medicine, risk management, fraud and anomaly detection, among others. A variety of algorithms exist for generating binomial random variates. This paper concerns the algorithm chosen for rho mu, an open source Java library for efficient randomization. In rho mu, I implemented a hybrid of two existing binomial random variate algorithms. For most cases, rho mu's hybrid relies on the BTPE Algorithm (Binomial, Triangle, Parallelogram, Exponential), and falls back to the inverse transform for cases that BTPE cannot handle. BTPE uses rejection sampling, and BTPE's authors originally provided an analytical formula for the expected number of iterations in terms of n and p. That expression is complicated to interpret in practical contexts. I explore BTPE by instrumenting rho mu's implementation to empirically analyze its acceptance/rejection behavior to gain further insight into its runtime performance. Although the number of iterations depends upon n and p, my experiments show that the average number of iterations is always under 2, and that the average number of random uniform floats required to generate a single random binomial is under 4 (2 per iteration). Thus, when analyzing the runtime of a simulation algorithm that includes steps generating random binomials, one can consider such steps to have a constant runtime.