Erik Bernhardsson    About

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 times where . 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 times then there’s exactly outcomes. But we can’t partition this space evenly into 6 buckets since
  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 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:

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

Want to get blog posts over email?

Enter in your email address and get weekly emails with new articles!

Erik Bernhardsson

... is the CTO at Better, which is a startup changing how mortgages are done. I write a lot of code, some of which ends up being open sourced, such as Luigi and Annoy. I also co-organize NYC Machine Learning meetup. You can follow me on Twitter or see some more facts about me.