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,\dots ,p_n$ . First, we consider the problem of sampling from the distribution where the i‐th event has probability proportional to $p_i$ . Second, we study the problem of sampling a subset which includes the i‐th event independently with probability $p_i$ . For both problems we present on two different classes of inputs–sorted and general probabilities–efficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a trade‐off between preprocessing and query time, which we prove to be asymptotically optimal everywhere.