3
$\begingroup$

I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution:

$P(X = 0) = p,\;\;P(X=1)=1-p,\;\;0<p<1$,

then we can use rand() as a subroutine to create a unbiased sampler from the set {0,1}. My idea for this is along the following lines:

  1. Choose some fairly large even integer n.

  2. Create a table "t" containing two integers.

  3. Loop over $i=1,\ldots,n$ sampling $x=rand()$ for each $i$. When $i$ is even increment $t[i]$ and when odd increment $t[1-i]$.

  4. Return $0$ if $t[0]\geq t[1]$ and vice versa.

Now the expected value for $t[0]=t[1]=n/2$, so this should give a value very close to the uniform distribution. The only problem is that the set of outcomes in (4) is biased towards $0$, so for any fixed $n$, we do not get a uniform distribution, although we do get it in the limit. There has to be a way to get $n$ to depend on some random value to balance it out, but I can't figure out how.

Anyone have any other ideas how to approach this? The key in the problem was that we do not know $p$.

$\endgroup$
  • $\begingroup$ Are we given the value p? If so you can sample as you are describing (but perhaps less times). And then return 0 if the number of 0s divided by the total number of samples is less than p. so basically make step 4. $\text{Return 0 if }t[0] / n \ge p$ $\endgroup$ – Jake Dec 12 '14 at 22:12
  • $\begingroup$ No, we are not. The algorithm should remain correct even if we just substitute the calls to rand() by another function with a different bias. The point here is also to actually prove that the distribution is exactly uniform, not just close. Even if you know $p$ in practice it would be very hard to make the algorithm depend on $p$. If $p$ is for example transcendental, then you can't do any precise arithmetic and comparisons with it. $\endgroup$ – JT1 Dec 12 '14 at 22:58
  • $\begingroup$ In that case can estimate it before hand by sampling a large number of times? $\endgroup$ – Jake Dec 12 '14 at 23:00
  • $\begingroup$ I'm asking about an algorithm that gives an output distribution that is precisely the uniform distribution. I know how to solve this if I can approximate. $\endgroup$ – JT1 Dec 12 '14 at 23:09
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin $\;$ $\endgroup$ – user12859 Dec 13 '14 at 0:56
3
$\begingroup$

For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c_k$ be the number of inputs of Hamming weight $k$ which will cause you to return $1$. For your generator to be unbiased, you need $$ \frac{1}{2} = \sum_{k=0}^n c_k p^k (1-p)^{n-k} = \sum_{\ell=0}^n \left(\sum_{k=\ell}^n c_k (-1)^{\ell-k} \binom{n-k}{\ell-k} \right) p^\ell. $$ If $p$ is transcendental or of the form $a/b$ for odd $b$ then the equation $\frac{1}{2} = \sum_{\ell=0}^n d_\ell p^\ell$ has no integer solutions $d_0,\ldots,d_n$. In particular, even if you know $p$, then in these cases no finite number of samples can be used to extract even one uniformly random bit.

The standard solution, attributed (IIRC) to von Neumann, is to use the following algorithm:

  1. Repeatedly sample two biased samples $r_1,r_2$ until $r_1 \neq r_2$.
  2. Return $r_1$.

Conditioned on $r_1 \neq r_2$, the two outcomes $(r_1,r_2)=(0,1)$ and $(r_1,r_2)=(1,0)$ have the same probability, and so the result is an unbiased bit.

How efficient is this generator? The probability that $r_1 \neq r_2$ is $2p(1-p)$, and so on average you will need $1/(2p(1-p))$ samples per bit. Compare that to the optimal extractor given by Shannon's source coding theorem: extracting $n$ bits should take $n/H(p) + o(n)$ samples with high probability (when $p$ is known).

enter image description here

The plot shows that the von Neumann algorithm is reasonably good but not optimal.

$\endgroup$
  • $\begingroup$ Thanks! This was more than I asked for. Some very good info. $\endgroup$ – JT1 Dec 13 '14 at 9:22
0
$\begingroup$

I think you can roll twice each time. If you get (0,1), return yield of 0. If (1,0), return 1. Because the probability of (0,1) and (1,0) are both p*(1-p), the probability of returning 0 and 1 is identical. Of course, this algorithm has a risk of very very long loop, especially p or (1-p) is very small (like 0.01 or 0.99). But it is easier to implement.

$\endgroup$
  • 1
    $\begingroup$ This is exactly the solution that Yuval proposes in his answer and attributes to von Neumann. Please check the existing answers to questions and make sure your answer contains something new. $\endgroup$ – David Richerby Mar 28 '17 at 13:18

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.