Assume you have a source of random binary information that has a bias but no correlation between consecutive bits. John von Neumann describes an algorithm to debias the random source and output a perfectly unbiased sequence of 1s and 0s as follows:


1. Extract two bits from the source
2. If the two bits are the same, discard them and goto 1
3. If they are different, output the first bit, discard the second one, and goto 1


A more formal description of the algorithm is: given a Bernoulli sequence $S$ where $p\neq \frac{1}{2}$, this algorithm when performed on $S$ will return a (shorter) Bernoulli sequence with $p=\frac{1}{2}$.


How would one go about proving this proposition? Thank you in advance.


Source: <http://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor>



Proof of Von Neumann's debiasing algorithm
The original article by von Neumann
(<https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf>)
does not bother to prove this.
Most likely because if the probability of "1" is $p$ and that of "0" is $q$ in a Bernoulli sequence, it was evident for him that both "10" ad "01" have probability $pq$.


