C puzzle: Make a fair coin from a biased coin

Question

How can I determine the probability that a function would return 0 or 1 in the following case:

Let the function_A return 0 with probability 40% and 1 with probability 60%. Generate a function_B with probabilities 50-50 using only function_A only.

I thought of the following:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

What combination could give 50-50?

Answer 1

This is a classic probability puzzle and to the best of my knowledge you can't do this with just two calls to the function. However, you can do this with a low expected number of calls to the function.

The observation is that if you have a biased coin that comes up heads with probability p, and if you flip the coin twice, then:

• The probability that it comes up heads twice is p²
• The probability that it comes up heads first and tails second is p(1-p)
• The probability that it comes up tails first ands heads second is (1-p)p
• The probability that it comes up tails twice is (1-p)²

Now, suppose that you repeatedly flip two coins until they come up with different values. If this happens, what's the probability that the first coin came up heads? Well, if we apply Bayes' law, we get that

P(first coin is heads | both coins are different) = P(both coins are different | first coin is heads) P(first coin is heads) / P(both coins are different)

The probability that the first coin is heads is p, since any coin toss comes up heads with probability p. The probability that both coins are different given that the first coin is heads is the probability that the second coin came up tails, which is (1 - p). Finally, the probability that both coins are different is 2p(1-p), since if you look at the probability table above there are two ways this can happen, each of which has probability p(1-p). Simplifying, we get that

P(first coin is heads | both coins are different) = p (1-p) / (2p(1-p)) = 1 / 2.

But that's the probability that the first coin comes up tails if the coins are different? Well, that's the same as the probability that the first coin didn't come up heads when both coins are different, which is 1 - 1/2 = 1/2.

In other words, if you keep flipping two coins until they come up with different values, then take the value of the first coin you flipped, you end up making a fair coin from a biased coin!

In C, this might look like this:

bool FairCoinFromBiasedCoin() {
    bool coin1, coin2;

    do {
        coin1 = function_A();
        coin2 = function_A();
    } while (coin1 == coin2);

    return coin1;
}

This may seem woefully inefficient, but it's actually not that bad. The probability that it terminates on each iteration is 2p(1 - p). On expectation, this means that we need 1/(2p(1-p)) iterations before this loop will terminate. For p = 40%, this is 1/(2 x 0.4 x 0.6) = 1/0.48 ~= 2.083 iterations. Each iteration flips two coins, so we need, on expectation, about 4.16 coin flips to get a fair flip.

Hope this helps!