The Distribution of the Running Maximum

From a Path Maximum to an Endpoint

A walk can reach a high level and later finish well below it. Consequently, the endpoint alone does not reveal whether the path crossed a given barrier. For a simple symmetric walk, however, a reflection of the part of the path after its first visit to the barrier gives an exact way to count the paths that crossed it. This converts a maximum probability into two endpoint probabilities.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space carrying independent increments $\xi_1,\xi_2,\ldots$, each equal to $1$ or $-1$ with probability $\tfrac12$. Define the discrete-time process on the countable state space $S=\mathbb{Z}$ by $S_0=0$ and $S_k=\sum_{\ell=1}^k\xi_\ell$ for $k\ge1$. Its natural filtration is $\mathcal{F}_k=\sigma(\xi_1,\ldots,\xi_k)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. For an integer $n\ge0$, its running maximum is $M_n=\max(0,S_1,\ldots,S_n)$, where $M_0=0$.

Theorem (Running-maximum tail): For every integer $n\ge0$ and positive integer $a$, $$ \mathbb{P}(M_n\ge a)=\mathbb{P}(S_n\ge a)+\mathbb{P}(S_n\ge a+1). $$ For an integer threshold $a\le0$, $\mathbb{P}(M_n\ge a)=1$. The displayed identity is stated for positive $a$.

The two terms have a path-counting interpretation. Every path ending at or above $a$ must have visited $a$, since the walk starts at $0<a$ and moves by steps of size one. Among the paths that visit $a$ but end below it, reflection after the first visit to $a$ pairs them with paths ending strictly above $a$. The strict inequality matters: since endpoints are integers, “strictly above $a$” means at least $a+1$.

Proof. Fix $n\ge0$ and a positive integer $a$. Let $A$ be the set of length-$n$ paths that visit $a$ by time $n$ and end below $a$, and let $B$ be the set of length-$n$ paths that end above $a$. For a path in $A$, let $\tau$ be its first time at $a$. Keep the path unchanged through time $\tau$, and reflect its subsequent positions about $a$: set $S'_k=S_k$ for $k\le\tau$, and $S'_k=2a-S_k$ for $k>\tau$. Each step after $\tau$ has its sign reversed, so the reflected sequence is also a valid walk path. If the original endpoint is $y<a$, the reflected endpoint is $2a-y>a$; thus this map sends $A$ into $B$. Conversely, any path in $B$ must visit $a$, because it starts below $a$, ends above $a$, and has steps of size one. Reflecting it after its first visit to $a$ gives a path ending below $a$. Reflection twice returns the original path, so this is a bijection between $A$ and $B$. Every length-$n$ increment sequence has probability $2^{-n}$; therefore the two sets have equal probability. The event $\{M_n\ge a\}$ is the disjoint union of $\{S_n\ge a\}$ and $A$, while $\{S_n\ge a+1\}=B$ because endpoints are integer-valued. Hence the stated identity follows. If $a\le0$, then $M_n\ge0\ge a$ for every path, so the probability is $1$. $\square$

Evaluating the Endpoint Tails

Each endpoint tail can be evaluated by counting the number of upward steps. Let $K_n$ be the number of $+1$ increments among the first $n$ steps. A path with $K_n=k$ has endpoint $S_n=k-(n-k)=2k-n$, and there are $\binom{n}{k}$ such paths, each with probability $2^{-n}$. Thus an endpoint threshold $b$, where $b$ is an integer, corresponds to $k\ge\lceil(n+b)/2\rceil$. The binomial coefficient is understood to be zero when its lower argument is outside $0,\ldots,n$, and a sum whose lower limit exceeds $n$ is zero.

Theorem (Exact binomial form): For $n\ge0$ and integer $a\ge1$, $$ \mathbb{P}(M_n\ge a) =2^{-n}\left[ \sum_{k=\lceil(n+a)/2\rceil}^{n}\binom{n}{k} + \sum_{k=\lceil(n+a+1)/2\rceil}^{n}\binom{n}{k} \right]. $$ If $n+a$ is even and $r=(n+a)/2$, this becomes $$ \mathbb{P}(M_n\ge a) =2^{-n}\left[\binom{n}{r}+2\sum_{k=r+1}^{n}\binom{n}{k}\right]. $$ If $n+a$ is odd and $q=(n+a+1)/2$, it becomes $$ \mathbb{P}(M_n\ge a)=2^{1-n}\sum_{k=q}^{n}\binom{n}{k}. $$

Proof. The path count above gives $\mathbb{P}(S_n\ge b)=2^{-n}\sum_{k=\lceil(n+b)/2\rceil}^{n}\binom{n}{k}$. Substituting $b=a$ and $b=a+1$ into the running-maximum identity proves the first formula. If $n+a$ is even, then $\lceil(n+a)/2\rceil=r$ and $\lceil(n+a+1)/2\rceil=r+1$. Adding the two sums counts $\binom{n}{r}$ once and each term with $k\ge r+1$ twice, giving the even case. If $n+a$ is odd, then $\lceil(n+a)/2\rceil=\lceil(n+a+1)/2\rceil=q$, so the two identical sums give the odd case. The zero-sum convention covers thresholds beyond the walk’s maximum possible value $n$. $\square$

