Exact sublinear binomial sampling

DOI10.1007/S00453-015-0077-8MaRDI QIDQ5963375zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Meng-Tsung Tsai

Publication date 19 February 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0077-8

zbMATH Keywords

binomial distributionexact samplingsublinear sampling

Mathematics Subject Classification ID

Recommendations

• Exact Sublinear Binomial Sampling
• Binomial subsampling
• Faster sublinear algorithms using conditional sampling
• Sublinear time approximate sum via uniform random sampling
• Fast perfect sampling from linear extensions
• Sampling from binomial and Poisson distributions: a method with bounded computation times
• Exact sampling for intractable probability distributions via a Bernoulli factory
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Fast sampling of perfectly uniform satisfying assignments
• Polynomial time approximate or perfect samplers for discretized Dirichlet distribution

Cites work

• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3564899 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2002843 (Why is no real title available?)
• scientific article; zbMATH DE number 1861860 (Why is no real title available?)
• Efficient generation of networks with given expected degrees
• Exact Sublinear Binomial Sampling
• Exact and efficient generation of geometric random variates and random graphs
• Generating the maximum of independent identically distributed random variables
• Heterogeneous subset sampling
• Internal DLA: efficient simulation of a physical growth model (extended abstract)
• On the Alias Method for Generating Random Variables from a Discrete Distribution
• Sampling exactly from the normal distribution
• Sampling from binomial and Poisson distributions: a method with bounded computation times
• The generation of binomial random variates
• The patchwork rejection technique for sampling from unimodal distributions

Cited in

(4)

• OptORAMa: Optimal oblivious RAM
• Perfect \(L_p\) sampling in a data stream
• scientific article; zbMATH DE number 418881 (Why is no real title available?)
• Exact Sublinear Binomial Sampling

Describes a project that uses

Uses Software

• GSL
• car
• carData
• R
• gmp

This page was built for publication: Exact sublinear binomial sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963375)