Exact sublinear binomial sampling

DOI10.1007/S00453-015-0077-8zbMATH Open1331.68279OpenAlexW2284102689MaRDI QIDQ5963375FDOQ5963375

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

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

zbMATH Keywords

binomial distributionexact samplingsublinear sampling

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Alias Method for Generating Random Variables from a Discrete Distribution
• Title not available (Why is that?)
• The generation of binomial random variates
• The patchwork rejection technique for sampling from unimodal distributions
• Sampling from binomial and Poisson distributions: a method with bounded computation times
• Sampling exactly from the normal distribution
• Title not available (Why is that?)
• Generating the maximum of independent identically distributed random variables
• Heterogeneous subset sampling
• Efficient generation of networks with given expected degrees
• Exact and Efficient Generation of Geometric Random Variates and Random Graphs
• Internal DLA: Efficient Simulation of a Physical Growth Model
• Exact Sublinear Binomial Sampling

Cited In (4)

• OptORAMa: Optimal oblivious RAM
• Perfect $L_p$ Sampling in a Data Stream
• Title not available (Why is that?)
• Exact Sublinear Binomial Sampling

Uses Software

• gmp
• R
• carData
• car
• GSL

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)