waited coins
 

Hi internet,

Got this puzzle from a book called [U]Which Way Did the Bicycle Go?[/U] by Wagon, Velleman and Konhauser. The book is endorsed by the Mathematical Association of America.

Here is the coin puzzle (#187 out of 191)

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

More precisely: There exists a positive integer n and some subset of th 2^n possible outcomes of flipping the p-coin n times such that the probability of a sequence of n flips being in the subset is q.

For example, a fair coin can be used to simulate a 3/4 - coin by using two flips and defining a pseudo - head coming up is 3/4, and so we have simulated a 3/4 - coin.

There is a p such that a p-coin can simulate both a 1/2 - coin and a 1/3 coin.
Find such a value.

Regards,
Matt

I couldn't wait,

I post the solution now while I am thinking about it.

solution 187 Biased Coins
[SPOILER]
It turns out that p=(3 + sqrt(3))/6 yeilds the desired p-coin.

It is not hard to see that if p simulates 1/2 and 1/3, it must
simulate 1/6. A natural first attempt is to let p=1/6, but
this doesn't work (see problem 187.1) As a second attempt
let us choose p so that if the coin is flipped twice the
probrability of getting HT is 1/6. Such a p satisfies
p(1-p) = 1/6, and so p amy be taken to be (3*sqrt(3))/6.
This p clearly simulates 1/3 (consider the 2 flip event
"HT or TH"; thus occurs with probability 1/6+1/6 or 1/3),
Now, and this is a bity of lucky coincidence, ti turs out that
the 3-flip event "HHH or TTT" occurs with probability 1/2;
for the chance of getting one of these two sequences is

p^3 + (1-p)^3 = (9+5*sqrt(3))/36 + (9-5*sqrt(3))/36 = 1/2

Problem 187.1 Prove that 1/6 does not simulate 1/3.
Problem 187.2 Prove that 1/6 does not simulate 1/2.
Problem 187.3 Prove that no rational number simulates
both 1/2 and 1/3.

Note, This problem is due to Szalkai and Velleman, whose
paper contains further results about coin simulations.
[/SPOILER]

Regards,
Matt