# Making random sources uniformly distributed

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?

• If $q = 1-p$, $p$ and $q$ are hardly independent. – Raphael May 19 '12 at 14:52

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.$$
• Nice. Although the question asks for a solution does not consume more than $(p_ap_b)^{-1}$ symbols; this solution has no bound on this quantity. – Raphael May 19 '12 at 19:11
• No, in the last paragraph, the OP asked (somewhat awkwardly) for an algorithm whose expected number of trials is at most $1/p_ap_b$. For almost all probabilities $p_a$, there is no exact algorithm with a finite upper bound on the worst-case number of trials. – JeffE May 19 '12 at 19:50