Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.