After I saw Melissa’s coin-based problem last week, I knew I had to follow up with one of my own:
You have been cloned! Given the circumstances, you may as well change your name and move to Chicago. Double You has the same idea, and they even picked the same pseudonym you wanted. Well, one of you has to stay put and live your original life—who will it be?
Double You pulls a coin out of their pocket. “Easy. Heads I move to Chicago, tails you move to Chicago.”
You pull an identical coin out of your pocket. “No way. We both know this is a rigged coin.”
It’s true. Both the coins unfairly weighted. The coins come up heads 75% of the time, and tails 25% of the time. There is a 0% chance that either coin produces a tie—any outcome besides heads or tails.
To solve this problem, describe a system of coin flips which uses only these unfair coins which nevertheless produces a fair contest. Your coin flipping scheme must satisfy the following properties:
- It is 50% likely that you win the contest and change your identity.
- It is 50% likely that you lose the contest and do not change your identity.
- It is 0% likely that there is no winner.
Dynamical Mathematical Gazette 
In principle, one can sample uniformly from n outcomes by identifying them with n equilikely mutually disjoint events from some random process. As long as these events have a combined non-zero probability, one can just repeat the random process until one of the events occurs. In this case, we can flip both coins, noting their order, and then the outcomes HT and TH are equilikely. Expected runtime can be an issue in practice, but given the high-stakes, once-and-for-all nature of this context, I’m sure both parties are happy to wait.
Is there a more efficient solution?
LikeLike