Exact Sublinear Binomial Sampling

Drawing a random variate from a given binomial distribution B(n, p) is an important subroutine in many large-scale simulations. The naive algorithm takes time w.h.p. in the WordRAM model, which is too slow in many settings, though to its credit, it does not suffer from precision loss. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [22] and the GNU Scientific Library  [11], however, all previous sublinear-time algorithms involve precision loss, which introduces artifacts such as discontinuities into the sampling. In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss. We assume that each bit of p can be obtained in time.