The Coin Paradox

• Home Page
• Biography
• PGP Public Key
• Research
• Writings
  • Grad School Advice
  • RoShamBo and Compression
  • The Two Envelope Problem
  • Two Envelope Variant
  • Statistical Learning Theory
  • The Coin Game Paradox
  • Quantum Mechanics
  • Analysis Of Multi-tasking
  • Note on Psuedorandomness
  • Note on Bit Commitment
• Source Code
• Pictures

Assume you have a fair coin and you want to play a game with your friend. You bet your friend that when you start flipping the coin you will see the sequence ( Heads, Tails ) before you see the sequence ( Heads, Heads). For example, you would win on the toss sequences shown below:

• T, T, H, T
• H, T
• T, H, T

• T, T, H, H
• H, H
• T, H, H

Now consider a simple variation on this game. Instead of betting on the outcome of a single coin, imagine what would happen if both you and your friend each had a coin. The game would now be played as follows: Each turn you flip your coin and your friend flips his coin. If the sequence (Heads, Tails) occurs on your coin before the sequence (Heads, Heads) occurs on your friends coin, then you win. If the sequence (Heads, Heads) occurs on your friends coin before (Heads, Tails) occurs on your coin, then your friend wins. If the sequence (Heads, Tails) occurs on your coin in the same turn that (Heads, Heads) occurs on your friends coin, then both of you start over (e.g. there are no ties).

At first glance it seems like the second game also results in each player having a probability of winning of 1/2. However this is not true! The player who bets on (Heads, Tails) will win much more often. The simplest way to see this is by calcuting the average number of flips it takes each player to win.

E[X_HH|F_1 = T] = 1 + E[X_HH]

E[X_HH|F_1 = H] = (1/2) * ( 2 ) + (1/2) * (E[X_HH] + 2)
E[X_HH|F_1 = H] = 2 + (1/2) * E[X_HH]

E[X_HH] = (1/2) * ( E[X_HH|F_1 = H] + E[X_HH|F_1 = T] )
E[X_HH] = (1/2) * ( 1 + E[X_HH] + 2 + (1/2)*E[X_HH])
E[X_HH] = (1/2) * ( 3 + (3/2)*E[X_HH]) = 3/2 + (3/4) E[X_HH]
E[X_HH] = 6

E[X_HT|F_1 = T] = 1 + E[X_HT]

E[X_HT|F_1 = H] = (1/2) * ( 2 ) + (1/2) * (E[X_HT|F_1 = H] + 1)
E[X_HT|F_1 = H] = 1 + (1/2) * (E[X_HT|F_1 = H] + 1)
E[X_HT|F_1 = H] = 3

E[X_HT] = (1/2) * ( E[X_HT|F_1 = H] + E[X_HT|F_1 = T] )
E[X_HT] = (1/2) * ( 1 + E[X_HT] + 3 )
E[X_HT] = 2 + (1/2)*E[X_HT]
E[X_HT] = 4

As we showed above the average time until the sequence (Heads, Heads) occurs is six flips, but the average time until the sequence (Heads, Tails) occurs is four flips. Therefore "on average" it will take longer to get (Heads, Heads) on a coin than it will to get (Heads, Tails). Technically this does not show that the person betting on (Heads, Tails) in the second game has a higher probability of winning. To do that we would have to do more detailed calculations similiar to what we did above. However the fact that the average time to get (Heads, Tails) is shorter than the average time to get heads tails is still quite a fascinating result!