Getting a Fair Toss From a Biased Coin(billthelizard.com)
billthelizard.com
Getting a Fair Toss From a Biased Coin
http://www.billthelizard.com/2009/09/getting-fair-toss-from-biased-coin.html
8 comments
Flip the coin to get sufficient entropy, then take the md5 of the bits generated. That should give you some number of virtual flips as output.
Since you can't end up with more entropy than you started with by using a deterministic process, if you're going to do that you may as well use the bits to seed a random number generator.
I was starting to think in terms of arithmetic encoding before reading the article, but the given solution is far more elegant.
Flipping for 'sufficient' entropy is pretty much what the method does, where 'sufficient' in this case is the maximum.
von Neumann is credited with coming up with the fair toss trick:
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...
Thanks, I didn't know who originated that method. I added a note citing von Neumann.
Neat idea. But how do you convince your friends to do this?
A: I call heads.
<flip>
B: It came up tails! I win!
A: No, wait, we're not done yet. We need to flip it again, if it comes up tails, we start over.
B: What? No, give me my doughnut!
A: I call heads.
<flip>
B: It came up tails! I win!
A: No, wait, we're not done yet. We need to flip it again, if it comes up tails, we start over.
B: What? No, give me my doughnut!
Edit: oops! I failed to reinvent discarding by pairs. That makes my attempt a fail. D'oh!