A wait that ends and has no average

Every wait in this collection so far has had an answer. Collecting all six faces of a die takes fourteen point seven throws on average. Waiting for HTH on a fair coin takes ten tosses, and HTT eight. The answers were sometimes surprising and sometimes needed a clever accounting, but there always was one: a number, finite, that a long run of experiments would average out to.

Here is a wait that has none. Draw a number at random — from any continuous distribution: heights, rainfall, the output of a random-number generator. Then keep drawing until a number turns up that is larger than the first. Count the further draws needed. Call it $W$.

The wait is certain to end. It is usually short — half the time the very next draw does it. And its average is infinite. Not large: infinite, in the precise sense that the averages of more and more independent copies of $W$ grow without bound and settle on nothing. The reason is a single line of symmetry, and that line does not mention the distribution at all.

The line that does all the work #

Ask for the chance that after $n$ further draws the wait is still going. That happens exactly when the first draw is the largest of the first $n + 1$. Among $n + 1$ draws from a continuous distribution there are no ties, and every one of them is equally likely to be the largest — the draws are independent and identically distributed, so no position can be favoured. The first is the largest with chance $1/(n + 1)$.

$$P(W > n) = \frac{1}{n + 1}.$$

That is the whole distribution. The chance that the wait is exactly $n$ is the difference $\frac{1}{n} - \frac{1}{n+1} = \frac{1}{n(n+1)}$. Half the waits are one draw, a sixth are two, a twelfth are three. Ninety per cent are over within nine draws.

And the average is the sum of the tail chances, a standard identity for any wait counted in whole steps:

$$E[W] = \sum_{n \ge 0} P(W > n) = 1 + \tfrac12 + \tfrac13 + \tfrac14 + \cdots,$$

which is the harmonic series, and it diverges. Every individual wait ends; their average does not exist.

Nothing about the distribution entered. The argument used only that the draws are independent, alike, and never tie. That is unusual enough to be worth checking.

The four distributions could hardly be more different. The uniform is bounded; the normal has thin tails; the exponential is lopsided; the Cauchy has tails so heavy that it has no mean of its own. Their waits are indistinguishable. The figure is a picture of a statement about ranks, and ranks do not know what scale they were measured on.

Why the earlier waits were finite and this one is not #

The coupon collector and the coin patterns had finite averages for a reason that can be named. At every step of those waits there was a chance, bounded away from nought, of finishing within the next few steps. Waiting for HTH, whatever has happened so far, the next three tosses complete the pattern with chance at least one in eight. A wait with that property has a tail that falls geometrically — the chance of lasting another three tosses is at most seven-eighths each time — and a geometric tail has a finite sum.

The wait for a record has no such floor. Once the wait has gone on for $n$ draws, the evidence says the first number was unusually large: it beat $n$ others. The chance that the next draw beats it is $1/(n + 2)$, conditional on having waited this long, and that chance shrinks as the wait grows. The longer the wait has been, the longer it is likely to be. Its tail falls only like $1/n$, and a $1/n$ tail is exactly the borderline the harmonic series sits on: anything faster would sum, and this does not.

That is the difference between this wait and the ones before it. The coupons and patterns were waits for a fixed target, which a memoryless process keeps a constant chance of hitting. The record is a target set by the process itself, and the process sets it higher the longer the wait drags on.

The same $1/n$-type borderline has appeared once before, in a different guise. A fair random walk returns to its starting point with certainty, and the reflection principle shows that its first return has a tail falling like $1/\sqrt n$ — slower still, and again an infinite average. What is new here is that no walk, no lattice and no particular distribution is needed. The record wait is the purest case: a $1/n$ tail produced by nothing but the order of independent draws. Even the race between patterns that beat one another in a circle ended in finite expected time, because each pattern was a fixed target; a record is a target that moves.

An average that will not settle #

What does an infinite average look like in practice? Not like a large number. Sample a million waits, average them, and the result is a perfectly ordinary finite number — about thirteen or fourteen. Sample a second million and average again, and the answer is again about fourteen, unless one wait in the second million happens to be enormous.

Every run climbs. The averages after a hundred waits sit near five; after a million, near thirteen; and they climb about $2.3$ — that is, $\ln 10$ — for each further factor of ten. The jumps are visible: one run is thrown up to eighty-five by a single wait of more than a hundred thousand draws, and then decays slowly as the ordinary waits dilute it, until the next large one arrives.

