Exact Sublinear Binomial Sampling

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)637-651
Number of pages15
JournalAlgorithmica
Volume73
Issue number4
DOIs
StatePublished - 1 Dec 2015

Keywords

  • Binomial distribution
  • Exact sampling
  • Sublinear sampling

Fingerprint Dive into the research topics of 'Exact Sublinear Binomial Sampling'. Together they form a unique fingerprint.

Cite this