The longest run has no limit

Two-thirds of a step past the line ended with a question about races between coin patterns: whether all sixteen patterns of length four, raced at once, finish in an order that can be read off their overlaps. That question turns out to have a trivial answer. Every window of four tosses is one of the sixteen patterns, so the race always ends at the fourth toss, and each pattern wins with chance exactly one in sixteen. The interesting races are the ones in which some outcome is not covered, and the most extreme of those is a single pattern that is very long: a run of heads.

This essay is about the longest run of heads in $n$ tosses of a fair coin — the largest $k$ such that $k$ heads appear in a row somewhere. Two patterns, one chance, different waits mentioned in passing that it is about $\log_2 n$. That is true, and the average is known to remarkable precision. What is surprising is that the distribution of the longest run has no limit at all. It does not converge to anything as $n$ grows; it cycles.

The three distributions in the figure are for 65,536, 82,273 and 104,408 tosses, and they are drawn against the run length minus $\log_2 n$, so that a common limiting shape would put them on top of one another. They do not coincide. The bars sit at different horizontal positions, and their heights differ. Double $n$ and each shape comes back exactly, shifted by one. That is the whole story in one picture, and the rest of the essay computes it.

A wait that has already ended #

The longest run is a waiting time in disguise. The longest run in $n$ tosses is at least $k$ exactly when a run of $k$ heads has appeared by toss $n$ — that is, when the wait $T_k$ for the first run of $k$ heads is at most $n$. So the distribution of the longest run is the distribution of every waiting time $T_1, T_2, T_3, \ldots$ read off at a single moment.

The waits are the ones computed earlier for coin patterns. A run of $k$ heads is a pattern that overlaps itself at every shift, which is the worst case for waiting: the mean wait is $2^{k+1} - 2$, twice what a pattern with no self-overlap of the same length would take. The figure below checks that mean from the chain whose state is the current run length — each toss either extends the run by one or resets it to zero — and checks the whole distribution of the longest run against a simple approximation.

The approximation is easy to explain. A run of $k$ heads begins at a given toss when that toss is a head preceded by a tail — or by the start — and followed by $k - 1$ more heads: probability $2^{-(k+1)}$. Such beginnings are rare and almost independent, so their number by toss $n$ is nearly Poisson with mean $n/2^{k+1}$, and the chance of none is $\exp(-n/2^{k+1})$. The exact calculation uses a recurrence for the chance $q_k(n)$ that $n$ tosses contain no run of $k$:

$$q_k(n) = q_k(n-1) - \frac{q_k(n-k-1)}{2^{k+1}},$$

which subtracts, from the sequences of length $n - 1$ with no run, those that complete a first run at toss $n$ — and such a run must be a tail followed by $k$ heads, with no run in the $n - k - 1$ tosses before. Every figure in this essay comes from running that recurrence for every $k$ up to 44 and every $n$ up to $2^{20}$, a little over a million, and the recurrence was checked against a direct count of all $2^n$ sequences for $n$ up to 14.

The average settles #

Write $L_n$ for the longest run in $n$ tosses. Its average can be computed from the distribution, and it settles beautifully.

The average approaches $\log_2 n - 0.66725$ within a few doublings, and by a million tosses it is within three millionths of it. The constant has an exact form, $\gamma/\ln 2 - 3/2$, with $\gamma = 0.5772\ldots$ Euler’s constant — the same constant by which the harmonic numbers exceed the logarithm in the collector’s problem, and for a related reason. The longest run is the largest of many nearly independent, geometrically distributed run lengths, and the average of a maximum of that kind is a logarithm plus a constant built from $\gamma$.

The route to the constant is short. The average of a quantity that takes the values $0, 1, 2, \ldots$ is the sum of its tail probabilities, $\sum_{k \ge 1} P(L_n \ge k)$. By the previous figure each tail is close to $1 - \exp(-n/2^{k+1})$, which is nearly 1 for $k$ well below $\log_2 n$ and nearly 0 well above it. The sum is therefore about $\log_2 n$ — the number of terms close to 1 — plus a correction from the terms in the transition, and that correction is a sum of the form $\sum_j \left(1 - e^{-2^{j}}\right)$ against $\sum_j e^{-2^{-j}}$ over the halvings and doublings around the transition. Sums over powers of two of that kind are evaluated by turning them into integrals of $e^{-x}$ against $dx/x$, and $\int (e^{-x} - \text{its step approximation})\,dx/x$ is exactly where Euler’s constant lives. The $-3/2$ splits as $-1$, from the exponent $k + 1$ in the rate $2^{-(k+1)}$ — a run needs a tail in front of it, which halves the rate and costs one doubling — and $-1/2$, the average price of replacing a sum over whole numbers by an integral — the same rounding to whole numbers that, further down, adds $1/12$ to the variance.