The dashed line explains the drift. In a sample of $N$ waits, a wait much longer than $N$ is unlikely to appear at all, so the average behaves like the average of the wait cut off at $N$: $\sum_{n < N} \frac{1}{n+1}$, which is about $\ln N + \gamma$, where $\gamma \approx 0.577$ is Euler’s constant. The runs sit mostly a little below the line — the average of a heavy-tailed sample is usually below its truncated mean, and occasionally far above it — and they never level off, because the line does not.

This is the law of large numbers failing in the only way it can: its hypothesis is a finite mean, and here the mean is not finite. A weaker law, in the form William Feller gave for heavy tails, still says something — the sum of $N$ waits divided by $N \ln N$ tends to one in probability — but even that holds only in probability. Yuan Shih Chow and Herbert Robbins showed in 1961 that when the mean is infinite, no rescaling of the running sum converges along almost every sequence of draws. Any single run, followed for ever, keeps being thrown off by a later giant. The envelope paradox and the St Petersburg game live in this same territory, where a quantity is finite every time it is observed and its expectation is not.

Records, counted #

The wait $W$ is the gap to the first record after the first draw. Turn the question round and ask how many records a long sequence holds.

The $k$-th draw is a record when it is the largest of the first $k$, which by the same symmetry happens with chance $1/k$. Alfréd Rényi noticed in 1962 something sharper: these events are independent of one another. Whether the tenth draw is a record says nothing about whether the hundredth is, because the hundredth’s rank among the first hundred is independent of the order of the first ten among themselves. So the number of records among $n$ draws is a sum of independent coin flips with chances $1, \tfrac12, \tfrac13, \ldots, \tfrac1n$, and by the linearity of expectation its mean is the harmonic number $H_n = 1 + \tfrac12 + \cdots + \tfrac1n$.

A hundred draws hold about five records; a thousand, about seven and a half; a million, about fourteen. The distributions are narrow — the variance is $H_n - \sum 1/k^2$, about $\ln n$ — and they creep to the right by $\ln 10 \approx 2.3$ per factor of ten. The exact probabilities are a classical object in disguise: the chance of exactly $k$ records among $n$ draws is the number of permutations of $n$ things with $k$ cycles, divided by $n!$, because a standard bijection sends the records of a sequence to the cycles of a permutation — the same cycles that decide how many guests get their own hat back.

Records keep coming for ever — the harmonic series diverges, so there is no last one — and they come slower and slower. Read through a stable climate’s temperature record, with each year an independent draw from the same distribution, and in the hundredth year the chance of a new record is one in a hundred. Eight records in a thousand years would be ordinary. The same counting runs the best strategy for choosing the best of a sequence seen one at a time: the only candidates worth stopping for are records, and the strategy is a rule about which record to accept.

When the kth record arrives #

The positions of the records grow in a pattern as regular as their count.

If the latest record arrived at draw $T$, the next one comes after draw $m$ only if the record so far is still the largest of the first $m$ — chance $T/m$. That is the original wait with a head start: the chance of still waiting after $m$ more draws, given the record held for $T$, is $T/(T + m)$. Its average, too, is infinite. Every record, once set, is followed by a wait with no average.

Taking logarithms tames it. The ratio of successive record positions is roughly the reciprocal of a uniform random number, so its logarithm is an exponential random variable with mean one: each record arrives, typically, about $e \approx 2.72$ times further along than the one before. The logarithm of the $k$-th record’s position is close to a sum of $k$ such exponentials, with mean about $k$ and spread about $\sqrt k$ — the fan of runs in the figure, centred on the dashed line. The thirtieth record is, typically, four million million draws in. The arithmetic is the coupon collector’s harmonic numbers turned inside out: there, the harmonic sum was the wait for the last stages; here, it is the count, and the wait is its exponential.

Ties, and the limit that makes it certain #

The symmetry used one assumption that is easy to miss: no ties. Draws from a continuous distribution are almost surely distinct. A die is not like that, and the difference is instructive.

Roll a die and wait for a strictly higher roll. If the first roll is a six, the wait never ends: chance one in six. Otherwise, starting from $r$, each roll beats it with chance $(6 - r)/6$, so the wait is geometric with mean $6/(6 - r)$ — short and well behaved. The waits that end average $137/50 = 2.74$ rolls. So the die’s wait is the opposite of the continuous one: it fails to be certain, and given that it ends, it has a perfectly good average.

