Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I write a Las Vegas algorithm (called GenUnbiasedBit) that returns 1 or 0 with equal (nonzero) probability, using calls from GenBiasedBit as a source of randomness? I'm not really sure how to approach this problem. Since 1 and 0 must be generated with equal chance, I'm assuming they must both have a 50/50 chance of being selected. Since this is a Las Vegas algorithm, I'm not sure how to guarantee that its output is correct, if we don't know the probability of GenBiasedBit generating a 1 or 0.
1 Answer
We can simulate an unbiased coin as follows. Toss a pair of coins, and repeat until they produce different outcomes. If the outcome was H,T (heads followed by tails) output heads, and if it was T,H output tails.
Conditioning on the event that the above simulation halts (i.e. at some iteration $i$ we receive different outcomes), then both H/T have equal probability. The probability of a "bad output" in a single iteration (same result from both coins) is $p^2+(1-p)^2$, which is less than $1$ for $p\in (0,1)$. Thus, the probability of "failure" after $n$ iterations is bounded by $(1-2p(1-p))^{-n}$.