Exact Sublinear Binomial Sampling

Martín Farach-Colton, Meng-Tsung Tsai*

*此作品的通信作者

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)637-651
頁數15
期刊Algorithmica
73
發行號4
DOIs
出版狀態Published - 1 十二月 2015

指紋

深入研究「Exact Sublinear Binomial Sampling」主題。共同形成了獨特的指紋。

引用此