Probability
Penney's game: why the second player wins
Every run of three coin flips is equally likely, yet in Penney's game the player who chooses second can always pick a sequence that tends to appear first, winning at least two times in three. Here is the reply rule, the full table checked by exact calculation, and Conway's trick for computing any match-up.
Equally likely is not the same as equally early. In a race between patterns, what matters is how each pattern overlaps the other.
Equally likely, not equally early
Flip a fair coin three times and every outcome, HHH or HTH or THH, has the same chance: one in eight. If two people each bet on a pattern for one block of three flips, nobody has an edge.
Penney's game, introduced by Walter Penney in 1969, changes one thing. Each player picks a three-flip pattern, then the coin is flipped again and again, and whoever's pattern appears first in the running stream wins. Once the patterns race in one continuous stream, equal chances stop meaning equal speed, and the player who chooses second can always use that.
The reply rule
The second player sees the first player's pattern before choosing. Call the first player's flips one, two, three. The reply is: the opposite of flip two, followed by flips one and two.
In short: copy the first player's first two flips and put the opposite of their middle flip in front. Against HHT you play THH; against HTH you play HHT; against TTT you play HTT. A common mistake is to flip the first symbol instead of the middle one. That gives THT against HHT, which wins only 3/8 of the time, worse than a coin toss.
The whole table, checked
Here are all eight match-ups, with the second player's chance of winning. Against HHH, THH wins 7/8. Against HHT, THH wins 3/4. Against HTH, HHT wins 2/3. Against HTT, HHT wins 2/3. Against THH, TTH wins 2/3. Against THT, TTH wins 2/3. Against TTH, HTT wins 3/4. Against TTT, HTT wins 7/8. Each of these was computed exactly, and in every case the reply given by the rule is also the best possible reply.
The extreme case is the easiest to see. HHH can only win if the very first three flips are HHH, which happens one time in eight. If a tail appears anywhere before that, then the first run of three heads must come right after a tail, and that tail plus two heads is THH, already finished. So the second player is never worse than two wins in three, and against HHH or TTT it is seven in eight.
No best sequence, only a best reply
Part of the intuition comes from waiting times. On average you wait 14 flips to see HHH, 10 to see HTH, and 8 to see THH. A pattern that overlaps itself, like HHH, tends to arrive in clumps, so its first appearance comes late.
But waiting time cannot be the whole story, because the wins go in a circle. THH beats HHT 3/4 of the time, HHT beats HTT 2/3, HTT beats TTH 3/4, and TTH beats THH 2/3. The relation is non-transitive, like rock, paper, scissors: there is no strongest sequence to pick first, only a best answer to whatever was picked.
Conway's leading numbers
John Conway found a way to compute any match-up by hand, described in Winning Ways and in Martin Gardner's writing. For two patterns A and B, write a correlation A:B. Slide B under A: at each position of A, ask whether the rest of A, from that position to the end, matches the start of B. Write 1 for yes and 0 for no, and read the digits as a binary number.
The odds that B appears before A are (A:A minus A:B) to (B:B minus B:A). For A as HHH and B as THH: A:A is 111, or 7; A:B is 000, or 0; B:B is 100, or 4; B:A is 011, or 3. The odds are 7 to 1, which is 7/8, matching the table. The lab on the Penney's Game page does this for any pair you choose.
Where the edge stops
The edge has limits, and they are worth knowing. For patterns of length three or more, Guibas and Odlyzko proved in 1981 that the second player always has a winning reply, built from the first player's first symbols with one symbol added in front. For length two it fails: against HT or TH, the best reply only ties at one half.
It also depends on a fair coin. If the coin lands heads four times in five, THH beats HHH only 61 times in 125, under one half, so the first player's HHH becomes the favourite. The lesson travels beyond coins: when events race in a stream, ask how the patterns overlap, and ask whether the process is really as fair as you assumed.