Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Exact Sublinear Binomial Sampling
verfasst von : Martín Farach-Colton, Meng-Tsung Tsai
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{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.