waited coins

MattcAnderson · 2017-08-25, 01:52

Hi internet,

Got this puzzle from a book called Which Way Did the Bicycle Go? 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

MattcAnderson · 2017-08-25, 02:04

I couldn't wait,

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

solution 187 Biased Coins

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.

Regards,
Matt

2017-08-25, 01:52	#1
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 800₁₀ Posts	waited coins Hi internet, Got this puzzle from a book called Which Way Did the Bicycle Go? 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

2017-08-25, 02:04	#2
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1440₈ Posts	I couldn't wait, I post the solution now while I am thinking about it. solution 187 Biased Coins 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 (3sqrt(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+5sqrt(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. Regards, Matt