You are at a crossroads with five roads leading away from it, and you don’t know which direction to go. You would like to choose randomly, with equal probability for each road. If your only way of making random choices is to flip a fair coin (one that could come up heads or tails with equal probability), you could assign one of the roads to each of the sequences HHH, HHT, HTH, HTT, and THH. Those outcomes are all equally likely, so you know that if you flip three times and choose the corresponding option, each one of them will have an equal chance. The problem is that there are three outcomes that are not assigned to any road, so if one of those three comes up you will have to try again. Therefore, it could take you arbitrarily long to make your decision, if you are unlucky and keep getting one of the unassigned outcomes.
You don’t have all day to stand around, so you’d like a better method. But it turns out that people have proved there is no process with a single fair coin that is guaranteed to finish in a finite amount of time and choose one of five options with equal probability.
- Suppose you could have a single unfair coin that would come up heads with probability (and tails with probability ). Is there a you can select and a procedure for using this unfair coin to choose one of the roads, each equally likely, that is guaranteed to complete in a finite number of flips?
- If so, can you determine the smallest number of flips that could be used, and what probability you want the coin to have to be able to decide in flips?
- Now suppose you are allowed to have more than one coin, each one marked with the probability that it comes up heads. What’s the fewest flips you would need to choose your direction? How many coins do you need, and what’s a set of probabilities for the coins that lets you do it in that minimal number of flips? If your set contains , that’s OK; but is there also a way to achieve that minimum with all unfair coins?