# Generating uniformly random bits from a stream of arbitrarily biased bits

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.

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}$.