Proving von Neumann extractor correct Von Neumann extractor works as follows:


  Suppose $C$ is a biased coin, with $p = P[C = 1] &gt; P[C = 0]$ and let $b_1b_2\ldots$ be sequence of results by independent coin tosses. For $i \ge 0$ one observes $b_{2i}b_{2i+1}$. If the two bits differ then one takes $b_i'$ to be the first bit. Otherwise,one takes $b_i' = \epsilon$ the empty word. 


I would like to prove that in the sequence $b_1'b_2'\ldots$, bits are uniformly distributed. This would show that this mechanism is a real randomness extractor. 

My approach

I applied the total law of probability in this way (please let me know how can I properly write this equation in latex):

$P[b_i' = 1] = P[b_{2i}b_{2i+1} = 01] P[b_i'= 1 : b_{2i}b_{2i+1} = 01] +$

$P[b_{2i}b_{2i+1} = 10] P[b_i'= 1 : b_{2i}b_{2i+1} = 10] +$

$P[b_{2i}b_{2i+1} \neq 01,10] P[b_i'= 1 : b_{2i}b_{2i+1} \neq 01,10] = p (1-p)$

The result is the same for $P[b_i' = 0]$. 

However, then $p$ cannot be arbitrary right? Because I would need $2p(1-p) = 1$. Otherwise I have to compute the probability of $b_i' = \epsilon$, but this does not make sense because the $\epsilon$ won't appear in the final string. 

How can I formally finish this situation?
What you need to show is that the output bits are i.i.d. and uniform.

Given there is an output bit, clearly the probability that you output a zero is the same as the probability that you output a one, namely $p(1-p)$ as you indicated. So uniformity is settled.

These bits are also independent since they depend on disjoint subsequences of the input stream, which is itself assumed to be i.i.d, though non uniform.

So all you still need to prove is that bits are output at some nonzero  rate. This rate is $2p(1-p)$ per two input bits and is positive provided $p \in (0,1)$ which is the case of a non degenerate source.