Waiting for HH vs HT

You will learn: Track overlap states and distinguish first waiting times from pattern frequency.

Start with: Geometric distribution · Markov chains

In two fixed fair-coin flips, HH and HT each have probability one quarter. Starting from no previous flip and watching continuously, however, the expected time to the first HH is six flips, while the expected time to the first HT is four. Equal probabilities in one window do not make overlapping windows independent.

Review geometric waiting and Markov-chain states. A pattern search remembers whether the latest flip was an H that could begin the desired pair.

Head probability p 0.50 Observation cap N 20.00 Random seed 61.00

Independent flips; p changes in percentage-point steps. Both searches start with no previous flip. The time to a pattern includes the flip that completes it.

Solid blue: HH. Dashed red: HT. Steps show discrete first-completion probabilities, including all paths not yet finished.

Quantity	HH	HT
Expected uncapped waiting time	6.000000	4.000000
Probability completed by N	0.9831095	0.9999800
Probability unfinished after N	0.01689053	0.00002002716
Expected min(waiting time, N)	5.911560	3.999958

Reveal one common sequence

No flips revealed.

0 flips revealed. HH: not completed yet. HT: not completed yet.

An unfinished sample has an unknown eventual waiting time, not a recorded completion at the cap. The capped expectation in the table is a different, explicitly truncated quantity. Increasing only N preserves every already generated flip.

Exact two-state recurrences for the first occurrence of each pattern. Equal probability in one fixed two-flip window does not make successive overlapping windows independent.

Two states are enough

Before completion, use state 0 for “no useful trailing H” and state H for “the latest flip is H.” From state 0, a head moves to H and a tail stays at 0 in both searches.

From state H, the searches differ. For HH, another head finishes; a tail erases the partial match. For HT, a tail finishes; another head keeps a useful trailing H. Thus HHH has two overlapping HH occurrences, while HT cannot overlap with itself by one position.

A progress table makes the distinction concrete for HHT: the HH search finishes on flip two; the HT search retains its last H after flip two and finishes on flip three. On HTH, HT finishes on flip two, but HH has not finished by flip three. Neither pattern must win on every sample.

Derive both waiting times

Let e₀ and eH be expected remaining flips in the two transient states, with head probability p. The first-step equation shared by both searches is e₀=1+(1−p)e₀+peH. The “1” counts the next flip, including a completing flip.

For HH, eH=1+(1−p)e₀. Substitution gives:

E[T_{HH}]=e_0=\frac{1+p}{p^2},\qquad p>0.

For HT, eH=1+peH, giving eH=1/(1−p) and:

E[T_{HT}]=\frac1p+\frac1{1-p}=\frac1{p(1-p)},\qquad 0<p<1.

At p=1/2 these are six and four. At p=1, HH finishes on the second flip but HT never occurs. At p=0 neither occurs. For sufficiently large p, HH has the smaller expectation; solving equality gives p=(√5−1)/2≈0.618. The fair-coin ordering is not universal.

Make a prediction

Can you treat each successive pair as an independent trial with success probability 1/4?

Explore the answer

No. Consecutive windows share a flip. HH after an HH can occur again immediately if the next flip is H, whereas HT cannot. Using disjoint pairs would define a different search that ignores patterns straddling pair boundaries.

First arrival is not long-run frequency

In n fair flips, each of the n−1 adjacent windows has probability one quarter of being HH and the same probability of being HT. By linearity of expectation, both patterns have expected count (n−1)/4, even though the window indicators are dependent.

The longer initial wait for HH therefore does not show that HH has a smaller long-run frequency among overlapping windows. HH occurrences can cluster inside runs of heads, leaving longer empty stretches. The starting condition and the way occurrences are counted matter.

Keep unfinished waits visible

The exact recurrence propagates probabilities of both transient states and accumulated completions. The survival probability P(T>k) is the remaining transient mass. Summing these tails gives the capped expectation:

E[\min(T,N)]=\sum_{k=0}^{N-1}P(T>k).

This finite quantity is not the uncapped mean and is not the mean only among completed searches. For example, at N=2 both fair-coin patterns have completion probability one quarter and capped mean two, despite their different eventual means. The revealed sequence reports “not completed yet” when appropriate; it does not invent an ending at the observation cap.

Make a prediction

If the first twenty flips contain no HH, is its waiting time twenty?

Explore the answer

Its waiting time is greater than twenty and remains unknown until completion. Twenty is the capped observation value min(T,20), a different quantity with its own explicitly labeled mean.

Compare the inspection paradox for another example where the observation protocol changes what a waiting-time average means.

Sources

Liviu Nicolaescu’s probability notes, example 3.32 derive the fair-coin first waiting times and discuss pattern overlap. The state equations above also derive the biased-coin results. The first-wait and overlapping-window frequency calculations are deliberately distinguished here.

Reset all settings