TY - JOUR

T1 - Exact Sublinear Binomial Sampling

AU - Farach-Colton, Martín

AU - Tsai, Meng-Tsung

PY - 2015/12/1

Y1 - 2015/12/1

N2 - 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.

AB - 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.

KW - Binomial distribution

KW - Exact sampling

KW - Sublinear sampling

UR - http://www.scopus.com/inward/record.url?scp=84949315998&partnerID=8YFLogxK

U2 - 10.1007/s00453-015-0077-8

DO - 10.1007/s00453-015-0077-8

M3 - Article

AN - SCOPUS:84949315998

VL - 73

SP - 637

EP - 651

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -