How to simulate a die given a fair coin

Question Detail: 

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number encoded by the k-length bitstring to outputs of the die by dividing the range $[0,2^k-1]$ into 6 intervals each of length $m$. However, this is not possible, since $2^k$ has two as its only prime factor but the prime factors of $6m$ include three. There should be some other simple way of doing this, right?

Asked By : probability_guy

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29204

Answered By : Emanuele Paolini

To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$ die flips, where $m$ is the largest number so that $6^m < 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ you must reject the value and repeat all $n$ flips.

You can implement a function which returns a single die flip by making $n$ coin flips and then cache the result for the following $m-1$ die flip requests.

The interesting point is that some values of $n$ are better than others because they have a less rejection rate. Here is a list of good values (i.e. values which have lower rejection rate than the previous ones):

n m r 3 1 0.25 8 3 0.15625 13 5 0.05078125 44 17 0.0378308072686 75 29 0.0247036782182 106 41 0.0113974522704 243 94 0.00933096248381 380 147 0.00726015308463 517 200 0.00518501504347 654 253 0.00310553931213 791 306 0.00102171682348 

obtained with the formulas: $$ m = \lfloor {n\log_3 2} \rfloor \\ r = 1 - \frac{3^m}{2^n}$$.

The first row corresponds to the answer of @FrankW with a reject rate of 25%. The following numbers are nice: $n=8$ and $n=13$ can both be kept in a single integer static variable. In particular the reject rate of $n=13$ is only 5% which is a sensible improvement with respect to 25% and makes this a good candidate for a possible implementation.