It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),
John von Neumann gave the following procedure:
- Toss the coin twice.
- If the results match, start over, forgetting both results.
- If the results differ, use the first result, forgetting the second.
In the worst case, the procedure may not terminate.
Problem: Is it possible to design an algorithm which guarantees termination in the worst case? What is the technique to solve such an impossibility problem?