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?

  • $\begingroup$ If $q = 1-p$, $p$ and $q$ are hardly independent. $\endgroup$
    – Raphael
    May 19, 2012 at 14:52

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

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    May 19, 2012 at 19:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – JeffE
    May 19, 2012 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.