A Die from a Coin

What’s going on

The die from your board game is lost, but you have a coin. Can you still roll a fair 1 to 6?

At first it looks impossible. Flip a coin five times and each of the 32 possible sequences has a chance of 1/32, so any rule based on them gives a chance of something out of 32. One sixth is not something out of 32, or out of any other power of two. With a fixed number of flips, a fair die cannot be done.

The way out is to allow the number of flips to change from roll to roll.

Squeeze the line

Draw a line from 0 to 1 and cut it into six equal parts, one for each face. That is the top row of the scene above. Now flip the coin:

• heads: keep the left half of the line;
• tails: keep the right half.

Then flip again and halve the piece you kept. As soon as the piece fits inside one of the six parts, stop: that part is your roll.

In the scene, the opening example went tails, heads, tails, tails. The pieces were 1/2 to 1, then 1/2 to 3/4, then 5/8 to 3/4, then 11/16 to 3/4. The last one lies inside the fifth part, which runs from 4/6 to 5/6, so the roll is a 5.

Why is it fair? The flips pick a random point on the line, one binary digit at a time, and the point lands in each part with a chance equal to the part’s length: one sixth. We simply stop as soon as we know which part it is in.

Press Run 10,000. Every face comes up close to 16.7% of the time.

Any chance at all

Choose a 1 in 3 chance in the menu. Now the line has a single cut at 1/3: left of it means yes, right of it means no. The same squeezing works for any chance at all.

And here is the surprise in the title of the original article: it takes only two flips on average, whatever the chance is.

Why? With one cut, each flip splits the piece into two halves, and at most one of them can contain the cut. So each new flip has at least a one-in-two chance of finishing the job. The first flip is always needed, a second is needed at most half the time, a third at most a quarter of the time, and so on:

1 + ½ + ¼ + ⅛ + … = 2.

Chances that sit exactly on a halving point, like 1/2 or 3/8, finish even sooner. Every other chance takes exactly two flips on average. Run 10,000 draws and watch the average line settle near 2.00.

A die has five cuts, and the first three flips are always needed. Its exact average is 4 flips. That is the same as a simpler method: flip three times, read the result as one of eight sequences, use six of them as the faces, and start again on the other two.

Try it yourself

1. A quick one in three

A friend suggests: flip twice; two heads means yes; heads-tails or tails-heads means no; two tails means start again. Is the chance of yes exactly one in three? How many flips does it take on average?

Answer

Yes, it is fair: of the three results that count, all equally likely, one means yes. But a round succeeds only 3 times in 4, so you need 4/3 rounds on average, which is 8/3 ≈ 2.67 flips. Squeezing the line needs only 2.

2. Unlucky streaks

With the squeezing method and a chance of 1/3, what is the chance that you need more than ten flips?

Answer

After ten flips the piece is 1/1024 of the line, and you still have to go on only if the cut at 1/3 is inside it. Only one of the 1024 possible pieces contains it, so the chance is 1 in 1024. Long streaks are possible, but very rare.

3. Wait for tails

Here is another rule: flip until the first tails. If it took an even number of flips, say yes; if odd, say no. What is the chance of yes?

Answer

The first tails comes on flip 2 with chance 1/4, on flip 4 with chance 1/16, on flip 6 with chance 1/64, and so on. These add up to exactly 1/3. Written in binary, 1/3 is 0.010101…, and the rule says *yes* when the first tails falls on a place where the binary digit is 1. The same works for any chance, and on average it also takes two flips.

Go deeper

• The opposite problem has a famous answer by John von Neumann: to get a fair result from a biased coin, flip it twice; heads-tails means heads, tails-heads means tails, and two equal flips mean try again.
• In 1976 Donald Knuth and Andrew Yao found the fewest coin flips needed on average for any lot. For a fair die the best possible average is 11/3, a little less than 4.
• Computers face the same problem: their random numbers come as bits, and turning bits into a fair number from 1 to 6 needs a “try again” step like the ones here.