Getting a Fair Toss From a Biased Coin

billthelizard.com

40 points·spydez··8 comments

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

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.

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.

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!

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!

Reply on news.ycombinator.com