Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If I set the slider to 50% then it still wants me to flip 3 times. At 50% one flip would do. There should be at least an exception for that situation, I can't imagine I'm being alone in testing the edge cases first.


The point is, you don't know ahead of time what the bias is. In that case, you have to keep flipping until you get a head followed by a tail, or a tail followed by a head. If the coin happens to have no bias, you should expect to flip 3 times before you get one of those results.


Three flips is correct. The idea, which could have been explained better, is to flip the coin repeatedly until you get HT, or TH. Once you have achieved that, you take the first of those two flips (either H or T, respectively) and that's your fair flip.*

When you have a fair coin, there is still some probability that you will get HH or TT on your first two flips- on average it will take you three flips to get HT or TH- which is why is says "Average 3 Flips" when you move the slider to 50%. Try it if you don't believe me.

As someone mentioned, if you know the bias (or lack thereof) of a particular coin, you don't need to use the "flip till you get HT or TH" algorithm. But it becomes useful when the coin's bias is unknown.


You never actually know the coin's true odds, so you still have to flip it an average of 3 times.


50/50 is a special case. You don't need to use the von Neumann extractor. This algo is for sources of randomness that you suspect have a bias.

But if you did use this algo on a 50/50 coin, half the time you'll get an HH or TT and have to start over. The other half of the time you'll get an HT or TH and return. So, on average, you'll need to do 3 flips for each execution of the algo.


Sure, I get that.

But that's why the bias can never be a (discrete) input, it is an emergent property of some unknown piece of matter, not something you set with a slider in steps of 1%.

As the coin gets more biased you'll need to flip more often to get a HT or TH pair with the amount of bias showing up as the frequency of the heads and tails over a longer run.

But the interesting bits are right around the middle where you can take a coin that is nearly perfect and use it in a perfect way, even when you can't even find out in finite time if the coin is perfect or not (and I would expect no real life coin to be perfect, but I would expect them to be so good as to be undetectable in a reasonable amount of time, 50/50 to me is 'perfection', I can't tell the left 50 from the one on the right).

The 'edge case', a perfect coin does not need three flips, it just needs one. If that's not the intended outcome you could either remove that 50/50 point or handle it correctly.

One of the more elegant ways of doing that would be to go from 49.9 to 50.1 or so, or an even smaller difference from the true center.


I think you are missing the trick here. Since HT and TH are equally likely, regardless the bias of the coin, as soon as you get one or the other, you can count it as a fair flip. All other combinations (HH and TT) are just ignored. The number of flips shown by the form is just about how patient you'll have to be to get a fair flip (HT or TH).

It doesn't matter how often you get TH and HT, only that they have the same frequency. Given then the probability of TH and HT are the same, if you only consider flips resulting in TH or HT, you automatically have a fair coin, no matter how bad (or good) the coin is.


The algorithm doesn't care for the edge case and still throws away HH and TT. That case has probability 0 anyway, if the bias is continuous.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: