Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
Pregunta
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 hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange