Make a fair coin from a biased coin

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

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 p2

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)2

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;

}

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.