Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Efficient Sampling Methods for Discrete Distributions


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

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
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.