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:
Choose some fairly large even integer n.
Create a table "t" containing two integers.
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]$.
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$.