Thursday, January 15, 2009

biased coin flipping

Probability riddle!

Easy version: There are two players, A and B. They have one fair coin. What game can they play such that player A wins with probability exactly 1/3?

Harder version: Now players A and B have a single coin that lands heads with probability p in [0,1]. What game can they play, which halts with probability 1, such that player A wins with exactly probability q in [0,1]? (Hint: First pretend they have a fair coin. Then simulate a fair coin with an unfair one.)

Try it first, this riddle is quite within reach with a little pondering, and there are lots of correct answers at least for the first part.

Answer after spoiler space...
.
.
.
.
.
.
.
.
Ok, for the first version here is the answer I came up with but there are others for sure, maybe much simpler. Write 3 as 11 in binary. Now flip the coin in sets of two flips, with heads as "1" and tails as "0", so that each pair of flips spells an integer between 0 and 3. If you ever spell 11, ignore it. If the first integer between 0 and 2 that you spell is 0, player A wins. Another answer: Flip the coin repeatedly until you get tails. If tails occurs on an even numbered flip, player A wins.

Note that in general, you can use this method to simulate any rational number a/b. If 0 is one of the first a unique n-bit (where n is the number of bits needed to write b in binary) numbers spelled with the coin in {0,1,...,b-1}, then player A wins. The logic is that in an arrangement of the integers from 0 to b-1, there is an a/b chance that 0 is in the first a numbers in the sequence.

For the harder version, first let's create an event of probability p with a fair coin. To do this, write p in binary. Now spell out another decimal digit by digit by flipping the coin as above. If the resulting number is less than p, player A wins. This halts with probability 1 because in some finite time you will figure out whether the number is less than or greater than p: on the first flip that differs from that digit of p. The intuition for this is pretty straightforward. p fraction of all real numbers between 0 and 1 are less than p.

Now to simulate a fair coin: I actually found a much less pretty answer for this, thought to myself "I bet there's some really easy symmetrical solution to this" and then didn't bother trying to find it. But then a friend of mine told it to me. Turns out it's known as Von Neumann's trick. All you have to do is flip the coin in sets of two. If it comes up T/T or H/H, ignore it. If it comes out T/H, take that as a tails flip. If it comes out H/T, that's heads. By symmetry there is an equal probability of these two events.