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.

David Shin: Have you saved all of your difficult problems for February?

Part I:

Well, I am fairly well convinced that there is no rational p (except for 1/2) such that a p-coin can simulate 1/2-coin.  My proposed proof follows:

Assume that there is.  
Then there is at least one specfic, non-infinite number of throws (call it n) of the p-coin which can do the trick.
And because p is rational, p can be expressed as the ratio of two relatively prime integers, r/t.  Let s = t-r.

There are 2^n different combinations of Heads and Tails.

The probability of any one specific combination of h heads and (n-h) tails is (r^h)*(s^(n-h))/((t^n).
Note that all but one of the 2^n combinations involve a power of r; (only the all-tails combination does not).

In order to have the p-coin simulate the 1/2 coin, we need to partition the 2^n combinations into two groups, each of which totals to probability 1/2.
Consider the group which does not include the all-tails combination.
When summing up its' probabilities, we notice that all of its numerators involve a power of r and the denominator for all of the terms are (t^n).   Therefore, the sum has a numerator which is a multiple of r and a denominator which is a multiple of t.
Since t is relatively prime to r, there is no way that this sum can equal 1/2.  This contradicts our assumption.

Therefore, there is no rational p such that a p-coin can simulate 1/2-coin, except for another 1/2-coin.
And that's not really a simulation, is it?

Part II:
I see no similar objections to an irrational p.  

Posted by Steve Herman on 2005-02-18 23:11:25