Exact sublinear binomial sampling

Martín Farach-Colton, Meng Tsung Tsai

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
    Pages240-250
    Number of pages11
    DOIs
    StatePublished - 2013
    Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
    Duration: Dec 16 2013Dec 18 2013

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume8283 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference24th International Symposium on Algorithms and Computation, ISAAC 2013
    Country/TerritoryChina
    CityHong Kong
    Period12/16/1312/18/13

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Exact sublinear binomial sampling'. Together they form a unique fingerprint.

    Cite this