Author: jason (Jason Jordan)
Date: 2003-Oct-18 06:50:28

The previous coin problem reminded me of an interesting puzzle I solved
back in college as part of a semester-long contest:

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 the 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 1/4-coin can be used to simulate a 5/8-coin by using 2 flips
and defining a pseudo-head to be either of the sequences HH or TT.  The
probability of a pseudo-head is then 1/16 + 9/16 = 5/8.

Find one coin that can simulate both a 1/2-coin and a 1/3-coin.

Author: bandsmer (Michael Bandsmer) Date: 2003-Oct-20 05:27:33 This problem is a lot harder than I expected. I had to do quite a bit of analysis to convince myself there is no rational p which works, and even then, it took a lot of trial and error to come up with an irrational p that works. The solution I found is p = 1/2 + sqrt(6)/6 = 0.9082482906... = probability of head So the probability of a tail is 1-p = 1/2 - sqrt(6)/6 Using this value for p, a 1/3-coin can be simulated by tossing the p-coin 5 times, with a pseudo-head sequence being any of the following: - exactly 1 tail - probability 5*p^4*(1-p) - HHHTT, HHTHT, HHTTH - probability 3*p^3*(1-p)^2 - TTTHH, TTHTH, TTHHT - probability 3*p^2*(1-p)^3 - exactly 1 head - probability 5*p *(1-p)^4 --------------------------------------------------- total probability 1/3 A 1/2-coin can be simulated by tossing the p-coin 8 times, with a pseudo-head sequence being any of the following: - exactly 1 tail - probability 8*p^7*(1-p) - HHHHHHTT, HHHHHTHT, HHHHTHHT or any rotation of these - probability 24*p^6*(1-p)^2 - HHHHHTTT, HHHHTHTT, HHHTHHTT or any rotation of these - probability 24*p^5*(1-p)^3 - HHHHTTTT, HHHTHTTT or any rotation of these - probability 16*p^4*(1-p)^4 - TTTTTHHH, TTTTHTHH, TTTHTTHH or any rotation of these - probability 24*p^3*(1-p)^5 - TTTTTTHH, TTTTTHTH, TTTTHTTH or any rotation of these - probability 24*p^2*(1-p)^6 - exactly 1 head - probability 8*p *(1-p)^7 ------------------------------------------------------------ total probability 1/2 I verified these sums with a program that does symbolic math. Other combinations of sequences for this value of p are possible as well. However, I'm pretty sure the solution above uses the fewest number of coin tosses (for this p anyway). I'm still puzzled as to why p = 1/2 + sqrt(6)/6 happens to work, and why everything else I tried doesn't. Is this the only solution? If so, how can it be proven? If not, what other solutions are there? In any case, I found it a very intriguing problem! Thanks! Mike
Author: jason (Jason Jordan) Date: 2003-Oct-20 05:38:02 Nice work! You found a solution different than the one I found, something I did not expect. For some reason, I assumed that the solution was unique. I haven't double-checked your numbers myself, but given your posts here, I trust that your work is thorough. :-) My solution used p = 1/2 + sqrt(12)/12. To simulate a 1/3-coin, flip this coin twice. Call it a pseudo-head if the sequence is HT or TH; call it a pseudo-tail otherwise. To simulate a 1/2-coin, flip this coin thrice. Call it a pseudo-head if the sequence is HHH or TTT; call it a pseudo-tail otherwise. I leave the math to the reader. I remember coming up with it during a frenzied pen-and-notebook session just before the problem deadline. But I can't recall how I went about solving it. :-) Note: This problem is from the paper "Versatile Coins" by Istvan Szalkai and Dan Vellerman, American Mathematical Monthly 100 (1993) pp. 26--33. I have not read it, just passing the info along.
Author: tomc (Tom Carmichael) Date: 2003-Oct-20 13:59:29 It's interesting to me that both solutions have 1/sqrt(x) in the solution, where x is a multiple a*b, given target pseudo coins 1/a and 1/b. I wonder if that's a general case. In other words, is .5 +/- 1/sqrt(24) a solution? How about if the targets are 1/3 and 1/5, is an answer .5 +/- 1/sqrt(15)? Too many problems, not enough time. :-)