Penney's Game with Length-2 Sequences
You and a friend each pick a distinct sequence of two coin flips -- $HH$, $HT$, $TH$, or $TT$ -- and then flip a fair coin repeatedly until one of your sequences appears in two consecutive flips. Whoever's sequence appears first wins.
The twist: one of you picks first, and the second player sees the first player's choice before picking their own. Both players play optimally.
- Should you choose your sequence first or second? Or does it not matter?
- What is your probability of winning under the optimal strategy?
- Report $L + p$, where $L = 1$ if you should choose first, $L = 2$ if you should choose second, $L = 3$ if it doesn't matter, and $p$ is your winning probability.
Hints
- There are only 4 sequences of length 2, giving 6 distinct matchups. Use the symmetry between $H$ and $T$ (swapping labels maps one problem to another) to cut the work in half.
- For each matchup, ask: what is the first "branching point" where one sequence irrevocably takes the lead? For $HH$ vs. $TH$, think about what happens the moment a $T$ appears.
- After computing all pairwise probabilities, check whether any sequence is dominated -- i.e., can the second mover always find a sequence that beats the first mover's pick with probability strictly greater than $\frac{1}{2}$?
Worked Solution
How to Think About It: There are only four possible sequences -- $HH$, $HT$, $TH$, $TT$ -- so this is small enough to just enumerate all six matchups. The key question is whether any sequence dominates the others badly enough that going second is a huge advantage (as in the length-3 version of Penney's game), or whether the best pair of sequences locks in an even split regardless of order. Start by asking: is there any sequence $X$ such that for every other sequence $Y$, the second mover can pick a $Z$ that beats $X$ with more than 50%? If not, order doesn't matter.
Key Insight: With length-2 sequences, symmetry protects the first mover. The two "fastest" sequences -- $HT$ and $TH$ -- cannot be beaten with better than 50% by any response. So picking either one first is just as good as picking second; the best the opponent can do is also pick a 50/50 match.
The Method:
Because $H$ and $T$ are symmetric (just flip labels), we only need to work out three representative matchups:
Case 1: $HH$ vs. $HT$. Nothing relevant happens until the first $H$ appears. After that first $H$, the next flip is $H$ with probability $\frac{1}{2}$ (giving $HH$) or $T$ with probability $\frac{1}{2}$ (giving $HT$). The two sequences split exactly 50/50.
$P(HH \text{ beats } HT) = \frac{1}{2}$
Case 2: $HH$ vs. $TH$. If the very first flip is $T$, then $TH$ will win. Here is why: once a $T$ appears, the flip history stays in a "waiting for $H
$P(HH \text{ beats } TH) = \frac{1}{4}, \quad P(TH \text{ beats } HH) = \frac{3}{4}$
Case 3: $HT$ vs. $TH$. By the symmetry of the fair coin (swapping all $H \leftrightarrow T$ transforms one sequence into the other), neither sequence has an advantage.
$P(HT \text{ beats } TH) = \frac{1}{2}$
Filling in the table by symmetry: - $TT$ vs. $TH$: mirror of $HH$ vs. $HT$ -- split 50/50. - $TT$ vs. $HT$: mirror of $HH$ vs. $TH$ -- $HT$ wins with probability $\frac{3}{4}$. - $HH$ vs. $TT$, and $HT$ vs. $TH$: fair coin symmetry gives exactly 50/50.
The full win-probability matrix (row beats column):
| | $HH$ | $HT$ | $TH$ | $TT$ | |--------|---------------|---------------|---------------|---------------| | $HH$ | -- | $\frac{1}{2}$ | $\frac{1}{4}$ | $\frac{1}{2}$ | | $HT$ | $\frac{1}{2}$ | -- | $\frac{1}{2}$ | $\frac{3}{4}$ | | $TH$ | $\frac{3}{4}$ | $\frac{1}{2}$ | -- | $\frac{1}{2}$ | | $TT$ | $\frac{1}{2}$ | $\frac{1}{4}$ | $\frac{1}{2}$ | -- |
Optimal play analysis: $HT$ and $TH$ are the "safest" sequences: no sequence beats either one with probability greater than $\frac{1}{2}$. If Player 1 picks $HT$, the best Player 2 can do is pick $TH$ (or $HH$/$TT$), each giving at most 50%. Likewise for Player 1 picking $TH$.
This means the first mover can guarantee at least $\frac{1}{2}$ by picking $HT$ or $TH$. The second mover cannot exploit the first mover's choice to get above $\frac{1}{2}$. Order does not matter -- both players win with probability $\frac{1}{2}$ in equilibrium.
Answer:
$L = 3$ (it does not matter whether you go first or second), $p = \frac{1}{2}$.
$L + p = 3 + \frac{1}{2} = \frac{7}{2}$
Intuition
This problem is a warm-up to the famous Penney's game, where things get far stranger with length-3 sequences. With only two flips, the universe of sequences is small enough that there is no non-transitive cycle to exploit -- $HT$ and $TH$ are jointly "safe" picks that no opponent can beat above 50%. The key structural insight is that $HT$ and $TH$ are the alternating sequences: they each require the coin to "switch," which happens with probability $\frac{1}{2}$ on every flip independent of history. This makes them the fastest to appear on average and hardest to exploit.
With length-3 sequences, going second is always strictly advantageous -- there exists a non-transitive dominance cycle where for any sequence the first player picks, the second player can always find one that wins with probability at least $\frac{2}{3}$. That phenomenon is driven by the asymmetric overlap structure of longer sequences, which simply does not exist for length-2. In practice, problems like this appear in market-making contexts: understanding when you are in a "symmetric" game (where position in the queue does not matter) versus an asymmetric one (where order flow gives a structural edge) is the kind of intuition that separates good traders from great ones.