How to turn a biased coin into a Fair Coin
carlos.bueno.org
carlos.bueno.org
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.
As tucked away in another comment, related is: http://en.wikipedia.org/wiki/Randomness_extractor
(But thanks for the nice link!)
Good to see more examples of it in the wild.
As for the statistical significance, here's another view of how to do it: http://www.inference.phy.cam.ac.uk/mackay/abstracts/euro.htm...
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)).
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.
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.
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.
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.
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.
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.
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.
Is that what he is talking about?
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.
Does that help?
Given such a coin, and nothing else, how can you simulate a fair single 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.
* 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.