Von Neumann Unbiased Bits
Extract a fair bit from a biased coin and measure the chance that a finite attempt produces no output.
Free theory articleExtract a fair bit from a biased coin and measure the chance that a finite attempt produces no output.
Concept & interpretation
The Von Neumann extractor produces an unbiased binary bit from independent and identically distributed (IID) flips of a coin with unknown bias p.
Interactive Experiment
Explore the extraction protocol using the interactive Von Neumann Unbiased Bits module:
- Set the Bias quarters control to 1 (
p = 0.25) and Pair limit to 2. - Observe that the extraction probabilities for Output 0 and Output 1 are equal (
39/128each), while the remaining mass (25/64) corresponds to no output. - Increase the Pair limit and watch the No Output Probability decrease exponentially as
qm. - 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.