Two-thirds of a step past the line

Draw numbers evenly between nought and one and add them up until the total passes one. How many draws does it take on average? The answer is $e = 2.71828\ldots$, and it is one of the prettiest facts in elementary probability: the constant that counts what does not happen turns up because the chance that $n$ draws all fit below one is the volume of a corner of the $n$-dimensional cube, $1/n!$.

The natural next question is rarely asked. What about passing two, or ten, or $t$? Each draw averages a half, so passing $t$ should take about $2t$ draws. It does — plus a constant. The constant is not nought, and it is not a half, which is what a first guess about “the last step overshooting” suggests. It is two-thirds, and it is where this essay goes. The curve that reaches it has an exact formula, a ripple that dies away eightfold per unit, and a constant that turns out to depend on nothing but how much the steps vary.

The wait for a record had no average at all, because its target moved away the longer the wait went on. This target stands still, and the question is the reverse one: not whether the average exists, but exactly how it behaves.

Passing a line, once #

Start with the picture. A running total of random steps is a staircase, and the count is the number of treads before it clears the line.

Four totals, four counts: eleven, eight, eight, ten. The average count is $8.6666\ldots$ — almost exactly $2 \times 4 + \tfrac23$, short of it by six parts in a hundred thousand. Note the last tread of each staircase. It starts below the line and ends above it, and the amount it ends above is the overshoot. If the steps were all exactly a half long, the count would be $\lfloor 2t \rfloor + 1$, which averages $2t + \tfrac12$ over the possible positions of the line. Random steps add a sixth.

For the first unit, the count can be had exactly by the argument that gives $e$. The count exceeds $n$ when the first $n$ steps sum to at most $t$, and for $t \le 1$ that is the corner of the cube cut off by the plane $x_1 + \cdots + x_n = t$, a simplex of volume $t^n/n!$ — the same corner that counts the orderings of $n$ numbers. The average of a whole-number count is the sum of its tail chances, so

$$m(t) = \sum_{n \ge 0} \frac{t^n}{n!} = e^t \qquad (0 \le t \le 1).$$

At $t = 1$ that is $e$. Past one, the corner of the cube is no longer a simplex — the plane has cut into the far faces — and the volume becomes an alternating sum, one correction per face crossed.

The exact count for every t #

The volume of the set where $n$ uniform draws sum to at most $t$ is a classical formula, the distribution of the Irwin–Hall sum, and adding those volumes over all $n$ collapses to a finite sum with one term for each whole number up to $t$:

$$m(t) = \sum_{k=0}^{\lfloor t \rfloor} \frac{(-1)^k (t-k)^k}{k!}\, e^{t-k}.$$

For $t \le 1$ only the $k = 0$ term survives and gives $e^t$.

Where the alternating signs come from is visible in two dimensions. The chance that two draws sum to at most $t$ is the area of the unit square below the line $x + y = t$. For $t \le 1$ that region is a triangle of area $t^2/2$. For $t$ between one and two the triangle $x + y \le t$ pokes out of the square through two sides, and the parts outside are two small triangles, each a copy of the original corner shifted by one and of area $(t-1)^2/2$; the area inside is $t^2/2 - 2 \cdot (t - 1)^2/2$. In $n$ dimensions the simplex pokes out through $n$ faces, the pieces outside overlap in pairs, the pairs in triples, and inclusion and exclusion gives $\sum_k (-1)^k \binom{n}{k} (t - k)^n / n!$ with one term for every corner the plane has passed. Summing that over $n$, the binomial coefficients and factorials recombine into the exponentials of the formula above.

The formula is not a curiosity of the uniform law; it is what the renewal equation below produces for this law, solved one unit at a time. On each interval between whole numbers the equation is a delay equation — the count at $t$ depends on the count at $t - 1$ — and the term switched on at each whole number is the echo of the corner that the previous unit introduced. At $t = 1.5$ the formula gives $3.6573$; the line says $3.6667$; the echo of the first corner is still loud enough to be read in the second decimal place, and by the time three more corners have passed it is gone. Between one and two the formula is $e^t - (t - 1)e^{t-1}$, and so on, a new term switched on at every whole number.

The simulations sit on the curve, which is the check that the formula is the right one. More striking is how quickly the curve joins the line. At $t = 1$ the count is $e$ and the line says $2.667$: a gap of $0.05$. At $t = 3$ the gap is a ten-thousandth. At $t = 6$ it is under a millionth. For any purpose a computer could tell apart, the average count to pass $t$ is $2t + \tfrac23$ from about $t = 3$ on.

That the slope is two is the law of large numbers in its plainest form: the steps average a half, so in the long run the count grows at two per unit of distance. The intercept needs an argument of a different kind, and the error needs a third. Take them in that order.

