Two patterns, one chance, different waits

Toss a fair coin until HTH appears. Toss another until HTT appears. Each pattern occupies any given window of three tosses with probability one in eight, so the two questions look identical.

They are not. HTH takes ten tosses on average and HTT takes eight — and neither number is the eight that cutting a wait into stages and adding would suggest, which is a coincidence in one case and not in the other.

The spread is nearly a factor of two among patterns with identical probabilities, and the quantity that explains it is in the last column: how much of a pattern is left standing when an attempt at it fails.

Why a failure is not a fresh start #

The intuition that gives eight for every pattern is the one that treats the tosses as a sequence of independent windows: there are eight patterns, one in eight windows is the one wanted, so the wait is eight. The windows overlap, and that is the whole problem.

Suppose HTH is wanted and the tosses so far end in HT. The next toss decides:

• H completes the pattern.
• T does not, and the sequence now ends in HTT — but the last letter, T, is no use as the start of HTH, so the attempt restarts from nothing.

Now suppose HTH is wanted and the tosses end in HTH already — that is, the pattern has just appeared and a second appearance is wanted. The last two letters are TH, and the final H is already the first letter of a fresh attempt. A failure leaves progress behind.

Compare HTT. Ending in HT, a T completes it; an H fails, and the sequence ends in HTH, whose final H is the start of a new attempt. So HTT’s failures also leave something. What differs is what happens after a success, and more generally how much of the pattern can overlap itself.

HTH overlaps itself: its first letter is its last. So an appearance of HTH is often the start of the next one, appearances cluster, and clustering means longer gaps between clusters — the appearances are the same in number over the long run and they arrive bunched, so the wait for the first one is longer. HTT does not overlap itself at all, its appearances are spread evenly, and the wait is shorter.

That is the mechanism, and it says something slightly counterintuitive: the pattern that appears in clumps is the one with the longer wait.

The chain that computes it #

The computation is a Markov chain whose states are how much of the pattern has been matched so far, and it is the pattern-matching automaton every text search uses. Like the collector’s chain, it only ever moves forward or stays put — except that here it can also fall back, and the falling back is everything.

From state $i$ — meaning the last $i$ letters of the text are the pattern’s first $i$ — read a letter and move to the length of the longest suffix of the new text that is still a prefix of the pattern. For HTH:

$$\varnothing \xrightarrow{\ H\ } \text{H} \xrightarrow{\ T\ } \text{HT} \xrightarrow{\ H\ } \text{HTH (done)}$$

and the failures: from H a second H stays at H, from HT a T goes back to nothing, from the start a T stays at the start.

Writing $E_i$ for the expected further tosses from state $i$ gives one equation per state, each involving the states the two letters lead to, and solving the small linear system gives $E_0$. For HTH that is a three-by-three system and the answer is ten; for HTT it is eight. Nothing in the computation mentions the pattern’s probability, which is the same for both — it mentions only where the failures land. That is the same shape of answer as the unequal collector’s: a quantity everybody reaches for, in that case the average chance and here the window probability, turns out not to be what decides the wait.

Conway’s rule #

There is a closed form and it is startling: the expected wait is the sum of $2^k$ over every $k$ for which the pattern’s first $k$ letters equal its last $k$.

For HTT: only $k = 3$ works, since H $\neq$ T. So the wait is $2^3 = 8$. For HTH: $k = 1$ works, since the first and last letters are both H, and $k = 3$ works trivially. So the wait is $2 + 8 = 10$. For HHH: $k = 1, 2, 3$ all work. So the wait is $2 + 4 + 8 = 14$.

Every number in the hero figure is that sum, and the figure checks it against the linear system rather than quoting it.

The rule is Conway’s, from the 1970s, and the reason it works is a betting argument worth having because it is the most elegant thing on this page.

Imagine a team of gamblers, one arriving before each toss, each betting one unit at fair odds that the next toss continues the pattern from its beginning, and letting winnings ride. A gambler who arrived at toss $t$ and has matched $k$ letters holds $2^k$; a gambler who has mismatched holds nothing and leaves.

The whole game is fair, so at any time the expected total held by the team equals the total staked, which is the number of tosses so far. When the pattern first appears, the gamblers still holding money are exactly those whose entire run so far matches a prefix of the pattern and whose run ends at the final letter — which is to say, those at the overlap positions. Their holdings are $2^k$ for each overlap length $k$. Fairness gives

