Two players, A and B, toss a fair coin $2n$ times. Each head is a point for A and each tail a point for B, so A’s lead after $k$ tosses, A’s points minus B’s, is

a simple random walk started at $0$.

For what fraction of the game is A ahead?

The players are interchangeable, so the answer is symmetric about one half, and the natural guess is that it also concentrates there: in a fair game the lead should change hands regularly, and each player should be ahead about half the time. The exact distribution does not concentrate there. The fraction of the game spent in the lead is most likely to be near $0$ or near $1$, and one half is its least likely value. In the limit of a long game:

• With probability $1/2$, one of the two players is ahead for more than 85.4% of the game.
• With probability $1/5$, one of the two players is ahead for more than 97.6% of the game.
• The probability that the lead is shared anywhere between 45% and 55% is 6.4%.

The limiting density of the fraction is $1/(\pi\sqrt{x(1-x)})$, a U shape with integrable singularities at both ends, and the corresponding distribution function is $\frac{2}{\pi}\arcsin\sqrt{x}$: this is the arcsine law. The derivation needs one identity about paths, a product formula that follows from it, and Stirling’s approximation.

Ties are rare

The score is tied at time $2m$ with probability

the asymptotic form coming from Stirling’s formula; ties at odd times are impossible. The decay is slow: after a million tosses the chance of an exact tie at that moment is still $0.08\%$. Summing over the even times gives the expected number of ties in $2n$ tosses,

where the closed form follows by induction from $u_{2m} = u_{2m+2}\cdot\frac{2m+2}{2m+1}$. A game of 10,000 tosses has about 79 ties on average. The lead can change hands only at a tie, so it changes at most a few dozen times in ten thousand tosses. The U shape also needs the stretches between ties to be heavy-tailed, which the next section quantifies.

Reflection principle

Lemma. The probability that the score is never tied during $2n$ tosses equals the probability that it is tied at the end:

The two signs are symmetric, so it suffices to show $\mathbb{P}(S_1 > 0, \ldots, S_{2n} > 0) = \tfrac12 u_{2n}$, which is a count of paths. Write $N_{m,y} = \binom{m}{(m+y)/2}$ for the number of paths of $m$ steps from $0$ to $y$. A path that stays positive begins with an up-step to $(1, 1)$ and then runs from $(1,1)$ to $(2n, y)$ for some even $y > 0$ without touching the axis. Among all $N_{2n-1,\,y-1}$ paths from $(1,1)$ to $(2n,y)$, the ones that do touch the axis are in bijection with the paths from $(1,-1)$ to $(2n,y)$: reflect the initial segment, up to the first visit to $0$, in the axis.

So the number of paths from $(1,1)$ to $(2n,y)$ that avoid the axis is $N_{2n-1,\,y-1} - N_{2n-1,\,y+1}$. Summing over $y = 2, 4, \ldots, 2n$ telescopes to $N_{2n-1,\,1} = \binom{2n-1}{n} = \tfrac12\binom{2n}{n}$, and dividing by the $2^{2n}$ equally likely paths gives $\tfrac12 u_{2n}$.

The same count gives a second form that is needed below: $\mathbb{P}(S_1 \ge 0, \ldots, S_{2n} \ge 0) = u_{2n}$. Deleting the first step of a strictly positive path of $2n$ steps and shifting it down by one gives a non-negative path of $2n-1$ steps, and this is a bijection, so $\mathbb{P}(S_1 \ge 0, \ldots, S_{2n-1} \ge 0) = 2 \cdot \tfrac12 u_{2n}$; and since $S_{2n-1}$ is odd, $S_{2n-1} \ge 0$ forces $S_{2n-1} \ge 1$, hence $S_{2n} \ge 0$ automatically.

The lemma also describes the stretches between ties. The probability that the first tie occurs at time $2r$ is $f_{2r} = u_{2r-2} - u_{2r} = u_{2r}/(2r-1) \sim r^{-3/2}/(2\sqrt{\pi})$, and the probability that a stretch lasts longer than $2m$ tosses is $u_{2m}$ itself, of order $m^{-1/2}$. A tail this heavy has infinite mean, and in a game of $2n$ tosses the longest stretch occupies a positive fraction of the whole game. Whoever is ahead during that stretch is ahead for a large part of the game.

The last tie

Let $L$ be the time of the last tie, with $L = 0$ if the score is never tied. For $L = 2k$ the walk must be at zero at time $2k$ and then avoid zero for the remaining $2n - 2k$ steps; the steps after time $2k$ form a fresh walk, so by the lemma

This is the discrete arcsine law. Two features follow directly. The formula is symmetric under $k \leftrightarrow n - k$: the last tie is as likely to fall at time $2k$ as at time $2n - 2k$, so a last tie inside the first tenth of the game and a last tie inside the final tenth are equally probable. And since $u_{2m}$ decreases in $m$, the two ends $k = 0$ and $k = n$ are the most probable values, each with probability $u_{2n}$, while the middle is the least probable: for even $n$, $\mathbb{P}(L = n) = u_n^2 \approx 2/(\pi n)$, below the endpoint value by a factor of $\sqrt{\pi n}/2$. The 20-toss game, to four decimals, with only the first half listed since the second half mirrors it:

Inserting $u_{2m} \approx 1/\sqrt{\pi m}$ and writing $x = k/n$,

so the fraction $L/2n$ of the game elapsed before the last tie has, in the limit, the density $1/(\pi\sqrt{x(1-x)})$. The substitution $x = \sin^2\theta$ integrates it:

The limiting density is the beta distribution with both parameters equal to $\tfrac12$.

