Implement a fair coin using only a coin of unknown bias

You have a function `biased_coin()` that returns `1` (heads) with some fixed probability $p$ and `0` (tails) otherwise. Calls are independent and $p$ never changes, but its value is unknown; you only know that $p$ is strictly between 0 and 1. Using no source of randomness other than `biased_coin()`, implement `fair_coin()`, which returns `1` and `0` with probability exactly one half each. This was asked in a coding round, where the interviewer cared most about a working implementation: a short, convincing argument for why the result is fair is enough, and no formal proof is needed. ```hint Equal by symmetry Look for two outcomes of a small group of flips that must be equally likely whatever the value of p. ``` ```hint When the flips are no use Decide what fair_coin() should do when the flips come out as something other than your two symmetric outcomes. ``` ### Constraints and Clarifications - `biased_coin()` is the only randomness available; `random`, `os.urandom` and similar sources are off limits. - The method may not depend on the value of $p$, which is unknown. - Successive results of `fair_coin()` must be independent fair bits, not only fair on average. ### Clarifying Questions - Is $p$ guaranteed to be strictly between 0 and 1? A coin that always lands the same way cannot be made fair. - Must one fair flip use a bounded number of biased flips, or is a bounded expected number enough? - May `fair_coin()` take the biased coin as a parameter, so tests can inject a scripted coin? ### What a Strong Answer Covers - A procedure whose fairness holds for every p, with the one-line probability argument - The expected number of biased flips per fair flip as a function of p, and the fact that the worst case is unbounded - An implementation that calls the biased coin exactly as the argument assumes, with no extra or reused flips - Testing: a scripted coin for deterministic unit tests and a statistical check of fairness and independence - Recognizing subtly broken variants and explaining why they are biased ### Follow-up Questions - A teammate's version keeps the second flip of a matching pair and compares it with the next flip. Is the output still fair? - How many output flips, and which test, would you need to catch a `fair_coin()` that returns heads 51% of the time? - Can you get more fair flips out of the same biased flips by reusing the information in the pairs you discard? - Using `fair_coin()`, how would you produce a uniformly random integer from 0 to 5?