$$E[\text{number of tosses}] \;=\; \sum_{k \in \text{overlaps}} 2^k.$$

The expectation is read off a fairness condition rather than computed, and the linear system never appears. That is the optional stopping theorem for martingales, used at its most concrete, and it is the same fair-game bookkeeping that settles when a walk between two barriers stops — there the quantity held is a position and here it is a stake, and in both the fairness is the whole argument.

Longer patterns, and how far the spread goes #

For a pattern of length $L$ the sum runs from $2^L$ upward, so the wait is between $2^L$ — for a pattern that overlaps itself nowhere but trivially — and $2^{L+1} - 2$ for the all-heads pattern, which overlaps everywhere. Every pattern’s wait is within a factor of two of every other’s, which bounds how strange this can get, and the bound is achieved at both ends.

That four-and-six case is worth dwelling on. Waiting for HT takes four tosses and waiting for HH takes six, and both patterns have chance a quarter. The reason, stated as plainly as possible: once an H has appeared, HT is one T away for ever — every subsequent toss is either the T that finishes it or another H that leaves the position unchanged. HH needs two in a row, and a T undoes the progress completely.

The count is the same and the gaps are not #

There is a check worth doing, because the result looks as though it must contradict something.

Over a long stretch of $n$ tosses, HTH and HTT each appear about $n/8$ times. That is not in doubt: the expected number of occurrences is the number of windows times the probability of each, and the probability is the same. So the average gap between consecutive appearances is about eight for both.

And the expected wait for the first appearance is ten for one and eight for the other. Those two statements sit together, and reconciling them is the point.

The resolution is that the average gap and the average wait from an arbitrary starting point are different quantities whenever the gaps are unequal. A run of tosses begun at a random moment is more likely to land inside a long gap than inside a short one, simply because long gaps occupy more of the line — so the gap one lands in is longer than the average gap, by an amount that grows with how variable the gaps are.

HTH’s gaps are more variable than HTT’s: its appearances cluster, producing many very short gaps and some long ones, with the same mean. A random starting point lands in the long ones disproportionately, and the wait comes out longer even though the appearances are equally frequent.

That is the inspection paradox, and it is the same arithmetic as the observation that the bus one waits for is longer-delayed than the average bus, or that a randomly chosen person’s family is larger than the average family. Here it is exact and computable, and the two numbers — mean gap eight, mean wait ten — are both right and are about different questions.

The check completes the account: the probability sets the count, and the overlaps set the variance of the gaps, and it is the variance that the waiting time sees.

The non-transitive consequence #

The clustering has a consequence that goes well beyond waiting times, and it is the most-quoted thing about this subject.

Let two people each choose a pattern of three tosses, and toss until one of them appears; whoever chose it wins. Whatever the first person chooses, the second can choose a pattern that beats it, usually by a wide margin — and the relation beats runs in a cycle, so there is no best pattern.

The recipe is short: given the opponent’s pattern $abc$, choose $\bar{b}ab$, where $\bar b$ is the opposite of $b$. Against HHH choose THH, which wins seven times in eight; against HHT choose THH, which wins three times in four; against HTH choose HHT, which wins two times in three.

Non-transitivity in a setting with no hidden information at all is the striking part. The two patterns are known to both, the coin is fair, and the game is entirely symmetric except in the order of choosing — which is the same asymmetry the leader’s announcement exploits in a completely different subject, and for a reason that is also about what the second mover can condition on.

Conway also gave the odds as a closed form, in terms of the overlaps of each pattern with itself and with the other, and the formula is a ratio of two such sums. It is the same accounting as the waiting time with one pattern’s leading numbers measured against the other’s.

Every pattern of a length, and the shape of the spread #

It is worth asking how the waits are distributed across all patterns of a given length, since the hero figure shows four of eight and the four-toss figure shows four of sixteen.

For length $L$ there are $2^L$ patterns and their waits are $\sum_{k \in \text{overlaps}} 2^k$, always including $k = L$. So every wait is $2^L$ plus a sum of smaller powers of two, and the wait is determined entirely by the set of proper self-overlaps — the autocorrelation of the pattern, in the language of the subject.

