Call a biased coin a p-coin if it comes up heads with probability p and tails with probability 1-p. We say that a p-coin simulates a q-coin if by flipping a p-coin repeatedly (some fixed finite number of times) one can simulate the behavior of a q-coin.

For example, a fair coin can be used to simulate a 3/4-coin by using two flips and defining a pseudo-head to be any two-flip sequence with at least one real head. The chance of a pseudo-head coming up is 3/4, so we have simulated a 3/4-coin.

1. Find a rational value p such that a p-coin can simulate both a 1/2-coin and a 1/3-coin, or prove that no such value exists.

2. Find an irrational value p such that a p-coin can simulate both a 1/2-coin and a 1/3-coin, or prove that no such value exists.

As I've already mentioned, a sqrt(1/2) -coin can simulate a 1/2 coin, in exactly the same way that a 1/2 coin can simulate a 3/4 coin.

Similarly, a sqrt(1/3)-coin or a sqrt(2/3)-coin can simulate a 1/3 coin.

I haven't had much luck using a sqrt(1/2) coin to simulate a 1/3 coin, or using a sqrt(1/3) coing to simulate a 1/2 coin.  I also haven't had much luck using a sqrt(1/6) coin to simulate either.  The radical terms just aren't cancelling out for me in the binomial expansion.

While Part II still might be impossible, a more promising approach might be to use a (1/2 +/- sqrt(a))-coin.  Two flips of both a (1/2 + sqrt(a))-coin and a (1/2 - sqrt(a))-coin have probability (1/2 - 2a) of exactly one head and probability (1/4 - a) of a head-tail and probability (1/4 - a) of a tail-head.  The only one of these three which equals 1/2 or 1/3 is when a= 1/12.  A (1/2 - sqrt(1/12)) coin could be used to simulate a 1/3 coin, if we define exactly one head out of two flips as a simulated head.

Time for my day job.  To be continued...

Posted by Steve Herman on 2005-02-21 11:39:19