The Gold Standard of Probability | Waiting for Overlapping Patterns

Write H for a head and T for a tail. In a continuing stream H, H, T, the adjacent two-toss windows are HH and HT. The second toss belongs to both windows. That shared toss matters when events involving the windows are combined.

The first waiting time counts every toss from an empty start, including the toss that completes the desired pattern. The earliest possible completion is toss two. There is no toss before the recorded start to help form a pattern.

Contrast this with dividing the stream into disjoint blocks: tosses one and two, then three and four, and so on. The HT across the boundary between the blocks HH and TH in HHTH would be eligible in a sliding-window search but could be ignored by a disjoint-block search.

Before calculating, write the exact detection rule. “Wait for two outcomes” leaves open whether adjacent windows overlap, whether failed partial matches are retained and when the clock begins. These are parts of the experiment, not minor presentation choices.

Contents · Next chapter

For HH, an unfinished search needs two states. State 0 means there is no trailing H to help with the next toss. State H means the latest toss was H. A further H from state H completes the pattern; a T returns to state 0.

For HT, the same two state labels work, but their transitions differ. From state H, a T completes HT. Another H keeps the search in state H because that new H can begin a fresh HT.

The tosses themselves have no memory. The search has a state because previous results determine what counts as completion next. This distinction lets independent input produce dependent, overlapping window events without any contradiction.

Contents · Previous chapter · Next chapter

Let E₀ be the expected number of additional tosses needed from state 0, and Eₕ the expected number from state H. For a fair coin, the first-step equations are E₀ = 1 + 0.5E₀ + 0.5Eₕ and Eₕ = 1 + 0.5E₀.

The leading one counts the next toss, whatever it shows. From state H, the head branch finishes and needs zero additional tosses after that next toss. The tail branch returns to state 0.

The first equation rearranges to E₀ = 2 + Eₕ. Substituting into the second gives E₀ = 3 + 0.5E₀, hence E₀ = 6 and Eₕ = 4.

Six is the model mean from an empty start. It is not a guarantee of completion by toss six. Some sequences finish at two, others take much longer. Also notice that having one useful H does not make the expected remaining time one toss. A T can still erase that partial progress.

Contents · Previous chapter · Next chapter

Keep E₀ and Eₕ as expected additional tosses, now for HT. The empty-state equation is unchanged: E₀ = 1 + 0.5E₀ + 0.5Eₕ. The state-H equation becomes Eₕ = 1 + 0.5Eₕ.

A T completes the pattern. Another H consumes one toss but preserves the useful state. Solving gives Eₕ = 2 and E₀ = 4.

Compare this carefully with HH. Both searches wait for a first H. After that H, repeated heads preserve a possible beginning for HT, whereas a tail before HH destroys its beginning. The transition structure changes the expected delay.

The comparison does not mean HT has a larger probability than HH in one prespecified fair pair. Each remains one quarter. It means the first occurrence in an overlapping stream has a different waiting-time distribution. A fixed pair, a first arrival and a long-run count of occurrences are different random quantities. Name the quantity before comparing probabilities or means.

Contents · Previous chapter · Next chapter

If disjoint two-toss blocks are examined, each fair block independently matches HH with probability one quarter. The number of blocks until the first match is geometric with mean four blocks, or eight tosses. The same result holds for HT under that disjoint-block rule.

Those eight tosses do not contradict the sliding-window expectations of six and four. The block procedure discards opportunities crossing block boundaries. It also uses a different unit of trial.

A common mistaken calculation takes the one-quarter probability of a two-toss pattern and treats every new overlapping window as an independent trial. The windows share outcomes. For instance, HH in positions one–two and HH in positions two–three both occur exactly when HHH occurs, with probability one eighth rather than one sixteenth.

For HT in those adjacent positions, both occurrences together are impossible: toss two would need to be both T and H. Thus even two patterns with the same fixed-window probability have different overlap relationships. A geometric model needs its own justified independent trial structure.

Contents · Previous chapter · Next chapter

An expected waiting time does not directly give a deadline success probability. Enumerate all fair sequences of six tosses. There are 64 equally likely sequences.

Let aₙ count sequences of length n containing no HH. Such a sequence either ends in T after any permitted length-n−1 sequence, or ends in TH after a permitted length-n−2 sequence. Thus aₙ = aₙ₋₁ + aₙ₋₂, with a₀ = 1 and a₁ = 2.

The counts through n = 6 are 1, 2, 3, 5, 8, 13 and 21. Therefore HH has appeared by toss six in 64 − 21 = 43 sequences, giving probability 43/64, approximately 67.2%.

A sequence with no HT must consist of some tails followed by some heads. At length six there are seven such sequences, including all tails and all heads. Thus HT appears by toss six with probability 57/64, approximately 89.1%.

These are exact finite-model results, not simulation estimates. They show why a report should preserve both the mean wait and the deadline event that matters to the decision.

Contents · Previous chapter · Next chapter

Let p be the fixed head probability and q = 1 − p the tail probability, with 0 < p < 1. Tosses remain independent. For HH, first-step reasoning gives E₀ = 1 + qE₀ + pEₕ and Eₕ = 1 + qE₀.

Solving gives E₀ = (1 + p)/p². For HT, the state-H equation is Eₕ = 1 + pEₕ, so Eₕ = 1/q and E₀ = 1/p + 1/q = 1/(pq).

