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!

Answer 2

Here is an approach that will work, but it requires repeated trial.

1. the chance that function_A returns 1: P(1) = p (e.g. p=60%)
2. the chance that function_A returns 0: P(0) = 1 - p
3. the chance for a specific sequence of return values a,b,... on successive calls to function_A is P(a)P(b)...

4. observe certain combinations will arise with equal odds, e.g.:

         P(a)*P(b) === P(b)*P(a)
    P(a)*P(b)*P(c) === P(b)*P(c)*P(a)
   
    etc.
   

5. we can use that fact when selecting only sequences of (1,0) or (0,1), we then know that the chance of either is

       P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
    => x / (x + x)
    => 1 / 2
   

This, then, becomes the recipe for implementing a function_B:

• call function_A repeatedly until we receive a sequence of (0,1) or (1,0)
• we consistently return either the first or last element of the sequence (both will have equal odds of being 0 or 1)

function_B()
{
    do
    {
        int a = function_A();
        int b = function_A();
    } while( (a ^ b) == 0 ); // until a != b

    return a;
}

Answer 3

Given:

1. Events = {head, tail}
2. the coin is unfair => P(head) = p and P(tail) = 1-p

Algorithm:

1. Generate a sample of N1 events (head or tails) using the unfair coin
2. estimate its sample mean m1 = (#heads)/N1
3. Generate another sample of N2 events (heads or tails) using the unfair coins
4. estimate its sample mean m2 = (#heads)/N2
5. if (m1 > m2) return head else return tail

Notes:

1. The events returned in step #5 above are equally probable (P(head) = P(tail) = 0.5)
2. If #5 is repeated many times, then its sample mean --> 0.5 irrespective of p
3. If N1 --> infinity, then m1 --> true mean p
4. To generate a fair coin output, you need many independent sampling (here tosses) of the unfair coin. The more the better.

Intuition: Although the coin is unfair, the deviation of the estimated mean around true mean is random and could be positive or negative with equal probability. Since true mean is not given, this is estimated from another sample.

Answer 4

Doable. 2 calls to that functions won't suffice though. Think of calling the function over and over and over and getting increasingly close to 50/50

Answer 5

I wondered if something recursive should work, with increasing depth, the chance for 0 or 1 should be closer and closer to 0.5. At 1 level, the modified chance is p'=p*p+(p-1)*(p-1)

depth = 10;
int coin(depth) {
    if (depth == 0) {
        return function_A();
    }
    p1 = coin(depth-1);
    p2 = coin(depth-1);
    if (p1 == p2) {
        return 1;
    } else {
        return 0;
    }
}

Answer 6

h for head, t for tail and p() for probability of.

Lets suppose the following:
    p(h) = 0.6
    p(t) = 0.4

Lets define an event => Event: Flip the coin twice (flip1 , flip2) 

Flipping the coin twice could produce the following results
=> {h, h} , {t, t}, {h, t}, {t, h}

Here are the different probabilities for each event

{h, h} = 0.6 * 0.6 = 0.18
{t, t} = 0.4 * 0.4 = 0.12
{h, t} = 0.6 * 0.4 = 0.24
{t, h} = 0.4 * 0.6 = 0.24

As we can see, the probabilities of having {h, t} and {t, h} are equal. We can base ourselves on this to produce an equi-probable result, for that we can keep triggering our event until it returns either {h, t} or {t, h}. At that point we return the first try of the event (given that the event includes two flips)

Here is a quick recursive implementation of the solution

def unfair_foo():
      # Some code here to produce unfair result
 
def fair_foo():
    flip_1, flip_2 = unfair_foo(), unfair_foo()
 
    if flip_1  flip_2:
      # Base case
      return flip1

     return  fair_foo()  # Recursive call

Answer 7

def fairCoin(biasedCoin):
coin1, coin2 = 0,0
while coin1 == coin2:
coin1, coin2 = biasedCoin(), biasedCoin()
return coin1

This is originally von Neumann’s clever idea. If we have a biased coin (i.e. a coin that comes up heads with probability different from 1/2), we can simulate a fair coin by tossing pairs of coins until the two results are different. Given that we have different results, the probability that the first is “heads” and the second is “tails” is the same as the probability of “tails” then “heads”. So if we simply return the value of the first coin, we will get “heads” or “tails” with the same probability, i.e. 1/2.This answer is from - http://jeremykun.com/2014/02/08/simulating-a-fair-coin-with-a-biased-coin/ read more about it at http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin