Making random sources uniformly distributed

Question

How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities $prob(a)$ and $prob(b) = 1 - prob(a)$ that are unknown to us.

How do I state an algorithm that does the job and that does not consume more than an expected number of $(prob(a) \cdot prob(b))^{-1}$ symbols of $S$ between two output bits and prove its correcteness?

Answer 1

Consider this: get two elements $x_0$ and $x_1$ from $S$. If $x_0x_1$ is $aa$ or $bb$ then discard them and repeat. Otherwise return $0$ for $ab$ and $1$ for $ba$, events that occur with the same probability $p_ap_b$.

This will use $2n$ elements from $S$, $n$ the number of performed steps. The probability of stopping at each step is $p=1-2p_ap_b$. The expected value of $2n$ is therefore $$2p\sum_{n=1}^∞{n(1-p)^{n-1}}=\frac{2p}{(1-(1-p))^2}=\frac{1}{p_ap_b}\enspace.$$