Cameron Freer

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

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 random coin flips. We prove that this algorithm, which we call the Fast Loaded Dice Roller (FLDR), is highly efficient…