The average is not quite settled, though. Over the last doubling computed it still moves by about four millionths, and part of what moves is an oscillation of period one in $\log_2 n$ that never dies out. Its amplitude is so small that no figure scaled to show the average can show it, and the computed averages, which move by a few millionths over the last doubling, bound it. That small oscillation is the trace, in the average, of something that in the distribution is not small at all.

The distribution cycles #

The figure that shows the failure to converge plots the probability of individual values.

Each curve is a sawtooth with one tooth per doubling of $n$, and the teeth do not shrink. The chance that the longest run equals $\lfloor \log_2 n \rfloor$ swings between 0.172 and 0.238 at the beginning of the range and between exactly the same values at the end. At each power of two the floor of $\log_2 n$ steps up by one, every curve jumps to a different value, and the cycle begins again. Even which value is the likeliest changes within each doubling: just after a power of two the likeliest value is $\lfloor \log_2 n \rfloor - 1$, and just before the next it is about to become $\lfloor \log_2 n \rfloor$ — which, as soon as the power of two is passed, is renamed $\lfloor \log_2 n \rfloor - 1$.

The reason is arithmetic, not probability. A continuous quantity near $\log_2 n$ with a fixed spread would have a limiting shape once $\log_2 n$ is subtracted. The longest run is a whole number. As $n$ doubles, $\log_2 n$ advances by one, and in between it passes smoothly through every fractional value, while the possible values of the run stay put at the integers. The same continuous shape is sliced at the integers in a different place for every fractional part of $\log_2 n$, and the slices come round again at every doubling. A distribution that depends on the fractional part of $\log_2 n$ cannot converge as $n \to \infty$, because the fractional part does not.

The cycle itself #

Plotting the probabilities against the fractional part of $\log_2 n$ instead of $\log_2 n$ itself folds the sawteeth into a single closed curve.

For large $n$ every value of $n$ with the same fractional part of $\log_2 n$ gives the same probabilities, so the curves for $n$ beyond 131,072 lie on a single cycle, and the dots for $n$ between 512 and 1,024 already lie nearly on it. The cycle is predicted exactly by the waiting-time approximation: the chance that the longest run is below $k$ is close to $\exp(-n/2^{k+1})$, which depends on $n$ only through $n/2^{k+1}$, and when $k$ is measured from $\lfloor \log_2 n \rfloor$ that ratio depends only on the fractional part. The formula is the extreme-value law of Emil Gumbel, the limiting law for the maximum of many independent quantities with exponential tails, cut into whole numbers. The cut is what makes the law cycle instead of converge.

This is the opposite of what a central limit theorem leads one to expect. Sums of many independent quantities settle into a bell curve once they are centred and scaled, whatever the quantities. Maxima of many independent quantities settle into one of three extreme-value shapes — when the quantities are continuous. When they are whole numbers with geometric tails, as run lengths are, there is no limit at all, only this cycle. The tail is not a bell found that the extremes of a sum obey laws the bell does not describe; here the extreme does not obey a limit law of any kind.

A spread that does not grow #

The variance tells the same story in its own terms.

However many tosses, the longest run is pinned to $\log_2 n$ within a couple of units: its variance does not grow with $n$ but settles at about 3.507. The value has two parts. The variance of Gumbel’s law, measured in units where one unit is a doubling, is $\pi^2/(6 \ln^2 2) \approx 3.4237$. Rounding a continuous quantity to the nearest whole number, at a position that is uniformly spread through the cycle, adds the variance of a uniform error on an interval of length one, $1/12 \approx 0.0833$. Their sum is $3.5070$, and the computed variance at a million tosses is 3.5070. Like the average, the variance carries an oscillation of period one in $\log_2 n$, too small to draw.

Why the average hardly moves #

