Efficient sampling methods for discrete distributions

DOI10.1007/s00453-016-0205-0zbMath1373.62042OpenAlexW2509544990WikidataQ59527804 ScholiaQ59527804MaRDI QIDQ2408923

Karl Bringmann, Konstantinos D. Panagiotou

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0205-0

zbMATH Keywords

distributiondata structuressampling algorithmproportional samplingsubset sampling

Mathematics Subject Classification ID

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

Related Items

Randomized numerical linear algebra: Foundations and algorithms, A sketched finite element method for elliptic models, Parallel Weighted Random Sampling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic generation of discrete random variates
• Fast simulation of new coins from old
• Efficient Generation of Networks with Given Expected Degrees
• Heterogeneous Subset Sampling
• Random sampling with a reservoir
• The complexity of generating an exponentially distributed variate
• Maintaining discrete probability distributions optimally
• The Average Distance in a Random Graph with Given Expected Degrees
• Exact and Efficient Generation of Geometric Random Variates and Random Graphs
• Succinct sampling from discrete distributions