Not every set of overlaps is achievable. If a pattern overlaps itself at length $k$ then it is periodic with period $L - k$, and the periods a string can have are constrained: two periods $p$ and $q$ with $p + q \le L$ force a period of $\gcd(p, q)$, which is the Fine–Wilf theorem — a constraint on strings with no probability in it, deciding which waiting times are possible, in the way an arithmetic condition decides which schedules exist. So the possible autocorrelations are a restricted family, and the achievable waits are correspondingly sparse — for three tosses only $8$, $10$ and $14$ occur, never $12$.

Most patterns sit at the bottom. The fraction of patterns of length $L$ with no proper self-overlap at all — the unbordered strings — tends to about $0.2677868$ as $L$ grows, over a binary alphabet, and those all have wait exactly $2^L$. The rest are spread up toward $2^{L+1} - 2$, with the all-heads and all-tails patterns alone at the top.

So the picture across the whole family is a spike at the minimum holding about a quarter of the patterns, a thinning tail above it, and two patterns at the maximum. The two figures in this essay show the extremes and one middle case, which is most of what there is to see.

Where it matters #

Text search. The chain above is the Knuth–Morris–Pratt automaton, and its failure function is exactly the overlap table this essay’s numbers are computed from. A search algorithm and a waiting time are the same object: the algorithm uses the overlaps to avoid re-reading, and the waiting time uses them to say how long until a match.

Cryptographic and statistical randomness tests. A test that counts occurrences of short patterns has to know their expected spacing as well as their expected count, and a generator that passes every count and fails on spacing is the standard failure this arithmetic catches.

Genome and sequence statistics. Deciding whether a short motif appears more often than chance requires knowing what chance is, and chance here is not one in $4^L$ — it depends on the motif’s self-overlaps, and a motif that overlaps itself clusters. Ignoring that is a standard way to produce a false discovery.

And runs in random-looking data. A test that rejects a sequence for containing a long run of heads is using a waiting-time distribution, and the all-heads pattern is the extreme case of this essay’s arithmetic: the longest run in $n$ tosses is about $\log_2 n$, and runs cluster for exactly the reason HHH does — which is why a hand-written fake coin sequence is recognisable: people avoid the clusters that self-overlap produces.

The clustering is the argument and is invisible #

The bars are expectations and each distribution has a heavy right tail. The wait for HTH has mean ten and a standard deviation near ten as well, so a single trial reaching thirty is unremarkable. Nothing in the figure distinguishes a pattern whose wait is reliably ten from one whose wait averages ten by being usually short and occasionally enormous — and the clustering means the second description is nearer the truth.

The clustering itself is invisible. The whole explanation is that HTH’s appearances arrive in bunches and HTT’s do not, and no figure here shows a sequence of tosses with the appearances marked. That would be the picture the argument is about; what is drawn is the number it produces.

And the overlap column is a computed fact about a string, not about a process. It is listed beside each bar because it determines the bar, which is the theorem; a reader could reasonably take the two as separate measurements, and they are not — the second is computed from the first by Conway’s rule and then checked against the chain.

Still open here: three patterns, and a biased coin #

The waiting times are completely understood: a closed form, a proof in three lines, and a bound of a factor of two across all patterns of a length. The competitive version is understood too, for two patterns, by Conway’s ratio.

Where the questions remain is with more than two players, and with biased coins. With three or more patterns competing, the structure of which sets are non-transitive is not fully described, and whether a set of patterns exists in which every member is beaten by another is known for three tosses and open in general. With a biased coin the leading-numbers formula generalises — the powers of two become powers of $1/p$ and $1/q$ matched to the letters — and which pattern is optimal against another moves around as the bias changes, in a way nobody has charted.

The window and the sequence #

The habit is the error the whole essay is about, and it is worth naming in a form that transfers.

The pattern occupies one window in eight, so the wait is eight treats a sequence as a row of independent windows. The windows overlap, so they are not independent, and the dependence is not a small correction — it moves the answer by up to a factor of two and it does so differently for different patterns with identical probabilities.

Where a quantity is defined over overlapping windows, the probability of one window says nothing about the spacing between occurrences. The count over a long stretch is governed by the probability and is the same for all these patterns; the gaps are governed by the overlaps and are not. Averages and waits come apart exactly when events can cluster, and self-overlap is the cleanest mechanism by which they can.