Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
See this question where the issue is dealt with in a more general way. –  Raphael Aug 18 at 9:57
    
Here's an article on the subject. It explains how to use rejection sampling and how to reuse the "wasted" bits to speed up further rolls. –  ZeroUltimax Aug 18 at 14:15

7 Answers 7

up vote 8 down vote accepted

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.

share|improve this answer
    
You don't need 6^m, 6*m is sufficient. So you could use 5 throws to get a 5 bit number rejecting only 1/16 cases. –  Taemyr Aug 19 at 13:19
    
Rejection rate of 5% for 13 tosses is horrible, when compared to 25% for 3 tosses. Because 25% for 3 tosses will only reject 4 times(ie. spend more than 12 tosses) in 0.390625% of the cases. –  Taemyr Aug 19 at 13:23
    
@Taemyr a 5 bit number can represent 32 different values which allows you to represent a single dice (because two dices have 36 possibilities). So only 6/32 values are acceptable with a reject rate of 27/32 = 84% –  Emanuele Paolini Aug 19 at 15:07
    
@Taemyr: a reject rate of $r$ on $n$ tosses means that, in average every batch of $n$ tosses gets rejected with probability $r$. So, in average, each toss is rejected with the same rate $r$ (not depending on $n$). –  Emanuele Paolini Aug 19 at 15:18
    
Yes. And using FrankW's method that has a rejetion rate of 25% for a batch of 3 tosses, you would have a probability of 1-0.00390625 to accept by no later than the 4th batch. –  Taemyr Aug 20 at 7:10

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.

share|improve this answer
    
Wouldn't this method give greater central tendency that a true d6 would? –  Red_Shadow Aug 18 at 19:55
3  
@Red_Shadow No. Note that you don't add the coin tosses (three wouldn't be enough, then) but you pick each bit in a $k$-bit binary number by coin. Thus, you sample uniformly from $[0..2^k - 1]$ and reject numbers not from the target interval; this can only yield a uniform distribution on the target interval. –  Raphael Aug 18 at 20:18
    
If you're crafty with the rejected range, it's actually easy in this case to use that to reduce the number of necessary coin flips in the rejection case. –  Mooing Duck Aug 18 at 21:34
    
@MooingDuck you can decide whether to discard your result after 2 tosses: if it is 0,0 0,1 or 1,0 then toss again for the last bit otherwise start over –  ratchet freak Aug 18 at 21:37
1  
@NikosM. The probability to take longer than $k$ steps is decreasing towards zero exponentially, though, so the answer makes no wrong claim: it is efficient in practice, and in fact used widely. (For more complicated distributions, it's often the only known method. At all.) –  Raphael Aug 19 at 14:10

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
4  
This is always going to perform massively, massively worse than rejection sampling. For rejection sampling, you only have to flip $\lceil \log n\rceil$ coins to simulate an $n$-sided die and each set of flips succeeds with probability strictly greater than $\tfrac12$. The method you're proposing requires you to flip $\tfrac{n}{2}$ coins and each set of flips only succeeds with probability $n/2^n$. –  David Richerby Aug 18 at 16:31

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.

share|improve this answer
1  
That's just Frank's answer. –  Raphael Aug 18 at 20:17
1  
@Raphael Actually, a strict subset of Frank's answer, since Frank addresses the expected running time. –  David Richerby Aug 18 at 20:33

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).

share|improve this answer
    
Comments are not for extended discussion; this conversation has been moved to chat. –  Gilles Aug 20 at 11:55
    
@Gilles, too bad negative vote is still here, despite all the explanations and chatting (as to the correctness) that went on :p –  Nikos M. Sep 4 at 3:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.