5

This is related to my other question on a similar topic.

Suppose we play the following game: we flip a coin repeatedly and record the outcomes. For example we might get HHTTTHTTHHTTT.... Now Alice and Bob each choose distinct patterns of the same length, called $A$ and $B$, respectively. Which ever player's pattern appears first wins the game.

Now suppose Alice chooses $A=$HHHH and Bob chooses $B=$HHHT. First, let's notice that the expected number of flips to obtain $A$ is 30, but for $B$ it's only 16. This would seem to imply that Bob is very likely to win this game most of the time.

However, thinking about the game in another way, neither Alice nor Bob can win until HHH occurs. And after this, the game ends on the next flip with each player winning equiprobably.

This seems counter-intuitive to me: we have two events, one expected to occur much sooner than the other, but relative to each other the ordering is 50-50. What am I missing?

Community
  • 1
Fixee
  • 11,565

1 Answers1

12

The odds of either player winning are 50%. However, imagine for a moment that after that player wins, you were to continue flipping until the other player sees their chosen sequence.

If Bob wins, that means the last four flips were HHHT, which means Alice cannot use those flips as part of her sequence, essentially meaning she's starting over, and it'll be an expected 30 more flips before she sees HHHH.

However, if Alice wins, then the last four flips were HHHH, which means Bob has a 50% chance that the very next flip gives him his sequence. Even if it doesn't, there's then another 50% chance the very next flip after that will complete a HHHT string. If you do the math, I believe Bob would expect to see his finished sequence on average 2 flips after Alice wins.

So the apparent paradox occurs because the expected number of flips each player must wait includes waiting after the other player has already won, in which case Alice would wait much longer than Bob. But if you stop the game as soon as one player wins, each player has a flat 50% chance of seeing their sequence.

MartianInvader
  • 6,394
  • Hi. I have a similar problem, but the sequences are HTT and THH. My professor says it is a paradox as well, but I can't see how. I mean, each one has also a flat 50% chance of winning, unless we consider the value provided by the last flip. But he doesn't say if we should or not consider it. Do you have an idea of how this is a paradox? Thanks. – ddz Dec 13 '17 at 09:00