Refine the die to $K$ faces and both features change together. The chance of an endless wait, $1/K$, shrinks to nothing. The average of the waits that end, $\frac{K}{K-1}\left(1 + \tfrac12 + \cdots + \tfrac1{K-1}\right)$, grows like $\ln K$. At a million faces the wait fails to end once in a million and otherwise averages fourteen draws. The continuous case is the limit of both trends at once: the endless waits disappear, and the average they leave behind is pushed to infinity.

That is a good way to see where the infinity comes from. It is the probability that, in the die, sat on “never” — the first draw happening to be the maximum possible value — smeared out, in the continuous case, over the first draws that are merely very large. A first draw in the top thousandth of the distribution produces a wait of about a thousand; the top millionth, about a million. Each band contributes the same amount to the average, and there are infinitely many bands.

What can still be averaged #

An infinite mean does not leave the wait without a summary. It leaves it without that summary, and the alternatives are worth having, because they are what a sensible report of such a wait should use.

The median is one draw: half of all waits end immediately. The upper quartile is three draws, since the chance of waiting more than three is a quarter. The ninetieth percentile is nine, the ninety-ninth is ninety-nine. Every quantile exists and has a formula — the chance of waiting more than $n$ is $1/(n + 1)$, so the fraction $q$ of waits is over by $1/(1 - q) - 1$ draws — and none of them is affected by the giant waits that wreck the average.

Averages of smaller powers survive too. The average of $\sqrt W$ is finite, about $1.83$, because the tail of $\sqrt W$ falls like $1/n^2$ and that sums. The average of $W^{0.9}$ is finite, about $5.50$. The average of $W^a$ is finite for every power below one and blows up as the power approaches one, like $1/(1 - a)$; the plain average, at power exactly one, is where it gives out. The logarithm is better behaved still: the average of $\ln W$ is $\sum \frac{\ln n}{n(n+1)} \approx 0.786$, and a sample of a million waits estimates it to three decimal places, where the same sample cannot estimate the plain mean at all.

So the trouble is specific. It is not that the wait is wild in every respect — it is short, in the median, and tame on a logarithmic scale. It is that the plain average weighs each wait by its length, and a $1/n$ tail is exactly heavy enough for those weights to add up to infinity. The choice of summary is a choice about how much weight to give the rare enormous waits, and the arithmetic mean gives them the most of any of these.

Finite samples of an infinite mean #

No figure here shows an infinite average. Every one of them shows finite samples, and the average of a finite sample is finite. What the figures show is the signature of an infinite mean: the averages climbing in figure after figure, a single wait moving a million-sample average by a large fraction, the logarithmic drift that matches the truncated mean. The statement that the mean is infinite is proved by the one line of symmetry and the divergence of the harmonic series, and the pictures are consistent with it in the only way a picture can be.

The tail figure checks $1/(n + 1)$ out to two thousand draws for four distributions. The theorem covers every continuous distribution and every $n$. And the claim that the record events are independent, which gives the exact distribution of the record count, is Rényi’s theorem; the bars are computed from it rather than verifying it.

Still open: records when the draws are not alike #

Everything above depends on the draws being identically distributed. Real sequences — temperatures in a warming climate, athletic performances in a growing population — are not: there is a trend, and with a trend the symmetry is gone. The chance that the $k$-th draw is a record is no longer $1/k$; with a steady upward drift and a distribution whose tail is not too heavy, it no longer falls to nought at all. Richard Ballerini and Sidney Resnick showed in 1985 that under a linear trend the long-run share of draws that are records then tends to a positive constant, so records stop thinning out. What that constant is depends on the shape of the distribution’s tail, and closed forms exist only for a few special distributions.

That leaves practical questions without clean mathematical answers. How much of an observed surplus of records can be attributed to a trend of a given size, when the distribution’s tail is itself estimated from the same data? The distribution-free magic of the stable case — the reason the four distributions in the tail figure agree — is exactly what a trend destroys, and no replacement statement of comparable generality is known.

The harmonic series as a wait #

The wait for a record is the harmonic series turned into a random variable. Its tail is $1/(n + 1)$; its average is $\sum 1/n$; the number of records it produces in $n$ draws averages $H_n$; the averages of many copies drift like $\ln N$. The divergence that is a curiosity in a table of series becomes, here, something that can be run on a computer and watched failing to settle.

And it comes from the least possible assumption. The coupon collector needed the kinds to be equally likely; the coin patterns needed the coin to be fair, or at least known. This wait needs nothing but independent draws that never tie, and the answer is the same for every distribution in existence — which is also why it cannot have an average: nothing about any distribution can bound it.