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

Publisher Website
Google Scholar
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.

This publication has 2 references indexed in Scilit: