Efficient Sampling Methods for Discrete Distributions

Bringmann, Karl; Panagiotou, Konstantinos

doi:10.1007/978-3-642-31594-7_12

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Efficient Sampling Methods for Discrete Distributions

MPS-Authors

/persons/resource/persons44182

Bringmann, Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Bringmann, K., & Panagiotou, K. (2012). Efficient Sampling Methods for Discrete Distributions. In A. Czumaj, K. Mehlhorn, A. M. Pitts, & R. Wattenhofer (Eds.), Automata, Languages, and Programming (pp. 133-144). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-BBDB-2

Abstract

We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p_1,...,p_n. We consider the problem of sampling a subset, which includes the i-th event independently with probability p_i, and the problem of sampling from the distribution, where the i-th event has a probability proportional to p_i. For both problems we present on two different classes of inputs � sorted and general probabilities � efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.