Efficient sampling methods for discrete distributions

DOI10.1007/978-3-642-31594-7_12MaRDI QIDQ2843242zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Konstantinos Panagiotou

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11858/00-001M-0000-002B-85D0-8

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Complexity and performance of numerical algorithms (65Y20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Efficient sampling methods for discrete distributions
• Succinct sampling from discrete distributions
• Maintaining discrete probability distributions optimally
• Dynamic sampling from a discrete probability distribution with a known distribution of rates
• Faster methods for random sampling

Cited in

(16)

• On the efficiency of determinant sampling
• Dynamic sampling from a discrete probability distribution with a known distribution of rates
• Count-then-permute: a precision-free alternative to inversion sampling
• Efficient sampling methods for discrete distributions
• Bayesian shape clustering
• Heterogeneous subset sampling
• scientific article; zbMATH DE number 125289 (Why is no real title available?)
• scientific article; zbMATH DE number 1303578 (Why is no real title available?)
• \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
• Maintaining discrete probability distributions optimally
• Practical algorithms for generating a random ordering of the elements of a weighted set
• Density independent algorithms for sparsifying k-step random walks
• Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time
• Succinct sampling from discrete distributions
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Discretization-based direct random sample generation

This page was built for publication: Efficient sampling methods for discrete distributions

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