The path folded at its first touch

A walk starts at $2$, takes twelve steps of one place each, and ends at $4$. How many such walks touch zero along the way?

Asked directly, this is a question about every step of a path’s history, and there are $\binom{12}{7} = 792$ paths to sift. Asked after one trick, it is a question about where paths end, and the answer is a number already on Pascal’s triangle.

The trick is to fold. Take any path from $2$ to $4$ that touches zero, find the first moment it touches, and reflect everything before that moment in the axis. What comes out is a path from $-2$ to $4$, because the start has been mirrored and the endpoint has not moved.

Why folding is a bijection #

Three things have to hold, and each is easy.

The fold produces a legal path. Reflecting a sequence of $\pm 1$ steps gives a sequence of $\mp 1$ steps, which is still a walk, and the join at the folding point is continuous because the path is at zero there and zero is its own mirror image.

Every path from $-2$ to $4$ arises this way. Such a path starts below the axis and ends above it, so it must cross — and a path of unit steps cannot jump over zero, so it touches. Fold it at its first touch and a path from $2$ to $4$ touching zero comes back.

The correspondence is one to one. Folding twice restores the original, because the first touch is at the same place in both — the fold does not move the moment of first touching, only the side the path was on before it.

So the touching paths and the paths from the mirror image are in exact correspondence, and counting either counts both:

$$\#\{\text{paths } 2 \to 4 \text{ touching } 0\} = \#\{\text{paths } -2 \to 4\} = \binom{12}{9} = 220.$$

That is the reflection principle, and its value is the conversion it performs: a constraint on a path’s history has become a constraint on its endpoint, and endpoints are what binomial coefficients count.

Every count printed under these figures is obtained by enumeration rather than by the formula: the generator builds all $2^n$ paths, classifies each one, and then checks the binomial coefficient against the result. A formula that has been compared with sixteen thousand paths is a formula that has been tested.

The ballot problem #

The oldest application is a question about counting votes, posed by Joseph Bertrand in 1887.

Two candidates receive $a$ and $b$ votes with $a > b$. The ballots are counted one at a time in a random order. What is the chance that the leader is ahead at every single moment of the count — never level, never behind?

$$\frac{a-b}{a+b}.$$

The answer is startling for how little it depends on. Not on the total, not on the margin’s size in absolute terms, only on the ratio. A candidate winning 501 to 499 leads throughout with probability $1/500$; a candidate winning 3 to 1 does so with probability $1/2$.

The reflection principle gives it in two lines. A count is a walk starting at zero, going up for each vote for the leader and down for the other, ending at $a - b$. The walks that fail the condition are those returning to zero after the first step. If the first vote is for the loser, the walk is below zero and must come back through it, so it fails. If the first vote is for the winner, the failing walks are those that later touch zero — and folding matches them exactly with the walks whose first vote was for the loser. So the failures are twice the number of walks beginning with a vote for the loser, which is $2b/(a+b)$ of all of them, and what is left is $(a-b)/(a+b)$.

The pleasure of the argument is that the folding is doing all the work and the arithmetic is doing none.

What it is really counting: Pascal’s triangle #

The reason the trick pays is that the unconstrained count is trivial. A walk of $n$ steps ending at a given place is a choice of which steps go up, so the count is a binomial coefficient, and the whole table of them is on the triangle above. Any question that can be converted into “how many paths end here” is answered by reading an entry.

The reflection principle converts a large family of such questions. The number of paths staying strictly positive, the number reaching a level before returning to zero, the number of first returns at time $2n$, the joint distribution of a walk’s maximum and its endpoint — all of them fold into differences of two binomial coefficients.

The maximum, for free #

Here is the conversion doing something a direct approach finds hard.

How high does a walk get? The event the walk reaches level $m$ at some point, and ends at $x$ is a statement about a maximum, which is a function of the entire path. Folding at the first visit to $m$ turns it into the walk ends at $2m - x$, which is one binomial coefficient.

So the distribution of the running maximum is available immediately:

$$\Pr[\max \ge m] = \Pr[S_n \ge m] + \Pr[S_n > m],$$

the two terms being the paths that end above the level and the paths that reach it and come back. In the limit this is the statement that the maximum of a walk has the same distribution as the absolute value of its endpoint — a fact that is nearly unbelievable stated on its own and is a one-line consequence of the fold.

That has a practical edge. A quantity of interest in almost every application of walks — the largest loss a strategy suffers, the deepest a queue gets, the furthest a diffusing particle strays — is a maximum, and maxima are hard. The reflection principle is the reason so many of them have clean answers.

Whose principle it is #

Bertrand posed the ballot problem in 1887 and gave an answer by a recurrence, remarking that the simplicity of the result suggested a better argument existed. Désiré André supplied one within weeks, in the same journal, and the reflection principle has been attributed to him ever since.

The attribution is wrong in an interesting way. André’s argument does not reflect anything: it sets up a correspondence between the bad sequences beginning with a vote for one candidate and those beginning with a vote for the other, by swapping the votes up to the first tie rather than reflecting a path. The two arguments produce the same count, and the swapping one has the advantage of not needing paths at all. Marc Renault traced the actual history in 2008 and found the reflection version appearing in print decades later, in work on Brownian motion, where paths are the natural language.

This kind of retrospective tidying is common enough to be worth expecting. An argument gets restated in the vocabulary of a later subject, the restatement becomes the standard form, and the name stays attached to the person who solved the problem rather than to the person who found the picture. Nothing dishonest happens at any step.