Time in the lead has the same distribution

Call the interval between tosses $k-1$ and $k$ an interval where A is ahead if $S_{k-1} > 0$ or $S_k > 0$. A tie is credited to the player who was ahead just before or just after it, so all the intervals between two consecutive ties go to one player, and A’s count is always even. Theorem. The number of intervals where A is ahead equals $2k$ with probability $u_{2k}\,u_{2n-2k}$, for $k = 0, \ldots, n$: exactly the distribution of the last tie.

The derivation conditions on the first tie. Write $p_{2k,2n}$ for the probability in question. The two boundary cases are the lemma in its second form: $p_{2n,2n} = \mathbb{P}(S_1 \ge 0, \ldots, S_{2n} \ge 0) = u_{2n}$, and $p_{0,2n} = u_{2n}$ by symmetry. For $1 \le k \le n-1$ the score must be tied at some time $2r \le 2n$. If the first tie comes at $2r$ and the stretch before it was A’s (probability $\tfrac12 f_{2r}$), that stretch contributes $2r$ intervals to A and the remaining $2n - 2r$ tosses must contribute $2k - 2r$; if the stretch was B’s, the remaining tosses must contribute all $2k$:

Induction on $n$ turns the probabilities on the right into $u_{2k-2r}\,u_{2n-2k}$ and $u_{2k}\,u_{2n-2k-2r}$, and the renewal identity $u_{2m} = \sum_{r=1}^{m} f_{2r}\,u_{2m-2r}$ (a tie at time $2m$ has a first tie at some time $2r \le 2m$) collapses both sums, leaving $\tfrac12 u_{2k}u_{2n-2k} + \tfrac12 u_{2k}u_{2n-2k}$.

Restrict attention to the games that end tied. Chung and Feller proved in 1949 that among the $\binom{2n}{n}$ paths with $S_{2n} = 0$, exactly $\frac{1}{n+1}\binom{2n}{n}$ of them, a Catalan number, have A ahead for $2k$ intervals, and this holds for every $k$ from $0$ to $n$. Conditioned on a tie at the end, the time in the lead is uniformly distributed. The U shape therefore comes from the games that end with someone ahead, and within those games the distribution of the time in the lead is more concentrated at the two ends than the unconditional one.

The widget draws a random game on the left, with A’s intervals in blue and B’s in red. On the right is the exact distribution $u_{2k}u_{2n-2k}$ of A’s number of intervals, computed from the recursion $u_{2m} = u_{2m-2}\cdot\frac{2m-1}{2m}$ rather than sampled, with the arcsine density overlaid. Ticking the box conditions both panels on a tie at the end and replaces the U with the flat Chung–Feller law.

Quantiles of the limit

The event that the player who spends longer in the lead does so for at least a fraction $q > \tfrac12$ of the game has limiting probability $\frac{4}{\pi}\arcsin\sqrt{1-q}$:

Setting the probability to $\tfrac12$ and to $\tfrac15$ and solving for $q$ gives $85.4\%$ and $97.6\%$, the two figures quoted at the start. A trading strategy that stays above its benchmark for 90% of a year, or a team that leads for 90% of a match, is showing an event that a fair coin produces one time in five ($\frac{2}{\pi}\arcsin\sqrt{0.1} = 0.205$ for a specified side). Time spent in the lead is weak evidence of an edge, and the margin at the end is the quantity that carries the information.

The law is not specific to coin tossing. Lévy (1939) proved the arcsine law for Brownian motion, where it holds exactly at every time horizon; for Brownian motion the same law describes the fraction of time spent positive, the last zero, and the location of the maximum. Erdős and Kac (1947) showed that the fraction of positive partial sums has the same arcsine limit for independent steps with mean zero and finite variance whenever the central limit theorem applies to them, in particular for all i.i.d. steps with finite variance, an early instance of the invariance principle (a limit law that depends on the step distribution only through its mean and variance, because the rescaled walk converges to Brownian motion). Sparre Andersen (1953, 1954) found the exact finite-$n$ version: for i.i.d. steps with any symmetric continuous distribution, the number of positive partial sums among $S_1, \ldots, S_n$ equals $k$ with probability $u_{2k}\,u_{2n-2k}$ for every $n$, the same numbers as in the coin-tossing case, and the argument is purely combinatorial. The U shape is a property of sums of independent symmetric steps, not of $\pm 1$ steps in particular.

References

• William Feller. An Introduction to Probability Theory and Its Applications, Volume I. 3rd edition, Wiley, 1968. Chapter III: the reflection principle, the last tie, and the time-in-the-lead theorem, with the derivation followed above.
• Paul Lévy. Sur certains processus stochastiques homogènes. Compositio Mathematica, 7:283–339, 1939. The arcsine laws for Brownian motion.
• Paul Erdős, Mark Kac. On the number of positive sums of independent random variables. Bulletin of the American Mathematical Society, 53(10):1011–1020, 1947. The arcsine limit for general steps with finite variance.
• Kai Lai Chung, William Feller. On fluctuations in coin-tossing. Proceedings of the National Academy of Sciences, 35(10):605–608, 1949. The uniform distribution of the time in the lead among paths that end tied.
• Erik Sparre Andersen. On the fluctuations of sums of random variables. Mathematica Scandinavica, 1:263–285, 1953, and part II, 2:194–222, 1954. The distribution-free finite-$n$ law for symmetric continuous steps.
• William Feller. An Introduction to Probability Theory and Its Applications, Volume II. 2nd edition, Wiley, 1971. Chapter XII: the combinatorial lemma and the arcsine laws for general random walks, including Sparre Andersen’s theorem.