Because $M_n$ is a nonnegative integer, its tail probabilities also determine its entire distribution. For every integer $m\ge0$, $\mathbb{P}(M_n\le m)=1-\mathbb{P}(M_n\ge m+1)$. For $m\ge1$, subtracting consecutive tails gives $\mathbb{P}(M_n=m)=\mathbb{P}(M_n\ge m)-\mathbb{P}(M_n\ge m+1)$. The mass at zero is instead $\mathbb{P}(M_n=0)=1-\mathbb{P}(M_n\ge1)$.

Worked Example: Four Steps and Threshold Two

Take $n=4$ and $a=2$. Here $n+a=6$ is even, so $r=3$. The exact formula gives

\mathbb{P}(M_4\ge2) =\frac{1}{16}\left[\binom{4}{3}+2\sum_{k=4}^{4}\binom{4}{k}\right] =\frac{1}{16}\left[4+2(1)\right] =\frac{6}{16} =\frac38.

To check using the two endpoint tails separately, $S_4\ge2$ requires $K_4\ge3$, giving $(\binom43+\binom44)/16=5/16$. The event $S_4\ge3$ requires $K_4\ge4$, giving $\binom44/16=1/16$. Their sum is $5/16+1/16=6/16=3/8$, as above. In particular, one of the six paths reaching the barrier finishes below it; reflection pairs that path with the single path ending at $4$.

Worked Example: Five Steps and an Odd Parity Case

Take $n=5$ and $a=2$. Since $n+a=7$ is odd, $q=(n+a+1)/2=4$. Therefore

\mathbb{P}(M_5\ge2) =2^{1-5}\sum_{k=4}^{5}\binom{5}{k} =\frac{1}{16}\left(5+1\right) =\frac38.

Directly from the two endpoint probabilities, $S_5\ge2$ requires $K_5\ge4$, so its probability is $(\binom54+\binom55)/32=6/32$. Also, $S_5\ge3$ requires $K_5\ge4$, so its probability is again $6/32$. Adding gives $12/32=3/8$. The equality of the tails here is a parity effect: a five-step walk cannot end at $2$, so the thresholds $2$ and $3$ select the same possible endpoints.

Worked Example: The Full Maximum Distribution in Three Steps

For $n=3$, the walk can have maximum $0,1,2,$ or $3$. First compute the positive-threshold tails:

\begin{aligned} \mathbb{P}(M_3\ge1)&=\mathbb{P}(S_3\ge1)+\mathbb{P}(S_3\ge2)=\frac{4}{8}+\frac{1}{8}=\frac58,\\ \mathbb{P}(M_3\ge2)&=\mathbb{P}(S_3\ge2)+\mathbb{P}(S_3\ge3)=\frac{1}{8}+\frac{1}{8}=\frac14,\\ \mathbb{P}(M_3\ge3)&=\mathbb{P}(S_3\ge3)+\mathbb{P}(S_3\ge4)=\frac{1}{8}+0=\frac18. \end{aligned}

These endpoint values follow from the eight equally likely increment sequences: the endpoints $3,1,-1,-3$ occur respectively $1,3,3,1$ times. Taking differences of tails gives $\mathbb{P}(M_3=0)=1-5/8=3/8$, $\mathbb{P}(M_3=1)=5/8-1/4=3/8$, $\mathbb{P}(M_3=2)=1/4-1/8=1/8$, and $\mathbb{P}(M_3=3)=1/8$. The masses sum to $3/8+3/8+1/8+1/8=1$. As a direct check, the paths with maximum exactly $1$ are $UDU$, $UDD$, and $DUU$, where $U$ denotes a $+1$ step and $D$ a $-1$ step; there are three, giving probability $3/8$.

Strict Barriers and a Common Mistake

The reflection counts paths that end strictly below the barrier and pairs them with paths ending strictly above it. It does not pair them with paths ending at or above it: paths ending exactly at $a$ already belong to the first endpoint event in the theorem. Since the walk is integer-valued, the reflected endpoint condition is $S_n\ge a+1$, not $S_n\ge a$.

Common mistake. It is tempting to write $\mathbb{P}(M_n\ge a)=\mathbb{P}(S_n\ge a)$, as though finishing above the barrier were necessary to have crossed it. For $n=4$ and $a=2$, that calculation gives only $\mathbb{P}(S_4\ge2)=5/16$, which is too small. The missing paths visit $2$ and later finish below $2$; reflection shows that their probability is $\mathbb{P}(S_4\ge3)=1/16$. Thus the corrected answer is $5/16+1/16=3/8$.

The maximum tail is useful whenever a question asks whether a walk ever crosses a level by a fixed time. It replaces a path-dependent event with endpoint probabilities, which can be evaluated by binomial coefficients. The formula relies on the walk’s unit-sized steps and the symmetry of its increments: the reflection preserves the set of equally likely paths. For a different step distribution, or for unequal probabilities of upward and downward steps, this same counting argument need not preserve probability.

Check Your Understanding

Use positive integer thresholds in the reflection identity, and show the endpoint-tail calculation that supports each numerical answer.

For $n=4$ and $a=1$, compute $\mathbb{P}(M_4\ge1)$ using the parity-specific binomial formula.
For $n=6$ and $a=3$, identify the parity case and write the exact binomial sum for $\mathbb{P}(M_6\ge3)$.
Explain why paths ending strictly below $a$ that have visited $a$ are paired with paths ending at least $a+1$, rather than at least $a$.
For $n=3$, use consecutive tails to compute $\mathbb{P}(M_3=1)$.
What does the formula give when $a>n$, and why is that consistent with the largest possible value of $M_n$?

The Distribution of the Running Maximum

What You'll Learn