TY - GEN
T1 - Exact sublinear binomial sampling
AU - Farach-Colton, Martín
AU - Tsai, Meng-Tsung
PY - 2013
Y1 - 2013
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 O(n) time and has no precision loss, however, this method is often too slow in many settings. 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 (GSL) [10], however, all known sublinear-time algorithms involve precisions loss, which introduces artifacts into the sampling, such as discontinuities. 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.
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 O(n) time and has no precision loss, however, this method is often too slow in many settings. 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 (GSL) [10], however, all known sublinear-time algorithms involve precisions loss, which introduces artifacts into the sampling, such as discontinuities. 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.
UR - http://www.scopus.com/inward/record.url?scp=84893346975&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45030-3_23
DO - 10.1007/978-3-642-45030-3_23
M3 - Conference contribution
AN - SCOPUS:84893346975
SN - 9783642450297
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 240
EP - 250
BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013
Y2 - 16 December 2013 through 18 December 2013
ER -