Three in a Row
There’s a puzzle—not quite old enough to be called an old chestnut—involving probability and non-transitivity. In abbreviated form:
Two people each choose a three-element series of heads and tails, for example, heads-heads-tails or tails-heads-tails or heads-heads-heads. They then begin flipping a coin. The first person to see his three-element combination in consecutive flips of the coin wins. Is the bet fair?
The answer is no; the bet favors whoever selects his three-element string second. Your intuition might tell you the bet is fair, on the grounds that each three-flip string is equally likely. This is so within a fixed string of three tosses—each combination happens one eighth of the time—but it is not true over an extended string of flips. To illustrate the imbalance, consider an extreme mismatch: HHH versus THH.
One time in eight, the first three flips will all be heads, and the first player wins. On any other first three throws, however, a tail appears before three consecutive heads. Once this happens, THH must appear before HHH; after HHH fails on the first three tosses, the next time HHH appears will be after a tail, which means the second player has already won; that tail and the next two heads form a winning THH. So the second player wins seven times out of eight.
The relationship is non-transitive, however: every sequence beats some other sequences, but every sequence loses to some other sequences, too. So no matter what the first player picks, the second player can pick a combination more than 50% likely to appear first. If the second player selects blindly, he has no advantage, but if he’s clever, he’ll pick a superior combination, with odds of winning between 2/3 and 7/8.
I first encountered this problem in a Martin Gardner book. I sensed the bet wasn’t fair, but I was far too young to work out the entire answer on my own. But I remembered the answer, and, now that I’m older, and I’ve learned about Markov chains and network analysis and a lot of similarly scary-sounding topics, I can work out a complete solution: what is each combination’s odds of beating every other combination?
Well, almost. The reason this puzzle isn’t an old chestnut is that a complete answer depends on methods that didn’t exist before electronic calculation. With proper programming, a cheap computer utility can work out the answer in the blink of an eye. But I no longer have those utilities available; my copies are either corrupted or designed for out-of-date Macs. So if I want a complete answer, I have to crank out all 64 possibilities by hand. It’s not quite so bad as that, because symmetry cuts down on my work—HHH versus HHT, for example, has equal chances as TTT versus TTH, and HHT versus HHH is the same problem as HHH versus HHT and TTH versus TTT is the same as TTT versus TTH, so I only have to work out one answer for all four matches. Still, a complete solution involves working out some infinite sums by hand, and it’s taking me a while.
I keep with the task in part out of stubbornness. But mostly, I do it to relive my college days, to experience again the challenge of a problem set (which might well include something like this), and to exercise skills of which I was once proud, but which are now largely atrophied. The calculations are at once tedious and invigorating.
Maybe I should dig out some old textbooks and work some of the problem sets. Maybe you should dig out your old textbooks, too—it might be more fun than you expect.