Published
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Longest run of heads
You will learn: Calculate the longest-run distribution without assuming overlapping windows are independent.
Start with: Events and probability · Expectation and variance
In forty fair coin flips, is a run of five heads surprising? The probability of at least one such run is about 0.46791866. That is much larger than the probability 1/32 that five specified consecutive positions are all heads, because a long sequence offers many possible starting positions.
Those opportunities overlap, however. Multiplying their count by 1/32 gives an expected number of successful windows, not the probability of at least one success. The experiment tracks the longest head run exactly under independent flips with fixed head probability p.
Inspect the distribution and a sequence
Filled bars: longest run ≥ 5. Open bars: shorter runs. All run lengths from zero to N remain in the distribution.
| Quantity | Exact value |
|---|---|
| P(longest run ≥ r) | 0.46791866 |
| Expected longest head run | 4.6923061 |
| Expected all-head windows of length r | 1.1250000 |
Inspect one sequence
THTTTHHTHHHTTTHHHTHHHTHTTHHHTTTTTHTHTTHT
This sequence's longest head run is 3. Head runs only; tails separate the runs.
| Head run starts | Ends | Length |
|---|---|---|
| 2 | 2 | 1 |
| 6 | 7 | 2 |
| 9 | 11 | 3 |
| 15 | 17 | 3 |
| 19 | 21 | 3 |
| 23 | 23 | 1 |
| 26 | 28 | 3 |
| 34 | 34 | 1 |
| 36 | 36 | 1 |
| 39 | 39 | 1 |
Filled bars correspond to longest runs at least as large as the selected threshold r. Open bars show shorter outcomes. The sum of the filled probabilities is the requested tail probability. The seeded string and its head-run table illustrate one outcome; they do not estimate the entire distribution from one sequence.
The longest run is zero when there are no heads. With no flips, that is the only possible result. At p = 0 all flips are tails; at p = 1 the entire sequence is one head run. If r exceeds the number of flips, its tail probability is zero even for an all-head sequence.
Count a small example
For ten fair flips there are 1,024 equally likely strings. Exactly 251 contain a run of at least four heads, giving 251/1024 = 0.2451171875. Raising the number of flips to twenty increases this probability to approximately 0.47801876. The event gets more likely because the longer sequence includes the earlier opportunities plus new ones.
For the default forty flips, the expected longest head run is approximately 4.6923061. An expectation need not be an attainable integer run length. At one hundred fair flips it is approximately 5.9917803. These values concern head runs only, not the longer of the longest head run and longest tail run.
Why window counts overstate a probability
There are max(0,n − r + 1) length-r windows in n flips. Each is all heads with probability pʳ, so linearity of expectation gives expected count max(0,n − r + 1)pʳ. Independence between windows is not needed for that expectation.
At n = 40, r = 5, and p = 1/2, the expected count is 36/32 = 1.125. It plainly cannot be a probability. A run of seven heads contributes three overlapping length-five windows; counting all three does not create three different “at least one run” events. The expectation is a union-bound upper bound on the at-least-one probability, but can be loose or exceed one.
Keep two state variables
After each flip, retain the length t of the trailing head run and the largest run m seen anywhere so far. A tail moves this state to (m,0). A head moves it to (max(m,t + 1),t + 1). Multiply the two branches by 1 − p and p, then combine masses that reach the same state.
Starting with probability one at (0,0), repeat those updates n times. Summing across trailing counts leaves the distribution of the maximum. Tracking only the current trailing run would forget an earlier record; tracking only the maximum would lose the information needed to determine whether the next head extends a run.
Make a prediction
You just saw four heads. Does that make a tail more likely on the next flip in this model?
Explore the answer
No. The next flip still has tail probability 1 − p because flips are independent. The existing four-head suffix changes the chance of completing a length-five run on the next step, but it does not change the coin’s probability. Predictions about a pattern and predictions about the next symbol are different questions.
What a streak can establish
Long runs can arise in independent data. Observing a streak is not by itself evidence that the probability changed, and the exact calculation assumes the model rather than testing it. Selecting the most impressive pattern after seeing a sequence also changes the event being evaluated. A planned test should specify whether it concerns heads, tails, either symbol, a fixed window, or the maximum over the whole record.
Reference
Dartmouth’s discussion of statistical issues in streaks distinguishes streak observations and chance models. The recurrence here supplies exact finite-sequence probabilities. Continue with waiting for HH versus HT for the role of overlap in first-arrival times.