[AJTSheppard]

Maybe this intuitive "proof" will help.

Coins and dice and datums (solid objects with detectable outcomes) may, or may not have bias, it depends on how they were made and on manufacturing defects that resulted. But, at a minimum, such bias can oftentimes be side-stepped or bypassed.

Consider this argument from Johnny Von Neuman.

Suppose you have a single biased coin with these outcome probabilities:

A) Heads (1) 60% (Call this probability p.)

B) Tails (0) 40% (The probability of this outcome is q=(1-p), by definition.)

Now let us apply this algorithm to sequential tosses for this coin:

1) Toss the coin twice.

2) If you get heads followed by tails, return 1. (Say this outcome occurs with probability p’.)

3) If you get tails followed by heads, return 0. (The probability of this outcome is q’=(1-p’), by definition.)

4) Otherwise, ignore the outcome and go to step 1.

The bit stream that results is devoid of bias. Here’s why. The probabilities of obtaining (0 and 1) or (1 and 0) after two tosses of the coin are the same, namely p(1-p). On the other hand, if (1 and 1) or (0 and 0) are thrown, those outcomes are ignored and the algorithm loops around with probability 1 – 2p(1-p). So, the probability (p’) of getting a 1 using this algorithm after any sequential two tosses of the coin is p’ = p(1-p) + p’(1-2p(1-p)). The solution of which is p’=1/2, and since q’=(1-p’), then q’=1/2. A fair unbiased toss!

In fact, the example bias numbers given above don’t matter for the argument to hold (note that after solving for p’ it is independent of p). The outcome of the algorithm is a fair toss (in terms of the (0 and 1)-bit stream that results), regardless of the actual bias in the coin for a single toss. All the bias does is have an effect on the efficiency with which the bit stream is created, because each time we toss heads-heads or tails-tails we loop around and those two tosses are thrown away (lost). For an unbiased coin the algorithm is 50% efficient, but now has the guarantee of being unbiased. For a biased coin (or simply unknown bias) the algorithm is less than 50% efficient, but now has the guarantee of being unbiased.

This algorithm is trivial to implement for the Satoshi9000.