Getting a Fair Toss From a Biased Coin

http://www.billthelizard.com/2009/09/getting-fair-toss-from-biased-coin.html

by spydez • 17 years ago

40 8 17 years ago

joshu• 17 years ago

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.

defen• 17 years ago

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.

Eliezer• 17 years ago

I was starting to think in terms of arithmetic encoding before reading the article, but the given solution is far more elegant.

pvg• 17 years ago

Flipping for 'sufficient' entropy is pretty much what the method does, where 'sufficient' in this case is the maximum.

vegashacker• 17 years ago

von Neumann is credited with coming up with the fair toss trick:

http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...

cruise02• 17 years ago

Thanks, I didn't know who originated that method. I added a note citing von Neumann.

roundsquare• 17 years ago

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!

JulianMorrison• 17 years ago

Haha! I saw the title and thought "how would I..." and reinvented it in seconds, almost (mine differed in that I'd allocate the H or T value of each pair arbitrarily by fiat ahead of time).

Edit: oops! I failed to reinvent discarding by pairs. That makes my attempt a fail. D'oh!

Getting a Fair Toss From a Biased Coin

Related Stories