Published
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Penney’s game
You will learn: Use shared-sequence prefix states to calculate which pattern appears first.
Start with: Events and probability · Expectation and variance
Choose a three-flip pattern, then let an opponent choose a different one. Toss a coin repeatedly and stop as soon as either pattern appears in three consecutive positions. With a fair coin, every particular three-flip window has probability 1/8 of matching either chosen pattern. That does not make their race fair.
The default first choice is HHT and the reply is THH. THH wins the race with probability 3/4. Both searches use the same sequence, including overlapping windows. Restarting a separate three-flip trial for every attempt would define a different game.
Predict the winner, then reveal flips
Both patterns race in the same independent coin sequence, starting with no previous flips. Stop when either first appears. Equal patterns are excluded.
Solid blue: first pattern HHT. Dashed red: second pattern THH. Dotted black: unfinished. Lines connect discrete flip counts.
| Outcome | By cap | Eventually |
|---|---|---|
| HHT first | 0.2500000 | 0.2500000 |
| THH first | 0.7479713 | 0.7500000 |
| Unfinished / never | 0.002028709 | 0.000000 |
Expected uncapped duration: 6.500000 flips. Expected min(duration, cap): 6.489378 flips. The cap does not change eventual winning probabilities.
Choose a response to HHT
| Response | Eventual response win probability |
|---|---|
| HHH | 0.5000000 |
| HTH | 0.3333333 |
| HTT | 0.3333333 |
| THH | 0.7500000 |
| THT | 0.3750000 |
| TTH | 0.5000000 |
| TTT | 0.3000000 |
Reveal one shared sequence
No flips revealed.
The game has not finished in the revealed prefix.
Inspect the prefix transition states
| Retained suffix | After H | After T |
|---|---|---|
| empty | H | T |
| H | HH | T |
| HH | HH | HHT wins |
| T | TH | T |
| TH | THH wins | T |
The chart gives probabilities of having won by each flip count. The dotted curve retains all unfinished games. At cap three, the two win probabilities are both 1/8 and unfinished probability is 3/4. By cap ten, HHT has won with probability 0.2490234375, THH with probability 0.609375, and 0.1416015625 remains unfinished. Eventual probabilities are one quarter and three quarters, independent of the plotting cap.
The reveal button exposes one seeded sequence one flip at a time and stops at its first winner. A sequence still unfinished at the cap is not a loss for either player. Increasing the cap retains the sequence’s earlier flips.
Work the default race without a simulation
If the first two flips are HH, HHT will win: subsequent heads preserve the run, and the first tail completes HHT. THH cannot have appeared before that first tail. Under a fair coin, this initial HH event has probability 1/4, and a tail eventually occurs with probability one.
Otherwise a T appears before a run of two Hs has been established. From then on, the first future occurrence of two consecutive Hs is immediately preceded by T, so THH appears before HHT. Such a run eventually occurs with probability one. This accounts for the other 3/4 of games.
This argument applies to this particular pair. It does not say the pattern THH beats every opponent. Use the response table after changing the first choice; a pattern’s advantage depends on its competitor.
Retain the useful suffix
The future does not need the entire flip history. It needs the longest suffix that is also a proper prefix of either target. For HHT versus THH, the transient states are empty, H, HH, T, and TH. From HH, another H leaves HH, while T completes HHT. From TH, H completes THH and T leaves suffix T.
Let w(s) be the probability of a first-pattern win starting from suffix s. With head probability p, w(s) is p times the value after H plus (1 − p) times the value after T. A first-pattern terminal state has value one; a second-pattern terminal state has value zero. Solving those simultaneous equations gives the eventual win probability. For expected duration, replace the terminal values by zero and add one for the next flip. The default expected duration is 6.5 flips.
Make a prediction
Can you infer the winner by comparing the two patterns' average waiting times in separate experiments?
Explore the answer
Not in general. The race depends on their joint occurrence in one sequence and on cross-pattern overlap. Separate waiting-time means do not specify that dependence. At the default both HHT and THH have individual mean waiting time eight for a fair coin, yet their head-to-head odds are unequal.
Change the coin and inspect the limits
The response table recalculates for the chosen head probability. The familiar fair-coin response strategy should not be applied to a biased coin without checking. At p = 0 or one the sequence is deterministic. If neither target is TTT or HHH respectively, the game never finishes; eventual win probabilities are both zero and expected duration is infinite.
The finite-state calculations use floating-point arithmetic. They are probability calculations, separate from the sample reveal. The table distinguishes capped duration from uncapped duration rather than treating unfinished observations as if they ended at the cap.
Reference
Miller, Penney’s Game Odds From No-Arbitrage derives the overlap-based odds. Continue with HH versus HT to compare first waiting times separately from competition in one shared sequence.