What I particularly like here is that the title of the article, and thus the title of the HN post, fully conveyed the puzzle, so I was able to think about it for a moment before reading the article, solve it, and then confirm that I had the correct answer. Always a happy moment. :)
This works and is very intuitive, but loses quite a bit of the coin flip's entropy in the process. There are more efficient algorithms, such as http://www.eecs.umich.edu/~qstout/abs/AnnProb84.html , which better use the entropy generated by the coin flip.
One solution I heard has a basic idea that's quick to explain, although the details are messy. It might be interesting to get some intution:
Flip the coin N times and count the number of heads, K. You got one of the C = {N \choose K} = N!/((N-K)!K!) ways of getting K heads, all of which have the same probability, no matter what the bias of the coin is. If you consider an ordering of the C choices, then you have an integer from 0 to C-1 drawn uniformly at random. You could represent that integer using binary and extract about log_2(C) random bits.
For large N, the number of bits extracted is nearly the optimal NH bits, where H is the binary entropy of the coin. To count how far through a list of combinations I am for large N, I might construct a lattice and, I'm guessing, start reproducing works referenced by the paper that the parent linked to. Whereas the paper itself seems to have, from my quick skim, the definitive answer. Nice.
This is a pretty well known problem. (First problem the professor in my undergrad algorithms class ever gave to us)
SPOILER
p = probability of heads
1 - p = probability of tails.
flip the coin twice:
head head = p^2
head tail/tail head = 2p(1-p)
tail tail = (1 - p)^2
Notice the two in the middle there. We can just say head tail = Heads and Tail Heads = Tails. If we get HH or PP, just do it again.
Ok, now call the above procedure, our "randomization algorithm"
we can calculate the expected running time -- our algorithm succeeds with probability 2p(1-p). The number of trials we need to run our algorithm for is a geometric random variable. Thus, the expected running time is 1/(2p(1-p)).
thanks for writing this. the formula used in the webpage, (HH+TT+HT)/TH, appears to be off by one. i calculated it myself from the series, i.e. sum(n=0 to inf, 2(n+1)2pq(p^2+q^2)^n), and through the algebra i work it out to the same as yours (doubled).
i'm not sure how the author's formula was derived, but i get the same result calculating the series for a slightly different (but wrong) algorithm: just keep flipping until HT or TH appears (not flipping by pairs). this series is sum(n=1 to inf, (n+1)(qp^n + pq^n)), i.e. sum(n=0 to inf, (n+1)(qp^n + pq^n)) - (p+q). the series works out to 1/(p(1-p)), but that last term would account for the one-off difference.
Good point. I am going off of the original algo by von Neumann, which throws away both flips if you get HH or TT. There are many others, and I don't see any reason against your optimization, if the flips are truly independent.
yeah, indeed -- but i think the optimization is actually broken. if you are just waiting for an HT or a TH in a sequence of flips, then you will just wind up with H..HT or T..TH, so that the very first flip decides the outcome. this is how i first (much too hastily) read the algorithm, but, somewhat surprisingly, found that the expectation matched exactly.
They are mostly useful in determining prior knowledge of the solution. For other people coming up with the a-ha solution during the interview is hit and miss.
No, not at all. Properly used, the interviewed party is supposed to be instructed that if they already know the answer, they should inform whoever is interviewing them so that a different question should be picked.
The goal is not to see if the person can get the answer. The goal is to see how the person approaches unexpected or novel problems.
That is why the person being interviewed is instructed to "think out loud" when asked these sorts of questions.
"The goal is not to see if the person can get the answer. The goal is to see how the person approaches unexpected or novel problems."
Then maybe we use different definitions of "brainteaser". My definition of brainteaser is a problem that needs a single clever, non-obvious trick to solve. Groping for a clever trick is usually very random and doesn't tell me much about the skills of the person trying to solve the problem.
If I want to judge someone's approach, then open-ended problems where you have multiple solutions (preferably involving several easier-to-get steps) are much better than single-insight brainteasers.
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.
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.
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.
This article claims this algorithm is very likely happening inside my computer right now, but it doesn't elaborate. Why would my computer be performing this algorithm?
Some processors have a hardware random source. Due to manufacturing problems these are usually biased, but can still be used because of this algorithm.
Randomness extractors are used widely in cryptographic applications, whereby a cryptographic hash function is applied to a high-entropy, but non-uniform source, such as disk drive timing information or keyboard delays, to yield a uniformly random result.
Maybe I'm crazy and it's the end of the day and my reading comprehension is shot, but I honestly can't even understand what the question is. Can somebody explain?
A fair coin would be one that is equally likely to land on either heads or tails when tossed - on any given toss, you have exactly a 50% chance of getting either heads or tails.
A biased coin, on the other hand, has a bias towards one side or another - e.g. you could have a coin that lands on heads 75% of the time.
The question is - if you've got a biased coin, how do you get it to behave like the fair coin?
It's probably easier to imagine a 10 sided die. You've got one with 7 sides painted red and 3 painted blue, so you've got a 70% chance of rolling red on any given roll. But you and your friend want to be able to use this die to decide who's round it is next - guess the right colour and it's the other guy's round. If you were to base this on a single role, you'd obviously both want to pick red. So what you want is to be able to use this die to create two outcomes which are both equally likely to happen.
You have a coin which is weighted, so it comes up heads 70% of the time and tails only 30%. Or worse yet, perhaps you don't even know what frequency it comes up heads.
Given such a coin, and nothing else, how can you simulate a fair single coin flip?
The question is how can you use a biased coin to reproduce an unbiased coin flip.
In this article, they give the example of a coin that flips heads 70% of the time. Their method was to flip the coin twice. They only considered cases where heads was flipped once and tails was flipped once because these cases both had a 21% chance of happening. So both cases have the same chance of occurring. In order to differentiate between the two cases, you consider the first coin flip to be your result. So heads than tails is the same as getting a heads and tails than heads is the same as getting a tails.
This sounds simpler - if it works (can anyone confirm it?)
* We maintain a fair coin abstraction that contains an unfair coin.
* Along with the unfair coin, we also maintain a counter 'C'.
* 'C' starts from 0, counting up 1 every time the coin is flipped.
* If C % 2 == 0 then we report the value of the unfair coin's toss. Otherwise, we reverse the value of the unfair coin's toss and report it.
Related: I vaguely recall hearing of a p2p game client where dice rolls were needed and to secure against cheating they polled each client and took the modulo of the sum of responses (iirc). You get unbiased outcomes as long as one player doesn't cheat.
One of the few sites, where I don't need to use my iReader chrome extension to read the text. I love the font and the hyphenation using the sweet-justice JS script seems to work out great.
