de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Efficient Sampling Methods for Discrete Distributions

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44182

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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.