A few nights ago as I was drifting off to sleep I thought of the following puzzle: suppose you go out for ice cream and there are three flavours to choose from: passionfruit, coconut, and squid ink. You like all three equally, but can only choose one, and so you decide you want to make the choice randomly and with equal probability to each.

However, the only device you have to generate random numbers is a fair coin. So, how you do use your fair coin to choose between the three options of ice cream?

Of course, you can only use coin flips to make your choice. For instance, cutting the coin into three equal pieces, putting them in a bag to create a new stochastic process does not count.

### A "Solution"

A "solution" is as follows: flip the coin for each possibility. If the result contains exactly one head, such as HTT, choose the possibility that corresponds to the head. Otherwise, do not choose and try again. Since there is a nonzero probability of this happening, the probability of a choice being made approaches 1 as the number of trials approaches infinity. Of course, you might have to flip the coin in this manner several times before a decision is reached, but in practice this should work fairly well for just three options (exercise: work out the expected number of trials required to make the decision!).

Note: there are other methods that are more efficient than this one. This one only has probability 3/8 of working on the first trial, whereas other methods can have probability 3/4, for instance, and I'll leave it as an exercise to devise more efficient methods.

The problem with this "solution" is one might never come to a decision. I timed myself flipping a coin, and it takes me about 7.5 seconds to flip a coin three times. Assuming I take this much time to do one trial with no time between trials then it in a minute there is only a probability of 0.02 that I won't make a decision. So this method is fairly reasonable. I tried this while writing and I got the coconut ice cream on the second try. (Shame, I wanted to try the squid ink! Then why did I use a coin??? ahh!)

For a fixed number $ n$ of flips, dividing the various possibilities amongst three equally is impossible, so an method that has a fixed number of flips in advance does not exist.

### Bonus Question

- Suppose you are in the situation as described above, with three options and a fair coin. Is there an algorithm that will allow you to make a decision with an unknown number of flips but that is guaranteed to terminate eventually?
- Suppose you could bias your coin so that H has probabity $ p$ and T has probability $ 1-p$. Could you choose a bias (i.e. choose $ p$) so that a decision amongst three choices can now be made in a number of flips fixed in advance (but you can still choose the number of flips)?

## 4 Comments

how to calculate the expected number of trials ??

The probability that one trial will be needed is $7/8$. The probability that two trials will be needed is $(1/8)(7/8)=7/8^2$. The probability that $n$ trials will be needed is $7/8^n$. Hence, the expected number of trials is

$\tfrac{7}{8} + 2\tfrac{7}{8^2} + 3\tfrac{7}{8^3} + \cdots = \tfrac{8}{7}$

Sorry to comment on an old post, but in addition to the 3/4 option (which is pretty well-documented in cryptography and perhaps other CS sub-fields as trivial rejection sampling on bitstrings, with the happy property that any power of two is "free" to sample from), my immediate thought was "…what about arithmetic coding?"

After all, arithmetic coding is really all about deriving an element of ? from a (potentially) unbounded sequence of bits, and committing to digits thereof as they become sufficiently stable. If the real is interpreted in base 3, then one simply takes the first digit once it stabilizes.

AFAIK, arithmetic coding yields the entropically optimal solution.

That's very interesting, I'll have to take a look at that. I've never heard of arithmetic coding. Thanks for the comment!

Edit/addendum: no problem with commenting on old posts!