Exact Sublinear Binomial Sampling

Martín Farach-Colton, Meng Tsung Tsai

    Research output: Contribution to journalArticlepeer-review


    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 (US)
    Pages (from-to)637-651
    Number of pages15
    Issue number4
    StatePublished - Dec 1 2015


    • Binomial distribution
    • Exact sampling
    • Sublinear sampling

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


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

    Cite this