The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions

Feras A. Saad, Cameron E. Freer, Martin C. Rinard +1

This paper introduces a new algorithm for the fundamental problem of generating a random integer from a discrete probability distribution using a source of independent and unbiased…