Independent Unbiased Coin Flips From A Correlated Biased Source: A Finite State Markov Chain

Abstract

von Neumann's trick for generating an absolutely unbiased coin from a biased one is this: 1. Toss the biased coin twice, getting 00, 01, 10, or 11. 2. If 00 or 11 occur, go back to step 1; else 3. Call 10 a H, 01 a T. Since p[H] = p[1]*p[0] = p[T], the output is unbiased. Example: 00 10 11 01 01 /spl I.oarr/ H T T. Peter Elias gives an algorithm to generate an independent unbiased sequence of Hs and Ts that nearly achieves the Entropy of the one-coin source. His algorithm is excellent, but certain difficulties arise in trying to use it (or the original von Neumann scheme) to generate bits in expected linear time from a Markov chain. In this paper, we return to the original one-coin von Neumann scheme, and show how to extend it to generate an independent unbiased sequence of Hs and Ts from any Markov chain in expected linear time. We give a right and wrong way to do this. Two algorithms A and B use the simple von Neumann trick on every state of the Markov chain. They differ in the time they choose to announce the coin flip. This timing is crucial.