Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange