Efficient Sampling Methods for Discrete Distributions

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