The step that crosses is not a typical step #

Where does the two-thirds come from? A clean way in is an identity of Abraham Wald’s. When a sum of independent steps is stopped by a rule that looks only at the steps so far, the expected total at the stop is the expected step times the expected count:

$$E[S_N] = E[X]\; E[N].$$

It is the fair-game principle once more — subtract $E[X]$ from every step and the running total becomes a martingale, which no stopping rule of finite expected length can bias. Here $E[X] = \tfrac12$, and the total at the stop is $t$ plus the overshoot. So

$$E[N] = 2\,(t + E[\text{overshoot}]),$$

and everything turns on how far past the line the last step lands. If that were a quarter on average — a step averaging a half, landing on average halfway along itself — the constant would be a half. It is a third, and the reason is that the last step is not an ordinary step.

A long step is more likely to be the one that straddles the line, in exact proportion to its length: a step of length $0.9$ covers nine times as much of the axis as a step of length $0.1$, so it is nine times as likely to be the one that a fixed point falls inside. The crossing step therefore has density $2x$ — the ordinary density, weighted by length, renormalised — and averages two-thirds rather than a half. The line lands uniformly within that step, so the overshoot is a uniform fraction of a size-biased step, with density $2(1 - y)$ and average one-third. Wald’s identity turns the third into the constant: $2 \times \tfrac13 = \tfrac23$.

This is the effect the wait for HTH uncovered, when a run of tosses begun at a random moment landed in a longer-than-average gap between appearances. There it explained why a wait and a gap differed. Here it is the whole of a constant, and the figure measures the bias directly: the histograms are the step lengths a fixed line actually catches.

The constant is set by the spread #

Nothing in the argument used the uniform distribution except at the last line. Run it for any step law with mean $\mu$ and the size-biased step averages $E[X^2]/\mu$, the overshoot averages $E[X^2]/2\mu$, and Wald’s identity gives

$$E[N(t)] \approx \frac{t}{\mu} + \frac{E[X^2]}{2\mu^2} = \frac{t}{\mu} + \frac{1 + \mathrm{CV}^2}{2},$$

where $\mathrm{CV}$ is the coefficient of variation, the standard deviation of a step divided by its mean. A half from the mean, and half the squared relative spread on top.

The curves were computed without the formula, from the renewal equation — the statement that after the first step $x$ the remaining count is the same problem with $t - x$ in place of $t$:

$$m(t) = 1 + \int_0^t m(t - x)\, f(x)\, dx.$$

Solved numerically, it reproduces the exact uniform curve to six figures, and it gives every other law the same treatment. Each settles on its own constant. The exponential is the extreme case: its steps are memoryless, so the overshoot is again exponential with the full mean, and the count is exactly $1 + 2t$ from $t = 0$ — the constant one, with nothing to settle. The steps of exactly one half are the other extreme. Their count is $\lfloor 2t \rfloor + 1$, and $m(t) - 2t$ is a sawtooth that never settles: a step law confined to a lattice of multiples of some fixed length never forgets where the line falls relative to that lattice. David Blackwell’s renewal theorem of 1948 is precise about this. For any step law not confined to a lattice, the expected number of steps landing in an interval of length $h$, far out, tends to $h/\mu$; for a lattice law it does not, and the averaged constant is all that survives.

The points fall on the line. Gamma laws of shape $k$ have $\mathrm{CV}^2 = 1/k$, and the measured constants run from one (shape 1, the exponential) down towards a half. The uniform law, with $\mathrm{CV}^2 = 1/3$, lands exactly on the gamma law of shape three — two laws with entirely different shapes, the same spread, and so the same constant. The triangular law lands on gamma of shape six. The constant does not see the shape of the step distribution at all; it sees one number, the relative variance. The two-thirds of the uniform case is $\tfrac12(1 + \tfrac13)$.

A line picks its step by length #

The bias the crossing step carries is not special to running totals. It appears whenever a fixed point is used to pick one piece from a row of pieces of random length, and it is worth recognising, because it is the commonest way a careful average comes out wrong.

Buffon’s needle is the oldest instance. A needle dropped on a lined floor crosses a line with a chance proportional to its length, so if needles of mixed lengths are dropped and only the crossers are collected, the collection is biased toward long needles in exactly the proportion drawn above: weighted by length and renormalised. Ask a hospital’s patients on a given day how long their stay will be, and the answers are biased the same way — a long stay is more likely to include the day of the survey. Ask passengers at a stop how long the gap between buses was, and the gap they landed in is, on average, $E[G^2]/E[G]$ rather than $E[G]$. The running total is the cleanest of these because the line is the “day of the survey” and the steps are the “stays”, and every quantity can be computed exactly.

