Independent unbiased coin flips from a correlated biased source - a finite state Markov chain (Q1822415)

Von Neumann's trick for simulating an absolutely unbiased coin by 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 \(\Pr [H]=\Pr [1]\Pr [0]=\Pr [T]\), the output is unbiased. Example: OO 10 11 01 01\(\to HTT\). \textit{P. Elias} [Ann. Math. Stat. 43, 865-870 (1972; Zbl 0245.65003)] 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 wrong and a right 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.