Half the time is the rarest answer

Two players toss a fair coin forty times, one keeping a running tally of the lead. At the end, one question: for how many of those forty tosses was the first player ahead?

The intuitive answer is about twenty, with some spread. The intuitive answer is not merely imprecise; it names the least likely outcome in the whole distribution.

The shape is a U. Spending the entire game ahead, or the entire game behind, is more likely than any other single outcome; being level at the halfway mark is rarer than being ahead throughout.

The distribution, exactly #

For a walk of $2n$ steps, the probability that exactly $2k$ of them are spent above the axis is

$$\Pr[\text{time above} = 2k] = \binom{2k}{k}\binom{2n-2k}{n-k}2^{-2n}.$$

Three things about that formula are worth noticing before anything else.

It is a product of two central binomial coefficients, one for each side of the split — which is the tell that the two halves of the walk are behaving independently, and that each half is doing something at its own extreme.

It is symmetric in $k$ and $n-k$, as it must be, since relabelling the players exchanges the two.

And it is largest at $k=0$ and $k=n$, because the central binomial coefficient $\binom{2m}{m}4^{-m}$ decreases with $m$, so the product of two of them is largest when the split is as uneven as possible. The U-shape is not an accident of small numbers; it is the formula’s shape at every size.

The name comes from the limit. As the walk gets long, the fraction of time spent above the axis has the distribution with density $1/(\pi\sqrt{x(1-x)})$ on $[0,1]$, whose cumulative function is $\tfrac{2}{\pi}\arcsin\sqrt{x}$ — the arcsine law, proved by Paul Lévy in 1939.

Why it is not a bell #

Nearly every distribution met in this collection gets more concentrated as the sample grows. Coin flips pile into a bell, averages settle down, and the whole apparatus of the central limit theorem says that adding many independent small things produces a shape that narrows.

The time spent above the axis is a sum of many small things too — one indicator per step — so the natural expectation is a bell.

The reason the bell does not arrive is that the indicators are not independent, and their dependence does not weaken with distance. If a walk is above the axis at step $1{,}000$, it is overwhelmingly likely to be above it at step $1{,}001$, and quite likely still to be above it at step $2{,}000$ — because to be below it, the walk must return to zero, and returns become rare as the walk drifts. The walk’s excursions away from the axis get longer and longer, in proportion to the time elapsed, so the last excursion typically occupies a constant fraction of the whole game.

That is the mechanism in one sentence: a fair walk’s visits to zero become sparse, so the final excursion is long, so one side tends to hold the lead for a long stretch that scales with the length of the game.

Once that is seen, the U is the natural shape and the bell would be the strange one. There is nothing pulling the walk back toward zero — a fair walk has no restoring force — so no mechanism exists to keep the lead changing hands.

Where the two binomial coefficients come from #

The formula splits the walk at its last visit to zero, and each factor counts one of the two pieces.

Suppose the last visit to the axis happens at step $2k$. Before it, the walk is an unconstrained walk of $2k$ steps that happens to end at zero; the number of those, as a fraction of all walks of that length, is $\binom{2k}{k}2^{-2k}$. After it, the walk never touches zero again, and the chance of a walk of $2n-2k$ steps staying strictly on one side is — by the reflection principle — exactly the same quantity $\binom{2n-2k}{n-k}2^{-(2n-2k)}$.

Two central binomial coefficients, one from a walk that returns and one from a walk that does not: the same expression appearing twice for two different reasons, which is the coincidence that gives the distribution its symmetry. It is also the reason the shape is U-rather-than-bell in one line — $\binom{2m}{m}4^{-m}$ falls with $m$, so the product of the pair is biggest when one of them is as small as possible, meaning $k = 0$ or $k = n$.

What it says about fairness #

The consequences for how a fair game looks are worth stating plainly, because the mistaken intuition here is common and has costs.

In a fair game of any length, one side is usually ahead for most of it. The lead changes hands rarely — the expected number of changes in $n$ steps grows like $\sqrt{n}$, not like $n$ — so a game of ten thousand rounds has on the order of eighty lead changes and not five thousand.

The last time the score is level is typically very early or very late, with the same U-shaped distribution. That is the same arcsine law again, applied to a different quantity, and it means the phrase neck and neck all the way describes an unusual game rather than a typical one.

And a player who has been behind for the whole of a long fair game has no evidence of unfairness whatever. The observation one side led for 95% of the rounds is, in a fair game of a thousand rounds, about as likely as any other single observation and more likely than the lead was even.

The applied version of this is the reason performance records are so easy to over-read. A fund manager, a football team or a sales region tracked against a fair benchmark will show long runs of leading and long runs of trailing, with a distribution of run lengths that has no characteristic scale — and every one of those runs will attract an explanation.

The last time the score was level #

The same distribution answers a second question, and this one is the more startling of the two.

When was the score last level? For a game of $2n$ rounds, the answer has exactly the arcsine distribution again, and it is U-shaped for exactly the reason the curve above flattens: the walk’s excursions grow, so the final one is typically a large fraction of the game.

In a game of ten thousand rounds, the chance that the last tie occurred in the first five hundred rounds is about $14\%$; so is the chance it occurred in the last five hundred. The chance it occurred in the middle five hundred is under $4\%$. A fair game is far more likely to have been settled early — in the sense of never being level again — than to have been contested throughout.

The expected number of lead changes tells the same story from another angle. It grows like $\sqrt{2n/\pi}$, so a hundred-round game has about eight and a ten-thousand-round game about eighty. Lead changes become rarer per round as the game goes on, at exactly the rate that keeps their total growing like a square root — the same square root that governs everything else about a walk.