The cycle is large in the probabilities and tiny in the average, and the contrast has a precise cause. Any quantity that depends on $n$ only through the fractional part of $\log_2 n$ can be written as a Fourier series in that fractional part, a sum of waves $e^{2\pi i m \log_2 n}$. For the average of the longest run, the coefficient of the $m$-th wave turns out to be a value of Euler’s gamma function at the imaginary point $2\pi i m/\ln 2$, divided by $\ln 2$. Far up the imaginary axis the gamma function is extraordinarily small: its size there falls like $e^{-\pi |t|/2}$, and at $t = 2\pi/\ln 2 \approx 9.06$ that is about $e^{-14.2}$, below a millionth. So the oscillation in the average is real, has period one in $\log_2 n$, never dies out, and is about a millionth in size.

The probabilities have no such protection. Their Fourier coefficients are not values of a smooth function evaluated far out, but the coefficients of a sawtooth, with a jump at every power of two, and a jump’s Fourier coefficients fall only like $1/m$. The same arithmetic produces a cycle of size a tenth in the probabilities and a millionth in the average. It is the same mechanism multiplying makes the digit one common used for leading digits: a quantity periodic in a logarithm, whose size depends on how smooth the periodic function is.

Why there is a cycle at all #

The cycle needs one more ingredient besides a whole-number quantity tracking a logarithm: the spread must stay bounded. If the spread grew with $n$, the integer slicing would become finer and finer relative to the shape, and the dependence on the fractional part would wash out. That is what happens to the longest climb of a shuffle, another longest-something in a random arrangement: it is a whole number too, near $2\sqrt n$, but its fluctuations grow like $n^{1/6}$, and centred and scaled it converges to a fixed limiting shape. The longest run’s spread is stuck at about $\sqrt{3.5} \approx 1.9$ for every $n$, so the slicing never gets finer, and the cycle never fades.

The same holds for a biased coin. With heads coming up with probability $p$, the longest run is about $\log_{1/p} n$, its variance again settles to a constant, and the probabilities cycle with period one in $\log_{1/p} n$ — once every time $n$ is multiplied by $1/p$ rather than by 2. The fair coin is the case in which the cycle’s period is a doubling.

The averages hide the cycle because averaging over the slices smooths it: each moment of the distribution is a sum over all the slices, and the sums barely depend on where the slicing falls. Only the individual probabilities expose it. Small cases lie, and here large cases lie as well: no value of $n$, however large, shows the limit, because there is none.

What runs in random data look like #

The longest run is a practical statistic. Tests of randomness check whether a sequence contains runs as long as a random sequence would, and a person writing down a “random” sequence of a hundred coin tosses almost always makes the longest run too short — four or five, when the average for a hundred fair tosses is about six. Twenty-three people noted that fake sequences are recognisable for exactly this reason: people avoid the clusters that self-overlapping patterns produce, and a run of heads is the pattern that overlaps itself most.

The cycle matters for such tests only in a mild way. A test that compares the longest run in $n$ tosses with a fixed table of probabilities is using a distribution that depends on where $n$ falls between powers of two, and a table computed for one $n$ is not right for another a little larger. The exact recurrence costs almost nothing to run, and the safe practice is to compute the distribution for the $n$ in hand.

Still open: runs in sequences that are not independent #

For independent fair tosses everything here is exact: the recurrence, the cycle, the constants. The open questions begin when the tosses are not independent. For the binary digits of numbers like $\sqrt 2$ or $\pi$, whose normality is itself unproved, nobody can prove that the longest run of ones among the first $n$ digits grows like $\log_2 n$ — though every computation agrees, and almost every orbit is fair explained why almost every number behaves this way. For sequences with dependence that decays, such as the output of a Markov chain, the longest run is known to be logarithmic with a constant set by the chain, and the oscillation persists; how large it is, and how it depends on the chain, has been worked out only for special cases. And for the longest run of a pattern other than all heads — the longest stretch of repeated HTH, say — the waiting-time picture generalises, but the constants depend on the pattern’s overlaps in ways that are known one pattern at a time.

Settled on average, cycling in detail #

The longest run of heads in $n$ tosses is a very predictable quantity: within a couple of units of $\log_2 n - 0.667$, with a variance of 3.507 that does not grow. Its average and variance settle to constants built from $\gamma$ and $\pi^2$. And its distribution never settles at all, because a whole number cannot follow a logarithm smoothly; the chance of each value goes round the same cycle once every time the number of tosses doubles. Computed exactly to a million tosses, the cycle at the end is the cycle at the beginning.