3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If $q = 1-p$, $p$ and $q$ are hardly independent. $\endgroup$ – Raphael♦ May 19 '12 at 14:52
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\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 '12 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 '12 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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