Proof of Von Neumann's debiasing algorithm

Question

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

Answer 1

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

Answer 2

This seems to be proved in Proposition 1 in this paper by Yuval Peres.