Problem of the Week 883

Stretching Your Coinage

Call a coin a p-coin (0 <= p <= 1) if it comes up heads with probability p and tails with probability 1 - p. Thus a fair coin would be a 0.5-coin. We say that p simulates q if by flipping a p-coin repeatedly (some fixed 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 the sequence of 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 "head" to be any sequence with at least one real head. The chance of a "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.

The problem comes from an article by Dan Velleman and I. Szalkai in the American Math. Monthly. The full citation is:

© Copyright 1999 Rob Leduc. Reproduced with permission.


10 March 1999