Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C puzzle: Make a fair coin from a biased coin

Tags:

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?

like image 333
garima Avatar asked Mar 25 '11 05:03

garima


People also ask

How do you make a fair coin out of a biased coin?

Riddler Classic. Mathematician John von Neumann is credited with figuring out how to take a biased coin (whose probability of coming up heads is p, not necessarily equal to 0.5) and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again.

Can a fair outcome be generated with a biased coin?

Fair results from a biased coinIf a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure: Toss the coin twice. If the results match, start over, forgetting both results.


2 Answers

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 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; } 

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!

like image 198
templatetypedef Avatar answered Sep 22 '22 21:09

templatetypedef


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; } 
like image 26
Shamim Hafiz - MSFT Avatar answered Sep 20 '22 21:09

Shamim Hafiz - MSFT