By Recently, I wrote an article on why the Monty Hall problem has perplexed so many brilliant minds where I showed that it was a corner case between 1 open and 1 closed door, while the intuitive but wrong answer is close to the probability curve of 1 open door.
Now a coin toss puzzle has appeared on Twitter that has gone viral as it goes against our common intuition of probability and random sequences (such as a series of coin tosses). The puzzle goes as follows.
The Problem
Flip a fair coin 100 times—it gives a sequence of heads (H) and tails (T). For each HH in the sequence of flips, Alice gets a point; for each HT, Bob does, e.g., for the sequence THHHT Alice gets 2 points and Bob gets 1 point. Who is most likely to win?
- Option A: Alice
- Option B: Bob
- Option C: Equally likely
I invite you to pause here for a moment and come up with your own solution.
.
.
.
- Since coin tosses are the very foundation of our understanding of probability theory that can be best understood by equally likely outcomes, most people tend to think that Option C is the correct answer.
- Since Alice gains two points in 3 heads appearing together (HHH) and any extension thereof, as opposed to Bob who does not have this luxury, the second most chosen answer was Option A.
- In reality, the correct answer is Option B. Bob wins most of the times.
Let us find out the reason from both intuitive and mathematical viewpoints.
Intuitive Reasoning
For any sequence starting with HH, the next coin flip has one of the following two outcomes.
- HH.H: Alice wins with the score 2-0 (since in 100 tosses, Alice wins 99-0, 98-1, and so on, this margin of victory can easily be confused with the number of branches in which Alice wins).
- HH.T: It is a tie with the score 1-1 (HH for Alice and HT for Bob).
So we have 1 win for Alice and 1 draw between the two.
On the other hand, for any sequence starting with HT, the next coin flip has one of the following two outcomes.
- HT.H: Bob wins with the score 0-1.
- HT.T: Bob wins with the score 0-1.
So we have 2 wins for Bob in such a case, as opposed to Alice’s case above. Clearly, Bob wins in most branches of all possible sequences.
Proof by Mathematical Induction
Since two coin tosses scenario produces equally likely outcomes, we start with $k=3$. The possible scenarios and their outcomes are drawn in the figure below.
From the above figure, Bob wins in 3 branches as compared to Alice who wins in 2. Therefore, Bob is the winner for $k=3$. Let us draw a table for flip $k+1$.
| Flip $k$ | Flip $k+1$ | Outcome |
|---|---|---|
| H | H | Draw or Bob wins |
| H | T | Bob wins |
| T | H | Bob wins |
| T | T | Bob wins |
Keep in mind that this table below does not represent sequences of possible outcomes. Instead, it simply describes the outcome for the next flip at $k+1$ as is customary in mathematical induction.
Now from the first row, we can see that Alice wins 1 point when an HH arrives. Hence, it is either a draw (if Bob has won until flip $k$ by a margin of 1) or Bob still wins (if he has won by a margin greater than 1 by flip $k$). The second row just consolidates his position due to HT while the third and fourth row do not change anything (i.e., Bob still wins).
