How to simulate a die given a fair coin

Question

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?

Answer 1

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.

Answer 2

What you can do, is to employ a method called rejection sampling:

• Flip the coin 3 times and interpret each flip as a bit (0 or 1).
• Concatenate the 3 bits, giving a binary number in $[0,7]$.
• If the number is in $[1,6]$, take it as a die roll.
• Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.

Since $\frac 68$ of the possible outcomes lead to termination in each set, the probability of needing more than $l$ sets of flips to get a die roll is $(1-\frac 68)^l = \dfrac 1{4^l}$. Hence, this method is efficient in practice.

Improvements:

@Angel's answer points out, that the number of coin flips in each set but the first can be reduced from 3 to 2, by using the distinction between a $0$ and a $7$ as the first bit for the next set.

@Emanuele Paolini explains, how you can reduce the number of rerolls, if you need multiple die rolls.

Answer 3

An alternative to rejection sampling (as described in FrankW's answer) is to use a scaling algorithm, that takes into account an answer of [7,8] as if it was another coin flipping.

There is a very detailed explanation at mathforum.org, including the algorithm (its NextBit() would be flipping your fair coin).

The case for throwing a dice with a fair coin (sampling 2 → 6) is easier than the generic algorithm. You just take a failure (7 or 8) as another coin input and perform two more flips.

Answer 4

A possibly simpler explanation of improved rejection sampling.

I am giving this explanation as it may hopefully help simplify understanding or analysis of probabilities in some situations.

FrankW suggests using rejection sampling, flipping the coin three times, keeping the result if it is in the right range, or repeating the three flips otherwise, until success.

Ángel suggests to save one flip on each trial, replacing it by a the binary choice remaining from the two unused values of the previous set of three.

This means really that one bit of information was produced with the first three flips, that did not need to be produced. More precisely, you should need to flip the coin only twice to know whether the current set of flips will be successful.

Knowing whether the current set of flip will be successful is the only probability that matters, since interpreting a successful set of flip is probability independent. And this can be known before all the flips are completed for that set.

This can be achieved in at least two ways, or more precisely in two different interpretations of the flips. There may be others.

Grouping results in pairs

The idea is to consider only three values (1,2), (3,4) and (5,6) represented by any three double-flip configurations, say TT, TH, HT. Then, you can apply rejection sampling with double-flips, repeating whenever you get the failure configuration HH.

Once you get one of the three successful configurations, you just flip the coin once more to decide whether you should take the first or the second value of the corresponding pair.

Early detection of flip-set failure

The idea is to use a slightly different reading of the three-flip configuration. If Head and Tail are interpreted as 1 and 0, then a configuration should correspond to the binary interpretation plus one. That is TTT (i.e. 000) corresponds 1, HTH (i.e. 101) corresponds 6, HHT (i.e. 110) and HHH (i.e. 111) corresponds to 7 and 8, or anything outside [1,6].

Then we know that the flip-set is succeeding or failing with only the first two flips. If they produce HH, the flip set fails independently of the last flip. So it can be skipped.

I think that early detection can always be used as an explanation, but depending on the number of faces on your simulated dice, failure detection may happen after a variable number of flips.

For example for a 10 faces dice you need in principle a flip set of 4 flips, with 6 configurations corresponding to failure. The trick is to have all the failure configurations at the high end of the sequence of binary values as follows:

TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

Successful configurations correspond to range [1, 10] and failures to range [11,16].

Then you fail when the first two flips give HH, or when the first three give HTH, without having to even attempt the missing flips of the set.

If you do not fail, you just terminate the set of flips.

Answer 5

Another approach to simulate a roll of a dN using a dM (in the case of the specific question asked a d6 using a d2) is to partition the interval [0, 1) into N equal intervals of length 1/N, [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, N).

Use the dM to generate a base-M fraction, 0.bbbb..., in [0, 1). If that falls in [(i-1)/N, i/N), take i as the roll of the dN. Note that you only have to generate enough base-M digits of the fraction to determine which interval it is in.

Answer 6

I came across this thread looking to validate if the solution I came up with with when my kids wanted to play a game requiring a die but one could not be found.

Take three coins and write numbers like this:

	Coin 1	Coin 2	Coin 3
Head	2	0	0
Tail	1	1	3

Flip the coins and add up the value, but reject if all heads or all tails. This prevents 2 and 5 from having two possible solutions. Should be fair, and doesn't require considering the coin order or doing any binary math. Easy enough for my 5 year old.

Coin 1	Coin 2	Coin 3	Sum
H - 2	H - 0	H - 0	n/a
H - 2	H - 0	T - 3	5
H - 2	T - 1	H - 0	3
H - 2	T - 1	T - 3	6
T - 1	H - 0	H - 0	1
T - 1	H - 0	T - 3	4
T - 1	T - 1	H - 0	2
T - 1	T - 1	T - 3	n/a

Answer 7

I would flip the coin three times and interpret the outcome as a binary number, rejecting outcomes out of range.

For example, let heads be a 1 and tails be 0. If you flipped it three times and got heads, tails, heads, you'd have binary 101, which is 5 in decimal. HHT = 110b = 6. TTT = 000b = 0 and HHH = 111b = 7, both of which are out of range and would be rejected, and you would reflip for all the digits.

Answer 8

There are two well-known approaches to this. One is "rejection sampling". For example, use three bit to pick one out of six values, trying again for the two extra samples. Or use 14 bits (8192 values) to select 5 values from 1 to 6 (7776 possibilities), trying again in 13 out of 256 cases.

The other is using the decompression part of a compression / decompression algorithm: With arithmetic coding, a sequence of random values from 1 to 6 can be compressed with almost no redundancy. Generate the compressed sequence at random, and decompress it. This is a lot more complicated, but will practically not require any additional random numbers.

Answer 9

Sorry in advance if the explanation is superfluous. I wasn't sure how much detail to go in to or how easy the concept was to understand.

Say you have three coins (fair coins). If you incrementally assign a value to each side of each coin, you'll have six values.

Like so: On the first coin, heads is 1 and tails is 2. On the second coin, heads is 3 and tails is 4. On the third coin, heads is 5 and tails is 6.

Flipping the coins will leave you with a set of three numbers, your current set. Now, your current set will become your previous set and you will repeat the process to get a new set of three numbers.

Continue doing this until one and only one number matches from your current to previous set. That's your number.

So if you got [ heads, tails, heads ] for the current set, that'd be [ 1, 4, 5 ]. Now you flip them again and your current set is [ 2, 4, 5 ]. Two matches. No good. Try it again. You get [ 2, 3, 6 ]. Only one match. Your number is two.

There will be an equal chance that any given number will appear, but it's not particularly cost-effective, given that there's only a 3/32 change that any given pair of sets will be successful (only one match). So on average, the algorithm would have to repeat about ten times. Also, it's not easily generalizable to odd-numbered die.

At the very least, maybe it's food for thought. Very interesting question.

Answer 10

Unfortunately one cannot (faithfuly) simulate a (fair) die using (sequences of) fair coin(s).

Simply because the event space of a die has a dimensionality of $6$ and this cannot be exactly matched by a power of $2$ (which is what the event space of a fair coin provides).

But one can do this with a fair "tri-coin" (if such a term can be used). Meaning a coin with 3 outcomes. And a simple 2-coin, so the joint space of these 2 coins matches exactly the event space of the die.

Rejection sampling (as mentioned in some answers) may provide an approximate simulation indeed. But it will still have an amount of error or mis-match of probabilities (in finite time). So if one wants to actually match the event spaces of these 2 systems, there will be cases it will not work.

In probabilistic simulation (of which rejection sampling is an example), generated typical sequences do indeed exhibit the relative elementary probabilities (in this case the event space of a die). However (as mentioned in comments) each of these typical sequences can contain arbitrarily long sub-sequences of exactly the same outcomes. This means that in order to use rejection sampling (in some cases) either it can take arbitrarily long or the generated distribution will be biased (i.e not fair die), due to over-representation or under-representation of some parts of its event space. if this was not the case, then a deterministic algorithm would be possible which would exactly match the event spaces of a die and a coin (which do not match by dimensionality).

Answer 11

Take 6 coins. Each coin gets 1 point for tails, 2 points for heads. Dump out the coins and count up the total based on this idea.