p58

von Neumann Extractor

Extractors here mean randomness extractors, that can generate a(n incompressible) random sequence from a `less random' (redundant) sequence.

 Von Neumann extractor is likely to be the earliest example of an extractor. Take a 01 sequence produced by a Bernoullis process $B(p,q)$ ($pq \neq 0$). The sequence is considered as the sequence of successive pairs $(a,b)$ of 01's. Then, the output of the extractor $E(a,b)$ is $a$ if $a\neq b$; otherwise, no output. Then, the produced 01 sequence obeys $B(1/2, 1/2)$. 

 Show the conclusion is indeed correct.