# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Efficient Sampling Methods for Discrete Distributions

##### 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 (*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.