Darts, Dice, and Coins: Sampling from a Discrete Distribution (2011) (www.keithschwarz.com)

This 2011 writeup surveys practical algorithms for sampling from a discrete distribution (a “loaded die”) and highlights a surprisingly under-known, decades-old technique: the alias method. The author frames the problem as being given probabilities p0...p_{n-1} for n outcomes and clarifies machine-model assumptions (constant-time ops like floor, uniform real generation, etc.). After motivating the use cases — games, robotics sensor noise simulation, imperfect roulette — the article walks from the simplest solutions to more optimized ones, emphasizing intuition, correctness, and cost in time, space and randomness. Key technical points: for a fair n‑sided die you can sample in O(1) by taking i = floor(x*n) for a uniform x in [0,1). A straightforward method for arbitrary rational probabilities is to expand to a fair L‑sided die (L = common denominator/LCM) and map faces back to originals: generation is O(1) but initialization and memory are O(L), which can be prohibitive. The alias method, presented as the standout solution, achieves O(1) sampling with only linear preprocessing and bounded extra space per outcome, making it ideal when many samples are needed. The writeup also cautions about numerical precision and when the constant-time arithmetic assumptions may break, a practical consideration for high‑precision or constrained environments.