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 vou 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.
Blum REF shows how to extract a fair coin from a Markov chain.
Independent Unbiased Coin Flips From A Correlated Biased Source: A Finite State Markov Chain
FOCS
Mathematics Computer Science