Solution to puzzle 13: Coin triplets
To answer these questions we need to calculate, for each pair of triplets, the probability that one triplet appears before the other. Given that each triplet is equally likely, it may initially seem that each is equally likely to appear first. For an example of why this is not so, consider the triplets HHH and THH. The only way for HHH to appear before THH is if the first three tosses come up heads. Any other result will allow THH to block HHH. Therefore, the probability that HHH appears before THH is 1/8.
We may calculate the probabilities for each pair in a similar manner. Consider, for example, HTT versus HHT. The probability HTT appears first is the mean of that probability over the four possibilities for the first two coin tosses. Let, for example, p(HT) be the probability HTT appears first following HT.
Suppose the first two throws are HH. Then the third throw can be either H or T. If it's H, then we are back in the same position: the preceding two throws are HH. But if it's T, then HHT has won! So the probability of HTT winning in this case is 0.
Putting the two possibilities for the third throw together, as a weighted mean, the probability that HTT wins following HH is: p(HH) = ½×p(HH) + ½×0 = p(HH)/2.
Now suppose the first two throws are HT. If the third throw is H, then neither player has won, and the probability HTT will ultimately win is (by definition) p(TH). (The last two throws were TH.) On the other hand, if the third throw is T, then HTT has won!
So this time the weighted mean for the probability that HTT wins, following HT is: p(HT) = ½×p(TH) + ½×1 = p(TH)/2 + 1/2.
Continuing in this way, we obtain the results below:
(1) p(HH) = p(HH)/2
(2) p(HT) = p(TH)/2 + 1/2
(3) p(TH) = p(HH)/2 + p(HT)/2
(4) p(TT) = p(TH)/2 + p(TT)/2
(1) 
p(HH) = 0. (Intuitively, HTT can avoid losing only by hoping for an infinite string of heads!)
(3) p(TH) = p(HT)/2
(2) p(HT) = p(HT)/4 + 1/2 p(HT) = 2/3
(3) p(TH) = 1/3
(4) p(TT) = p(TH) p(TT) = 1/3
The mean of these four results gives us: probability of HTT appearing before HHT = 1/3.
Here is the full table. Notice the surprising non-transitivity. Example: HHT beats HTT beats TTH beats THH beats HHT.
| 2\1 | HHH | HHT | HTH | HTT | THH | THT | TTH | TTT |
|---|---|---|---|---|---|---|---|---|
| HHH | 1/2 | 2/5 | 2/5 | 1/8 | 5/12 | 3/10 | 1/2 | |
| HHT | 1/2 | 2/3 | 2/3 | 1/4 | 5/8 | 1/2 | 7/10 | |
| HTH | 3/5 | 1/3 | 1/2 | 1/2 | 1/2 | 3/8 | 7/12 | |
| HTT | 3/5 | 1/3 | 1/2 | 1/2 | 1/2 | 3/4 | 7/8 | |
| THH | 7/8 | 3/4 | 1/2 | 1/2 | 1/2 | 1/3 | 3/5 | |
| THT | 7/12 | 3/8 | 1/2 | 1/2 | 1/2 | 1/3 | 3/5 | |
| TTH | 7/10 | 1/2 | 5/8 | 1/4 | 2/3 | 2/3 | 1/2 | |
| TTT | 1/2 | 3/10 | 5/12 | 1/8 | 2/5 | 2/5 | 1/2 |
a. What is the optimal strategy for each player? With best play, who is most likely to win?
The table shows that, for any triplet chosen by player 1, player 2 can always select a triplet that is more likely to appear first. In particular, the best response to each play by player 1, is:
| HHH: | THH | wins with probability 7/8 |
| HHT: | THH | wins with probability 3/4 |
| HTH: | HHT | wins with probability 2/3 |
| HTT: | HHT | wins with probability 2/3 |
The color coding illustrates the following strategy. Player 2 wants the final two coins of his triplet to be the first two in player 1's, because then he blocks half the cases where player 1 could win on the next round, by winning first. Similarly, player 2 wants the first two coins in his triplet not to be the final two coins in player 1's. This intuitive strategy is indeed supported by the probabilities listed in the above table.
The optimal strategy for player 1 is to choose triplet HTH or HTT, or their mirror images, THT or THH. This limits player 2's probability of winning to 2/3.
b. Suppose the triplets were chosen in secret? What then would be the optimal strategy?
From the table above, an optimal strategy for both players is to choose at random, with probability 1/2 for each, between HTT, and its mirror image, THH. The choice must be random so that the other player cannot discern and exploit any pattern of switching between HTT and THH.
(Note: These statements, while true, require rigorous proof; to be added.)
c. What would be the optimal strategy against a randomly selected triplet?
The expected return of each triplet against a randomly chosen triplet can be calculated from the above table.
We must decide what to do if our play matches the randomly selected triplet. We may call this void and play again, or we may split the (notional) winnings. The decision does not affect our choice of best play, but it does slightly alter the expected return from each play.
For example, the expected return for HHH, if we choose to void matching triplets, is:
(1/2 + 2/5 + 2/5 + 1/8 + 5/12 + 3/10 + 1/2) / 7 = 317/840 
0.377.
On the other hand, if we choose to split matching triplets, the expected return is:
(1/2 + 1/2 + 2/5 + 2/5 + 1/8 + 5/12 + 3/10 + 1/2) / 8 = 377/960 0.393.
The best play against a random triplet is HTT or THH. The table below shows the expected return and percentage expected profit from each play.
| Play | Expected return (void) | % expected profit (void) | Expected return (split) | % expected profit (split) |
|---|---|---|---|---|
| HHH | 317/840 | −12.3 | 377/960 | −10.7 |
| HHT | 469/840 | 5.8 | 529/960 | 5.1 |
| HTH | 407/840 | −1.5 | 467/960 | −1.4 |
| HTT | 487/840 | 8.0 | 547/960 | 7.0 |
Further reading
Source: The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems, by Martin Gardner. See Chapter 22.