Where the small cases lie #

The distribution at two steps is $\tfrac12, 0, \tfrac12$: the walk is above the axis for both steps or below for both, and never one of each. At four steps it is $\tfrac38, \tfrac14, \tfrac38$. The U is present from the start, and at these sizes it looks like a curiosity of tiny numbers rather than a law.

That is the trap this essay is tagged for. A reader who checks the claim at $n = 2$ sees an artefact of parity, concludes the effect is a small-number oddity, and expects it to wash out. It does the opposite: the ratio between the end bars and the middle bar grows without limit as the walk lengthens. At forty steps the ends are about twice the middle; at four hundred they are about six times; the ratio grows like $\sqrt{n}$.

Small cases lie in the other direction too. At small $n$ the middle bar is a substantial fraction of the total, so an even split is uncommon rather than negligible; in the limit the density at $x = \tfrac12$ is $2/\pi \approx 0.64$ against $\infty$ at the ends, and the probability of a split within a percent of even goes to zero.

Who found it, and what it was for #

Paul Lévy proved the arcsine law in 1939, as part of building the theory of Brownian motion, and the discrete statement above is the shadow it casts on coin tossing.

What made it famous is Feller’s textbook. In the 1950 first volume of An Introduction to Probability Theory and Its Applications, Feller devoted a section to it under a heading about the unreliability of intuition, worked the numbers for a game of a year’s daily tosses, where the arcsine law gives about one game in fifteen in which one player leads on more than $364$ of the $365$ days, and more than one game in four in which one leads on more than $347$ of them. He presented it not as a curiosity but as a correction — the standard mental model of a fair game, in which the lead oscillates and the fraction of time ahead concentrates on a half, is wrong in a way that no amount of thinking about single tosses will reveal.

The correction had teeth. Sequences of wins and losses are the raw material of a great deal of applied statistics, and a mistaken sense of what randomness looks like generates false structure everywhere it is applied — in the reading of sports records, in the evaluation of fund managers, in the detection of streaks, and in the folk belief that a run must end soon.

It is also, unusually, a case where the mathematics is easier than the intuition it corrects. The formula is two binomial coefficients and the proof is a fold; the misconception is deep-seated and survives being told the answer.

Where the law needs a condition #

The arcsine law is a statement about a walk with no drift and finite step variance, and both conditions choose the shape.

Give the walk the slightest drift and the U collapses at long times. A walk that gains a hundredth of a step on average per round will, after a few hundred thousand rounds, be above the axis essentially always, and the fraction of time above concentrates at one rather than spreading between the extremes. The U-shape is not a fact about unfair games looking fair; it is specifically the signature of exact fairness, and the distribution is a fingerprint that any drift smudges.

That cuts both ways as a diagnostic. Because the arcsine shape is fragile, an observed distribution of time-ahead that is U-shaped across many games is evidence of fairness rather than of anything else — and a distribution that piles up at one end is evidence of drift, which is what a test of skill against luck really wants to know.

Heavy-tailed steps change the answer too. A walk whose individual steps have infinite variance has its own arcsine-type law with a different exponent, because the balance between how far a walk travels and how often it returns is what sets the shape, and both quantities depend on the step distribution. The half-and-half symmetry of the fair coin gives the classical $1/(\pi\sqrt{x(1-x)})$; other step laws give a family of generalisations with the same U character and different curvature at the ends.

What the picture cannot show #

Every bar in these figures is an exact probability, computed over all $2^n$ walks, so nothing here is a sample and nothing is subject to simulation noise. That is a strength, and it hides the thing a reader most wants to see: what an individual game looks like.

The distribution says a long lead is likely. It does not show a lead being held, and the sixth figure — six actual walks — is the only one in the essay that shows the phenomenon happening rather than its statistics. Six is not many, and a reader is entitled to suspect the seed was chosen. It was not chosen for the outcome; it is stated in the figure’s own parameters, and any other seed produces the same impression, which is a claim the reader can check only by taking the generator’s word or running it.

The other thing no picture shows is the limit. Every figure here is at a finite length, and the arcsine density is the shape at infinity, where the U’s arms go to infinite height while remaining integrable. There is no drawing of that: at every finite $n$ the end bars are finite, and the limiting object is not the limit of the pictures in any sense the eye can supply.

The ladder from here #

Below: the walk itself and the reflection principle, which is where the two binomial coefficients in the formula come from. Above: the game with a barrier at each end, where the walk is stopped and the questions change completely.

Sideways: the same $\sqrt{n}$ that sets the scale of a walk’s spread sets the number of lead changes; the sparsity of returns is the recurrence result read as a statement about waiting times; and the failure of the bell here is a useful counterweight to the central limit theorem’s usual reach, since the two apply to different functions of the same walk.

Averaging is not always what happens #

The lasting point is a caution about a habit this collection otherwise encourages.

The central limit theorem is so reliable that a bell becomes the default expectation for anything built out of many small independent contributions. The time a walk spends on one side is built out of many small contributions, and they are not independent, and the result is the opposite shape — most of the mass at the extremes, the least at the middle.

The tell, in general, is long-range dependence: contributions that stay correlated over stretches which grow with the size of the problem. Where that holds, sums do not concentrate, averages do not settle, and the intuition trained on bell curves points exactly backwards. It is the same reason a system with memory of its whole past behaves unlike one that forgets, and the reason a run of luck is a worse guide to fairness than almost anyone expects.