The deeper reason the reflection form won is that it generalises where the swap does not. The swap is about sequences of votes; the reflection is about paths and levels, and once phrased that way it applies to a walk with any starting point, to a level anywhere, to the maximum, and to Brownian motion. The picture was the more portable object.

Where it fails #

The principle needs the walk to be symmetric and to move in unit steps, and both conditions are load-bearing.

Symmetry is what makes the reflected path as likely as the original. In a biased walk the fold still produces a valid path, and the correspondence is still one to one — but the two paths have different probabilities, since reflecting a stretch swaps its ups and downs and therefore changes its weight. The count is still right; the probability is not. The repair is to attach a factor for the swapped steps, which is doable and turns a clean argument into an exercise in bookkeeping.

Unit steps are what make cannot cross without touching true. A walk that jumps two places at a time can pass from $1$ to $-1$ without ever visiting zero, and then the set of paths that “cross” and the set that “touch” are different sets, and the fold at the first touch has nothing to fold at. Every version of the principle for continuous or jump processes has to deal with this, and the continuous case is easier than the jumping one: Brownian motion has continuous paths, so it cannot skip a level, and the reflection principle survives intact.

That is worth registering as an unusual direction of difficulty. The idealised limit is better behaved than the discrete models between, because it recovers the property — no skipping — that the unit-step walk had and a jumping walk lost.

First returns, and a sum that has no average #

Fold the principle once more and it produces the distribution of the time a walk takes to come back to where it started.

The chance that a fair walk has not returned to zero by step $2n$ works out at $\binom{2n}{n}2^{-2n}$, which is the chance that it is at zero at step $2n$ — a coincidence with no obvious reason, and a consequence of the same fold. That quantity falls like $1/\sqrt{\pi n}$, slowly.

Slowly enough to matter. The sum of those probabilities diverges, so return is certain — which is the recurrence result of the first rung — while the average waiting time is the sum of $n$ times a term falling like $n^{-3/2}$, and that sum diverges too. So a walk on a line returns with probability one and takes infinitely long to do it on average.

Both statements are true and they are not in tension, which is the standard first shock of the subject. Certainty of an event says nothing about the expected time to it, and the gap between the two is exactly the room a heavy tail lives in: almost every walk comes back quickly, a few take enormously long, and the few are heavy enough to carry the average away by themselves.

What it costs #

The argument gives exact answers and gives them in a form that is hard to use twice.

Every folding is bespoke. A different constraint — two barriers rather than one, a level that moves, a walk that must stay positive and end high — needs its own fold, and with two barriers the fold has to be applied repeatedly, producing an infinite alternating sum of binomial coefficients rather than a difference of two. The gambler’s ruin problem is exactly that case, and its clean answer comes from a recurrence instead, because the reflection series is correct and unusable.

So the principle is a sharp tool with a narrow blade. Where it applies it is unimprovable, and it does not generalise gently.

One more limitation is worth being explicit about, because it is where the tool stops being exact and starts being an approximation. Everything above is a statement about walks of unit steps on the integers. Real processes — a share price, a queue, a diffusing molecule — take steps of varying size, and the counts become integrals that have no binomial coefficients in them. What survives is the shape of the answer rather than the answer: the maximum still has the distribution of an absolute endpoint, first-passage times still have a $n^{-3/2}$ tail, and the constants change. The fold is exact for the model and indicative for the thing modelled, and it is worth knowing which of those is being relied on.

What the picture cannot show #

The figure shows one folded path. The argument is about a correspondence between two sets of paths — several hundred in the drawn case, and $2^{200}$ in the last figure — and no drawing shows a bijection. It shows one pair of partners and asks the reader to believe the pairing is exhaustive.

That belief is exactly the thing the checked counts are for. The generator enumerates every path of the drawn length, counts the touching ones and the mirrored ones, and refuses to draw if the two numbers differ. So what the reader gets is a picture of one instance and a guarantee about all of them — which is an honest division of labour, and worth stating rather than letting the picture imply more than it carries.

The other invisible thing is the first in first touch. Folding at the second touch, or at the last, does not give a bijection: several different paths fold to the same image and the count collapses. Nothing in the figure marks why the first is the right choice, and the whole argument fails without it.

The ladder from here #

Below: where a walk gets to, and whether it comes home. Above: the arcsine law, which is what folding says about the time a walk spends on one side, and gambler’s ruin, where a second barrier turns the fold into a series and a recurrence takes over.

Sideways: the same fold counts the ways of cutting a polygon, since the Catalan numbers are the paths that never go below zero and the reflection principle is the standard proof of their formula; and it is the argument behind the ballot-style counting in Pascal’s triangle.

Turning a history into an endpoint #

The habit worth taking is the conversion itself.

The hard quantity was a property of a path’s whole history: did it ever touch zero. The easy quantity was a property of one moment: where did it end. The fold exchanges one for the other at no cost, and the reason it can is that the constraint and the reflection interact — the level being touched is the level being reflected in, so the fold leaves the constraint invariant and moves everything else.

Look for that shape whenever a count over histories seems hard: a symmetry of the space of paths that fixes the constrained ones and moves the rest. It is the same move as a proof by pairing up the objects that should cancel, and the same move as an involution that fixes exactly the objects being counted. In each case nothing is calculated. Two sets are put into correspondence, and one of them was already understood.