Coin Toss Patterns & Penney's Game

Expected waiting times, competing patterns, and the second-player advantage

Part A — Expected Number of Tosses

1. Expected Tosses Until HHH

Let Eₙ be the expected number of tosses required to obtain n consecutive heads.

Eₙ = 2Eₙ₋₁ + 2

with

E₁ = 2.

Solving the recurrence gives

Eₙ = 2n+1 − 2.

For three heads:

E₃ = 2⁴ − 2 = 16 − 2 = 14.
Expected tosses until HHH = 14

State intuition

Start
0 heads
→ H →
H
→ H →
HH
→ H →
HHH

The important difficulty is that a tail can destroy the progress toward HHH.

For example: 

HH + T  →  HHT
           ↑
      progress resets

Therefore HHH takes considerably longer than the naive 2³ = 8 tosses.

2. Expected Tosses Until THH

THH behaves differently because it has no non-empty self-overlap.

Prefix Suffix Match?
T H No
TH HH No

For a length-3 pattern with no self-overlap, the expected waiting time is simply

2³ = 8.
Expected tosses until THH = 8
Interesting contrast:

HHH and THH each have probability 1/8 of appearing in any particular block of three tosses.

But their expected waiting times are different:

E(HHH) = 14
E(THH) = 8.

The difference comes from pattern overlap.

Part B — Which Appears First: HHH or THH?

Now suppose we continually toss a fair coin until either HHH or THH appears.

The key observation is to think about the first occurrence of HH.

Case 1 — The first HH is preceded by T

... T H H

Then we have just formed THH.

THH wins immediately.

Case 2 — There is no preceding T

For HHH to beat THH, the sequence must begin:

H H H.

Its probability is

P(HHH first) = (1/2)³ = 1/8.
P(HHH appears before THH) = 1/8

Therefore:

P(THH appears before HHH) = 1 − 1/8 = 7/8.
THH wins with probability 7/8 = 87.5%

Part C — Penney's Game

Penney's game has two players:

  1. Player 1 chooses a three-toss sequence.
  2. Player 2 sees it and chooses a different sequence.
  3. A fair coin is tossed repeatedly.
  4. The first chosen pattern to appear wins.

The Second-Player Strategy

Suppose Player 1 chooses

A B C.

A strong optimal response for Player 2 is

opposite(B) + A + B.
Important correction:

The rule is not generally “take Player 1's last two symbols and prefix their opposite.”

The usual construction is:

complement(second symbol) + first two symbols.

Example

Player 1 chooses:

HHH

The second symbol is H, whose opposite is T.

The first two symbols are HH.

Therefore Player 2 chooses:

T + HH = THH.
HHH vs THH → Player 2 wins with probability 7/8.

Why the Second Player Has an Advantage

The patterns overlap asymmetrically.

Whenever HHH is about to occur, the sequence often creates THH first. 

... T H H H
    └───┘
     THH

      └───┘
       HHH

THH therefore steals many of the paths that would otherwise eventually produce HHH.

Interactive Penney's Game Explorer

Choose Player 1's pattern. The optimal response for Player 2 is generated automatically.

Player 1

HHH

Player 2

Optimal response
THH
Winning probability: 87.5%

Interview Memory Trick

Question Think About
Expected waiting time Pattern self-overlap
Two patterns racing Useful suffix / state transitions
Penney's game opposite(second) + first two symbols
HHH expected waiting time = 14
THH expected waiting time = 8
P(HHH before THH) = 1/8
P(THH before HHH) = 7/8