Maintaining discrete probability distributions optimally

DOI10.1007/3-540-56939-1_77MaRDI QIDQ4630265zbMATH OpenOpenAlexFDO

Authors Torben Hagerup, K. Mehlhorn, J. Ian Munro

Publication date 29 March 2019

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

Full work available at URL https://doi.org/10.1007/3-540-56939-1_77

zbMATH Keywords

abstract data typebase segmentgarbage collectorgeneralized distributionnaive algorithmtable lookup

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Efficient sampling methods for discrete distributions
• Efficient sampling methods for discrete distributions
• scientific article; zbMATH DE number 437561
• Dynamic generation of discrete random variates
• Dynamic sampling from a discrete probability distribution with a known distribution of rates

Cites work

• Fast algorithms for generating discrete random variates with changing distributions
• Generating Markov-Chain Transitions Quickly: I
• scientific article; zbMATH DE number 437561 (Why is no real title available?)
• scientific article; zbMATH DE number 3815002 (Why is no real title available?)
• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 3522951 (Why is no real title available?)
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(18)

• Dynamic generation of discrete random variates
• A compact data structure for representing a dynamic multiset
• Optimal assumptions for discreteness
• Dynamic sampling from a discrete probability distribution with a known distribution of rates
• Rescorla-Wagner models with sparse dynamic attention
• Efficient sampling methods for discrete distributions
• Efficient sampling methods for discrete distributions
• scientific article; zbMATH DE number 437561 (Why is no real title available?)
• A nearly linear-time PTAS for explicit fractional packing and covering linear programs
• Practical algorithms for generating a random ordering of the elements of a weighted set
• Parallel Weighted Random Sampling
• scientific article; zbMATH DE number 7559204 (Why is no real title available?)
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• scientific article; zbMATH DE number 7651215 (Why is no real title available?)
• More efficient parallel flow algorithms
• Maintaining discrete probability distributions in practice
• Optimal resizable arrays
• Spanning adjacency oracles in sublinear time

This page was built for publication: Maintaining discrete probability distributions optimally

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