Simulating a Fair 7-Sided Die: A Tiny Rejection Sampling Example

This isn’t really an ML topic, but it’s something that came to my mind on the train ride home from work, and I realized that it is incredibly simple:

Rolling two six-sided dice produces 36 equally likely ordered outcomes.
To simulate a fair seven-sided die, we would like to divide these outcomes evenly into seven groups.

Since 7*5=35 this is almost possible: we can assign five outcomes to each value in {1,…,7}, leaving exactly one outcome unused. We simply discard that outcome and roll again.

In practice, we reject the outcome (6,6). For all remaining rolls, if the second die is in {1,…,5}, we return the value of the first die, producing values 1 through 6 with equal probability. If the second die is 6, we return 7.

Because each of the seven values is produced by exactly five equally likely outcomes, the resulting distribution is uniform. This is a simple example of rejection sampling in a discrete setting.

The idea above is implemented in the following code, along with the resulting output from 10 000 000 trials: