[ACCEPTED]-C puzzle: Make a fair coin from a biased coin-probability

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

The observation is that 44 if you have a biased coin that comes up 43 heads with probability p, and if you flip 42 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 41 repeatedly flip two coins until they come 40 up with different values. If this happens, what's 39 the probability that the first coin came 38 up heads? Well, if we apply Bayes' law, we 37 get that

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

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

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

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

In other words, if you 15 keep flipping two coins until they come 14 up with different values, then take the 13 value of the first coin you flipped, you 12 end up making a fair coin from a biased 11 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 10 may seem woefully inefficient, but it's 9 actually not that bad. The probability 8 that it terminates on each iteration is 7 2p(1 - p). On expectation, this means that 6 we need 1/(2p(1-p)) iterations before this 5 loop will terminate. For p = 40%, this 4 is 1/(2 x 0.4 x 0.6) = 1/0.48 ~= 2.083 iterations. Each 3 iteration flips two coins, so we need, on 2 expectation, about 4.16 coin flips to get 1 a fair flip.

Hope this helps!

Here is an approach that will work, but 6 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 5 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 4 use that fact when selecting only sequences 3 of (1,0) or (0,1), we then know that the 2 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 1 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;
}

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 5 of the estimated mean around true mean is 4 random and could be positive or negative 3 with equal probability. Since true mean 2 is not given, this is estimated from another 1 sample.

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

I wondered if something recursive should 4 work, with increasing depth, the chance 3 for 0 or 1 should be closer and closer to 2 0.5. At 1 level, the modified chance is 1 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;
    }
}

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 7 {h, t} and {t, h} are equal. We can base ourselves on 6 this to produce an equi-probable result, for that 5 we can keep triggering our event until it 4 returns either {h, t} or {t, h}. At that point we return 3 the first try of the event (given that the 2 event includes two flips)

Here is a quick 1 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