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.
Previous Article in event
Synthesis and structural characterization of novel urethane-dimethacrylate monomer with two quaternary ammonium groupsPrevious Article in session
Next Article in event
Some microbiological characteristics of the biofilm on the surface of pre-production pellets of polypropylene microplastics after short exposure in the soilNext Article in session
An Analysis of an Open Source Binomial Random Variate Generation Algorithm
Published: 26 October 2023 by MDPI in 4th International Electronic Conference on Applied Sciences session Computing and Artificial Intelligence
Keywords: binomial; btpe; inverse transform; Java; modeling; open source; random variate; simulation