Engineering Proceedings, 56(1), Article 86, . doi:10.3390/ASEC2023-15349

[PDF] [BIB] [DOI] [CODE]

Abstract

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, and fraud and anomaly detection, among others. A variety of algorithms exist for generating binomial random variates. This paper concerns the algorithm chosen for ρμ, an open source Java library for efficient randomization, which uses a hybrid of two existing binomial random variate algorithms: the BTPE Algorithm (Binomial, Triangle, Parallelogram, Exponential) and 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 ρμ’s implementation to empirically analyze its acceptance/rejection behavior to gain further insights 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 two, and that the average number of random uniform variates required to generate a single random binomial is under four (two 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.