Forwarding you to www.keithschwarz.com

Darts, Dice, and Coins

In the introduction to this writeup, I used the term "loaded die" to describe a general scenario where there are is a finite set of outcomes, each of which has some associated probability. Formally, this is termed a discrete probability distribution , and the problem of simulating the loaded die is called sampling from a discrete distribution . To describe our discrete probability distribution (loaded die), we will assume that we are given a set of n probabilities $p_0, p_1, ..., p_{n - 1}$ associated with outcomes $0, 1, ..., n - 1$. Although the outcomes can be anything (heads/tails, numbers on a die, colors, etc.), for simplicity I'll assume that the outcome is some positive natural number that corresponds to the given index.