# Proving von Neumann extractor correct

Von Neumann extractor works as follows:

Suppose $$C$$ is a biased coin, with $$p = P[C = 1] > 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?

• Getting it from the horse's mouth might help -> mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf – Paul Uszak Nov 12 '18 at 21:34
• I dont understand the $2p(1-p)=0$ condition you claim. See my answer. – kodlu Nov 13 '18 at 0:08
• Sorry @kodlu, I meant = 1 (sum of all possible outcomes should be 1) – Javier Nov 13 '18 at 11:03
• Well it needs to be normalised by the conditional probability that there is an output. – kodlu Nov 13 '18 at 20:00
• @Rodrigo In case it was not clear yet: yes, $p$ can be arbitrary, just not exactly $0$ or $1$, and this is exactly the point with Von Neumann extractor algorithm. – Vadym Fedyukovych Nov 14 '18 at 12:06

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