The general form of the constant also explains why the bias is invisible when the pieces are all alike and largest when they vary most. With every step the same length, choosing by length changes nothing. With steps that are usually short and occasionally long, the line almost always lands in a long one, and the average crossing step can be many times the average step. The relative variance, $\mathrm{CV}^2$, is exactly the measure of that, which is why it is the only feature of the distribution that survives into the constant — the same single number that, knowing only a mean and a spread, bounds how far a quantity can stray. A mean and a variance were enough there to bound a tail; here they are enough to fix a constant exactly, and nothing about the shape of the steps adds to it.

There is a practical moral, and it is the same as the one the coin patterns taught: when an average is taken over things that were found rather than things that were listed, ask how the finding weighted them. A list of all steps averages a half. The steps a line finds average two-thirds. Both numbers are right, and they answer different questions.

How fast the line is reached #

The curve joins the line fast, and the speed has a formula with a surprising ingredient.

On a logarithmic scale the gap is a falling line scalloped by dips, and each dip is a moment where the curve crosses the line and the gap is momentarily nought. Both features have the same source. Transform the renewal equation — multiply by $e^{-st}$ and integrate — and it becomes algebra: the transform of $m$ has a denominator $1 - \phi(s)$, where $\phi(s) = (1 - e^{-s})/s$ is the corresponding transform of a single uniform step. Where the denominator vanishes, the transform has a pole, and each pole contributes a term $e^{st}$ to $m(t)$.

The pole at $s = 0$, a double one, produces the line $2t + \tfrac23$ — that is another derivation of both the slope and the constant. Every other pole is a complex root of $1 - e^{-s} = s$, and the one nearest the imaginary axis is

$$s = -2.0888 + 7.4615\,i.$$

Its real part is the decay rate: $e^{-2.0888} \approx 0.124$, a factor of eight per unit of $t$. Its imaginary part is the ripple: a period of $2\pi/7.4615 = 0.842$, so the gap changes sign every $0.421$ — exactly the spacing of the dips. The constant $e$ at $t = 1$ and the eightfold decay are two faces of the same transform. A count of uniform steps is as tame as a sum can be, and still the way it settles is governed by a complex number nobody would guess.

A grid fine enough for six figures, and a spread left undescribed #

The figures compute averages; they say nothing about the spread of the count itself, which is the next question and has its own constants. The variance of the count grows like $\sigma^2 t/\mu^3$, and its constant term depends on the third moment of the step, so the spread of the count needs more than the relative variance to describe it.

The renewal-equation curves are numerical: the grid has spacing a four-hundredth, and agreement with the exact uniform formula to six figures is the evidence that the grid is fine enough. The constants in the last two figures are read off at $t = 5$ and $t = 6$, where the exact uniform curve is within a millionth of its limit; for the gamma laws the approach is also exponentially fast, but at rates from their own transforms, which the figures do not compute. And the identification of the decay rate with the complex root is a statement about all $t$ — the figure shows the dips spaced at $0.421$ out to $t = 9$, where the gap has fallen to ten parts in a billion and floating-point rounding begins to compete with it.

Still open: the structure of a race #

The renewal picture explains a constant that recurs throughout the waits in this collection. The appearances of a coin pattern form a renewal process; the gaps between them average $2^k$ for a pattern of length $k$, and the first wait exceeds a gap by a correction that comes from the pattern’s overlaps with itself — which is why HTH takes ten tosses and HTT eight, and why the essay on those two waits could read the difference as the same bias toward long gaps that produces the two-thirds here.

What the renewal picture does not supply is an account of races. When several patterns compete, the gamblers’ accounting gives each one’s chance of finishing first, one equation per pattern, and no simple rule relates the outcome of a three-way race to the two-way results. Whether all sixteen patterns of length four, raced at once, finish in an order that can be read off their overlap structure without solving the system is a question that has been asked here and not answered. Renewal theory knows each pattern’s gaps exactly; what it does not know is how the processes interfere when the first arrival of any one of them ends them all.

Two-thirds, read correctly #

The answer to “how many draws to pass $t$” is three numbers. The slope is two, because the steps average a half. The constant is two-thirds, because the step that crosses the line is chosen by its length and so averages two-thirds rather than a half, leaving a third behind. And the error falls by eight per unit and swings every $0.421$, because the transform of a uniform step has a complex root at $-2.0888 + 7.4615i$.

Only the first of those would survive a careless argument. The second is the inspection paradox doing quantitative work — and the general form, half of one plus the relative variance, says the constant is a measurement of how unequal the steps are. Make them all alike and it falls to a half; make them memoryless and it rises to one; the uniform steps sit between, at two-thirds, for exactly the reason a long step is more likely than a short one to be the step a line falls in.