Von Neumann Unbiased Bits

Concept & Intuition

Suppose a coin lands on 1 with probability p and 0 with probability 1 - p. By grouping independent flips into disjoint pairs, the mixed outcomes 01 and 10 occur with identical probability (1 - p)p = p(1 - p), regardless of the value of p.

• If the pair is 01, output 0.
• If the pair is 10, output 1.
• If the pair is 00 or 11, discard the pair and retry with the next disjoint pair.

Mathematical Formulation

For a single disjoint pair, let q = P(00) + P(11) = (1 - p)2 + p2 = 1 - 2p(1 - p) be the probability of a tie (no output). Across at most m independent pairs:

P(No output in m pairs) = qm, and P(Output 0) = P(Output 1) = (1 - qm) / 2.

Whenever 0 < p < 1, the conditional probability of outputting 1 given that an output occurs is P(Output 1) / (1 - qm) = 1/2, and the uncapped expected number of individual coin flips is 2 / (2p(1 - p)) = 1 / [p(1 - p)].

Worked Example & Boundary Behavior

Suppose the bias is p = 3/4 (3 Bias quarters) and we limit our attempt to at most m = 2 pairs.

1. First, calculate the pair probabilities:
   • P(00) = (1 - p)2 = 1/16
   • P(01) = (1 - p)p = 3/16
   • P(10) = p(1 - p) = 3/16
   • P(11) = p2 = 9/16
2. Calculate the probability of no output in one pair (q):
   q = P(00) + P(11) = 1/16 + 9/16 = 10/16 = 5/8.
3. For m = 2 pairs, the total probability of no output is q2 = (5/8)2 = 25/64.
4. The probability of outputting 0 is P(01)(1 + q) = (3/16)(13/8) = 39/128.
5. The probability of outputting 1 is identically 39/128.

Because 39/128 + 39/128 + 25/64 = 1, the total mass is accounted for, and conditional on producing an output, the probability of 1 is (39/128) / (78/128) = 1/2.

Interactive Experiment

Explore the extraction protocol using the interactive Von Neumann Unbiased Bits module:

1. Set the Bias quarters control to 1 (p = 0.25) and Pair limit to 2.
2. Observe that the extraction probabilities for Output 0 and Output 1 are equal (39/128 each), while the remaining mass (25/64) corresponds to no output.
3. Increase the Pair limit and watch the No Output Probability decrease exponentially as qm.
4. Set Bias quarters to 0 or 4 (deterministic coin) to observe the boundary case where q = 1, conditional fairness is unavailable, and uncapped expected flips are positive infinity.

Interpretation & Limitations

This method requires the coin flips to be strictly independent and identically distributed within each pair. It does not guarantee fairness if the bias drifts between the first and second flip of a pair, nor is it an entropy-optimal randomness extractor (more advanced multi-bit schemes such as Elias extraction approach the Shannon entropy bound).

References

For rigorous derivations of stopping times and randomness extraction from biased coins:

• Mossel and Peres, New coins from old (arXiv:math/0304143) — Detailed analysis of coin-flipping extraction protocols and the original Von Neumann scheme.