Use an invented coin model with p = 2/3. Waiting for HH now has mean (5/3)/(4/9) = 15/4 = 3.75 tosses. Waiting for HT has mean 1/(2/9) = 4.5 tosses. HH now has the shorter expectation.

The earlier fair-coin comparison was conditional on p = 1/2. It was not a universal ranking of two letter strings. Changing the model can change the conclusion. A learner who can explain that reversal understands more than a learner who has memorised the numbers six and four.

Contents · Previous chapter · Next chapter

For HH to have a smaller mean than HT, (1 + p)/p² must be less than 1/[p(1 − p)]. Because the denominators are positive for 0 < p < 1, multiplying through preserves the inequality.

The result is (1 + p)(1 − p) < p, or p² + p − 1 > 0. The relevant boundary is p = (square root of 5 − 1)/2, approximately 0.618.

Below that boundary HH has the longer mean; above it HH has the shorter mean. At the boundary the expectations agree. This boundary concerns the mean waiting times under the stated independent, fixed-p model. It does not say that the two full distributions become identical there.

Check the extremes in words. When heads are very common, finding a tail to finish HT becomes difficult. When heads are rare, obtaining two consecutive heads is particularly demanding. These checks help connect the algebra to the mechanism, rather than leaving the threshold as an unexplained decimal.

Contents · Previous chapter · Next chapter

After HH occurs, its final H can also begin the next HH. The stream HHH contains two overlapping HH windows. If a counter resets by discarding that useful H, it implements a different repeated-detection rule.

For a finite stream of n fair tosses, there are n − 1 adjacent two-toss windows. Each has probability one quarter of being HH, so the expected number of HH windows is (n − 1)/4. The same expectation holds for HT windows. Linearity of expectation does not require these window indicators to be independent.

Equal expected counts can therefore coexist with different first waiting times and different clustering. The apparent conflict disappears once the quantities and starting conditions are named.

This distinction transfers to pattern detection in supplied inspection records or message sequences. Are we counting all matches, recording only the first, or restarting after each accepted match? Are overlaps retained? A result is interpretable only when the detection rule accompanies it. The coin example establishes the logic, not empirical performance in another system.

Contents · Previous chapter · Next chapter

A small program or spreadsheet can maintain the unfinished states after each toss. Starting from probability one in state 0, distribute each state’s probability along its H and T transitions, and accumulate probability in the completed state.

For a fair six-toss search, the accumulated completion probabilities should reproduce 43/64 for HH and 57/64 for HT. Total unfinished plus completed probability must remain one at every step.

In a simulation, record each run’s full waiting time. If a maximum length is imposed, keep unfinished runs identified; averaging only finished runs biases the reported wait. The existing retry-limit guide develops that censoring issue for a simpler first-success model.

Choose checks that challenge the implementation: a stream with all heads, all tails, HHT and repeated H blocks before a tail. Verify the state after each new symbol. A large number of random runs can hide a transition error that a three-symbol hand check would expose immediately.

Contents · Previous chapter · Next chapter

Check one: completion within three tosses

For a fair coin, HH occurs by toss three in HHH, HHT and THH, so the probability is 3/8. HT occurs in HHT, HTH, HTT and THT, giving 1/2. Counting the named sequences avoids assuming independent overlapping windows.

Check two: the biased deadline

With p = 2/3, the HH event above has probability p³ + p²q + qp² = 16/27. The HT event has probability p²q + pqp + pq² + qpq = 4/9. The head-heavy model changes the deadline comparison as well as the expectations.

Check three: an extra consecutive head

For fair HHH, use states 0, H and HH. The equations are E₀ = 1 + (E₀ + Eₕ)/2, Eₕ = 1 + (E₀ + Eₕₕ)/2 and Eₕₕ = 1 + E₀/2. Solving gives E₀ = 14 tosses.

Explain why eight, the reciprocal of the fixed three-head probability, does not answer this waiting question. The missing argument concerns overlapping opportunities and retained partial progress.

Contents · Previous chapter · Next chapter

Do independent tosses make all derived events independent?

No. Events built from shared tosses can depend on each other. Independence must be checked for the actual events being combined.

Does an expected wait of six mean a 50% chance by six?

No. The mean does not define that percentile. Our fair HH calculation gives 43/64 by toss six.

Is the next toss affected by a previous run?

Under the stated fixed-p independent model, no. Previous outcomes affect the search state, not the next-toss head probability. A changing mechanism would require another model.

Which reading route comes next?

For foundations, return to The Gold Standard of Probability, conditional probability and expected value. For state design and hitting times, continue with How Markov Chains Work and Mathematics Mastery: Markov Chains.

For comparisons of different dependence mechanisms, read first success, retry limits and unfinished runs, sampling without replacement and the first defect and reinforced urns and equal marginals. These change different parts of an experiment; they are not interchangeable corrections.

For learning across subjects, use The Gold Standard of Education and How X Works.

Expected Lengths and the Paradox of the Common Man, hosted by Kansas State University, develops consecutive-head waiting times. Rick Durrett’s Essentials of Stochastic Processes, Chapter 1, provides a formal Markov-chain treatment of pattern waiting. The deadline enumerations, biased comparison and model-repair exercises here are worked directly from the stated rules.

Contents · Previous chapter · Return to Probability