Fair Outcome from an Extremely Biased Coin

Worked Solution

How to Think About It: The core tension is between simplicity and efficiency. Von Neumann's trick is elegant and easy to remember, but it wastes almost all your flips when the coin is extremely biased. At $p = 0.99$, only about 1% of flip-pairs produce a usable result. The information theory tells you exactly how bad this waste is and what the best you can possibly do looks like. And if you need a hard guarantee on the number of flips (no "keep trying until it works"), you need a fundamentally different approach -- block-based extraction.

Quick Estimate: For $p = 0.99$, each flip carries $H(0.99) = -0.99 \log_2(0.99) - 0.01 \log_2(0.01) \approx 0.0808$ bits of entropy. So the theoretical minimum is $1/0.0808 \approx 12.4$ flips per fair bit. Von Neumann uses pairs and succeeds with probability $2p(1-p) = 2(0.99)(0.01) = 0.0198$ per pair, so the expected number of flips is $2/0.0198 \approx 101$. That is about 8x worse than the information-theoretic limit -- a huge gap driven by the extreme bias.

Part 1 -- Von Neumann's Method:

Flip the coin twice. There are four outcomes: - $HH$: probability $p^2$ - $HT$: probability $p(1-p)$ - $TH$: probability $(1-p)p$ - $TT$: probability $(1-p)^2$

The key symmetry: $P(HT) = P(TH) = p(1-p)$, regardless of $p$. So map $HT \to 0$ and $TH \to 1$, and discard $HH$ and $TT$ (repeat). Each accepted pair gives one perfectly fair bit.

The probability of acceptance per pair is $2p(1-p)$. For $p = 0.99$: acceptance rate $= 0.0198$, so expected flips per fair bit $= 2 / 0.0198 \approx 101$.

Worst case is unbounded because every pair could land $HH$ (which happens with probability $0.9801$). You might need to repeat many times. There is no finite upper bound on the number of flips.

Part 2 -- Elias's Method and the Entropy Limit:

The Shannon entropy per flip is:

$$H(p) = -p \log_2 p - (1-p) \log_2(1-p)$$

For $p = 0.99$:

$$H(0.99) = -0.99 \log_2(0.99) - 0.01 \log_2(0.01) \approx 0.0144 + 0.0664 = 0.0808 \text{ bits}$$

So the theoretical minimum is $1/H(0.99) \approx 12.4$ flips per fair bit. No algorithm can beat this.

Elias's method works by treating the sequence of flips as specifying a point in $[0, 1)$ using arithmetic coding with the biased distribution. As flips accumulate, you maintain an interval $[a, b)$ that narrows with each flip. Whenever the interval is entirely contained within $[0, 0.5)$ or $[0.5, 1)$, you output a fair bit (0 or 1 respectively) and rescale. This extracts nearly $H(p)$ fair bits per flip in expectation, approaching the information-theoretic limit. Peres's iterative method (1992) further improves on this by recycling the "discarded" pairs from von Neumann's method, feeding them back through the extraction process recursively.

However, like von Neumann, Elias's method has no guaranteed stopping time -- the interval can straddle 0.5 for arbitrarily many flips.

Part 3 -- Block-Based Scheme for Guaranteed Termination:

Flip the coin $k$ times. The sequence of outcomes is one of $2^k$ possible strings, but these strings are not equally likely. Group strings by their number of heads: a string with $j$ heads has probability $p^j (1-p)^{k-j}$, and there are $\binom{k}{j}$ such strings.

Within each group of $\binom{k}{j}$ equally-likely strings, you can extract fair bits by: - Assign each string a number from $0$ to $\binom{k}{j} - 1$ - Output $\lfloor \log_2 \binom{k}{j} \rfloor$ fair bits by using the string's index in binary - Discard one or more strings if $\binom{k}{j}$ is not a power of 2

The total number of extractable fair bits from $k$ flips is approximately:

$$\sum_{j=0}^{k} \lfloor \log_2 \binom{k}{j} \rfloor \cdot P(\text{group } j \text{ is selected})$$

For $p = 0.99$ and $k$ flips, the dominant group has $j \approx 0.99k$ heads. To get at least one fair bit, you need $\binom{k}{j} \geq 2$ for the most likely $j$ values. Since $\binom{k}{k-1} = k$, even $k = 2$ gives you $\binom{2}{1} = 2$ strings (one head, one tail), so you can extract one fair bit from those -- but that group only occurs with probability $2(0.99)(0.01) = 0.0198$.

A practical choice: take $k$ large enough that the typical group near $j = 0.99k$ has a large binomial coefficient. For $k = 100$, the most likely outcome is 99 heads, and $\binom{100}{99} = 100$, giving $\lfloor \log_2 100 \rfloor = 6$ fair bits. The probability of getting exactly 99 heads is $\binom{100}{99}(0.99)^{99}(0.01)^1 \approx 0.370$. Groups with 97-100 heads cover most of the probability mass, and each has a large enough binomial coefficient to extract several fair bits.

The key trade-off: the block size $k$ is your hard cap on flips. Larger $k$ gives more efficient extraction (approaching the entropy limit), but you always terminate in exactly $k$ flips.

Answer: Von Neumann's method uses the symmetry $P(HT) = P(TH)$ but requires about 101 expected flips at $p = 0.99$ with unbounded worst case. The entropy limit is $\approx 12.4$ flips per fair bit, approached by Elias's arithmetic coding or Peres's recursive method -- but these also lack guaranteed termination. For a hard worst-case bound, use a block of $k$ flips and extract fair bits from the equally-likely permutations within each heads-count group. At $k = 100$, you get about 6 fair bits with certainty in exactly 100 flips.