Bringmann, Karl; Panagiotou, Konstantinos
(2017):
Efficient Sampling Methods for Discrete Distributions.
In: Algorithmica, Vol. 79, No. 2: pp. 484508

Full text not available from 'Open Access LMU'.
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) First, we consider the problem of sampling from the distribution where the ith event has probability proportional to p(i). Second, we study the problem of sampling a subset which includes the ith event independently with probability . For both problems we present on two different classes of inputssorted and general probabilitiesefficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a tradeoff between preprocessing and query time, which we prove to be asymptotically optimal everywhere.