3 ms·
Getting a Fair Toss From a Biased Coin
- roundsquare 17y agoNeat 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!
- joshu 17y agoFlip 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.
- Eliezer 17y agoI was starting to think in terms of arithmetic encoding before reading the article, but the given solution is far more elegant.
- pvg 17y agoFlipping for 'sufficient' entropy is pretty much what the method does, where 'sufficient' in this case is the maximum.
- defen 17y agoSince 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.
- vegashacker 17y agovon Neumann is credited with coming up with the fair toss trick: http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...
- cruise02 17y agoThanks, I didn't know who originated that method. I added a note citing von Neumann.
- JulianMorrison 17y agoHaha! 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!