coin2dice

Here's a problem that I used to give to candidates. I stopped using it seriously a long time ago since I don't believe in puzzles, but I think it's kind of fun.

1. Let's say you have a function that simulates a random coin flip. It returns “H” or “T”. This is the only random generator available. How can write a new function that simulates a random dice roll (1…6)?
2. Is there any method that guarantees that the second function returns in finite time?
3. Let's say you want to do this $$ n $$ times where $$ n \to \infty $$ . What's the most efficient way to do it? Efficient in terms of using the fewest amount of coin flips.

The first part is old, I think. The second and third part are follow up questions that I came up with.

I'll give you some time to think about it!

Don't peak!

Did you figure it out?

Solutions

1. There's a multitude of ways to do this. The easiest way to do it is probably to flip the coin three times and map the outcomes like this: (HHH, 0), (HHT, 1), (HTH, 2), (HTT, 3), (THH, 4), (THT, 5), (TTH, 6), (TTT, 7). If you end up getting HHH or TTT, you flip again.
2. Impossible! If you flip the coin $$ n $$ times then there's exactly $$ 2^n $$ outcomes. But we can't partition this space evenly into 6 buckets since $$ 3\nmid 2^n $$
3. This one is trickier. Think about it in terms of the amount of information you extract. Every coin flip extracts 1 bit, but every dice roll consumes $$ \log_2 6\approx 2.585 $$ bits. This is a lower bound – you need at least that many coin flips per dice roll.

Is there a way to achieve that lower bound? Turns out there is: basically encode a long series of coin flip as a binary representation of a number between 0 and 1, then convert it to base 6. This idea resembles Arithmetic coding. Sample code:

{% gist erikbern/22c48c622dd9e160419c %}

Hope you enjoyed geeking out with a math problem this time!