Worked Calculations for Walk Maxima

From Path Counts to Joint Probabilities

For a short simple symmetric walk, an endpoint probability is not enough to answer a question about how high the walk rose along the way. A path can finish at a low value after visiting a much higher one, or finish at its maximum. To calculate both features together, count the paths with the required endpoint and maximum, then divide by the number of equally likely paths. Reflection provides a compact count, while small examples make its barrier and parity details concrete.

Let $(\Omega,\mathcal{F},\mathbb{P})$ support independent increments $\xi_1,\xi_2,\ldots$, each taking $+1$ and $-1$ with probability $\tfrac12$. Set $S_0=0$ and $S_k=\sum_{r=1}^k \xi_r$ for integers $k\ge1$. The state space is $\mathbb{Z}$, the time index is discrete $k\ge0$, and the running maximum through time $n$ is $M_n=\max_{0\le k\le n}S_k$. Every length-$n$ sequence of steps has probability $2^{-n}$.

Write $\binom{n}{r}=0$ if $r$ is not an integer in $\{0,\ldots,n\}$. Otherwise, $\binom{n}{r}$ is the number of ways to choose $r$ objects from $n$. In particular, an endpoint $j$ is possible only if $n+j$ is even and $|j|\le n$: the number of up-steps must be $(n+j)/2$.

Theorem (Joint endpoint and maximum count): Let $n\ge0$, let $j$ be an integer and let $m$ be a nonnegative integer. If $j>m$, or $n+j$ is odd, or $|j|>n$, then $\mathbb{P}(S_n=j,M_n=m)=0$. In the other cases, $$ \mathbb{P}(S_n=j,M_n=m) =2^{-n}\left\{\binom{n}{(n+2m-j)/2} -\binom{n}{(n+2m+2-j)/2}\right\}. $$

The requirement $j\le m$ is necessary because the endpoint itself is among the values used to define $M_n$; also $m\ge0$ because $S_0=0$. The binomial convention automatically removes terms whose indices are impossible. To justify the formula, first count paths whose maximum is at most a barrier, then take the difference between two such counts.

Proof. A length-$n$ path ending at $j$ has $(n+j)/2$ up-steps, so there are $\binom{n}{(n+j)/2}$ such paths when that index is admissible. For a nonnegative integer $r$ with $j\le r$, paths ending at $j$ that ever reach $r+1$ are in bijection with all length-$n$ paths ending at $2(r+1)-j$. To define the map, take a path that reaches $r+1$, find its first visit there, and reflect every step after that visit: up-steps become down-steps and down-steps become up-steps. The endpoint changes from $j$ to $(r+1)+((r+1)-j)=2(r+1)-j$. Conversely, every path ending at $2(r+1)-j>r+1$ visits $r+1$; reflecting its steps after the first such visit recovers a path ending at $j$ that reaches $r+1$. Thus the number of paths ending at $j$ with maximum at most $r$ is $$ \binom{n}{(n+j)/2}-\binom{n}{(n+2r+2-j)/2}. $$ For $m\ge1$, subtract this count with $r=m-1$ from the count with $r=m$. The first binomial terms cancel, leaving the difference in the theorem. For $m=0$, the event $M_n=0$ is the event $M_n\le0$, so the displayed count with $r=0$ applies directly. Its first term equals $\binom{n}{(n-j)/2}$, since $\binom{n}{a}=\binom{n}{n-a}$; this is the first term in the theorem’s formula at $m=0$. Each path has probability $2^{-n}$, which gives the probability formula. If $j>m$, the endpoint exceeds the proposed maximum; if parity or the endpoint range fails, no path ends at $j$. These cases have probability zero. $\square$

Worked Calculations

In each calculation, first check whether the event is possible, then evaluate the two binomial coefficients. The difference counts paths with the exact maximum, not paths whose maximum is merely below a barrier.

Worked Example: Endpoint Zero and Exact Maximum One

For $n=4$, find $\mathbb{P}(S_4=0,M_4=1)$. The endpoint has the correct parity, since $4+0$ is even, and $0\le1$, so the joint event is possible. The formula gives

\begin{aligned} \mathbb{P}(S_4=0,M_4=1) &=2^{-4}\left\{\binom{4}{(4+2-0)/2} -\binom{4}{(4+2+2-0)/2}\right\}\\ &=\frac{1}{16}\left\{\binom{4}{3}-\binom{4}{4}\right\}\\ &=\frac{1}{16}(4-1)=\frac{3}{16}. \end{aligned}

Check by listing paths. A path ending at zero has two up-steps and two down-steps, so there are $\binom{4}{2}=6$ paths. Written as step sequences, they are UUDD, UDUD, UDDU, DUUD, DUDU, and DDUU, where U means $+1$ and D means $-1$. Their respective maxima are $2,1,1,1,0,0$. Exactly three have maximum one, so the probability is $3/16$, as calculated. The value $M_4=1$ means the walk reaches 1 but never reaches 2.

Worked Example: Endpoint One and Exact Maximum Two

For $n=5$, find $\mathbb{P}(S_5=1,M_5=2)$. The endpoint is possible because $5+1=6$ is even and $|1|\le5$, and $1\le2$. Substitution gives

\begin{aligned} \mathbb{P}(S_5=1,M_5=2) &=2^{-5}\left\{\binom{5}{(5+4-1)/2} -\binom{5}{(5+4+2-1)/2}\right\}\\ &=\frac{1}{32}\left\{\binom{5}{4}-\binom{5}{5}\right\}\\ &=\frac{1}{32}(5-1)=\frac{1}{8}. \end{aligned}

Check by counting paths below two barriers. There are $\binom{5}{(5+1)/2}=\binom{5}{3}=10$ paths ending at 1. Among them, the paths with maximum at most 2 are counted by subtracting paths that reach 3. Reflection sends those paths to paths ending at $2\cdot3-1=5$, of which there are $\binom{5}{(5+5)/2}=\binom{5}{5}=1$. Thus 9 paths have maximum at most 2. Paths with maximum at most 1 are counted by subtracting paths that reach 2; reflection sends those to paths ending at $2\cdot2-1=3$, giving $\binom{5}{(5+3)/2}=\binom{5}{4}=5$ paths to subtract. Thus 5 paths have maximum at most 1. The difference $9-5=4$ have maximum exactly 2, and $4/2^5=4/32=1/8$, agreeing with the formula.

Worked Example: A Boundary Maximum of Zero

For $n=4$, find $\mathbb{P}(S_4=-2,M_4=0)$. This endpoint is possible: $4+(-2)=2$ is even and $|-2|\le4$. The maximum is at least zero because the walk starts at zero, and the endpoint $-2$ does not exceed the proposed maximum zero. Hence this is a possible boundary case. Calculate

\begin{aligned} \mathbb{P}(S_4=-2,M_4=0) &=2^{-4}\left\{\binom{4}{(4+0-(-2))/2} -\binom{4}{(4+0+2-(-2))/2}\right\}\\ &=\frac{1}{16}\left\{\binom{4}{3}-\binom{4}{4}\right\}\\ &=\frac{1}{16}(4-1)=\frac{3}{16}. \end{aligned}

Check by listing the endpoint paths. Ending at $-2$ requires one up-step and three down-steps, so there are $\binom{4}{1}=4$ paths. The path UDDD reaches 1 and is excluded. The other three paths, DUDD, DDUD, and DDDU, never rise above zero, so each has maximum zero. Thus the joint probability is $3/16$. For a parity check, the event $S_4=-1$ has probability zero because $(4-1)/2=3/2$ is not an integer; no choice of maximum can make that endpoint possible.

Boundary Checks and a Common Counting Error

For an exact calculation, keep three checks separate. First, test endpoint feasibility: $n+j$ must be even and $|j|\le n$. Second, test the maximum: it must be a nonnegative integer at least as large as $j$. Third, use the correct crossing level. A maximum at most $m$ excludes paths that reach $m+1$, not paths that reach $m$. The distinction matters because reaching $m$ is allowed when the maximum is exactly $m$.

Common mistake: reflecting at the proposed maximum. Return to $n=4,j=0,m=1$. To count paths with maximum at most 1, the excluded paths reach level 2; reflection sends them to endpoint $2\cdot2-0=4$, giving $\binom{4}{(4+4)/2}=\binom{4}{4}=1$ path to exclude from the 6 endpoint paths. Hence there are $6-1=5$ paths with maximum at most 1. To count paths with maximum at most 0, exclude paths that reach level 1; reflection gives endpoint 2 and $\binom{4}{(4+2)/2}=\binom{4}{3}=4$, leaving $6-4=2$. The exact-maximum count is $5-2=3$.

A mistaken calculation reflects at level 1 when counting paths with maximum at most 1, and at level 0 when counting paths with maximum at most 0. It then subtracts $\binom{4}{3}=4$ from 6 in the first count and $\binom{4}{2}=6$ from 6 in the second, producing $2-0=2$ paths. The first reflection removed paths that merely reach 1, even though those paths are allowed; the second treats the starting value 0 as a barrier hit. Using the first forbidden level, one above the allowed maximum, avoids both errors.

These calculations are useful whenever a question specifies both where a walk finishes and how high it has gone. The binomial difference turns a path constraint into exact arithmetic, and the path-list checks for short walks help catch incorrect barriers or parity indices before using the formula on larger $n$.

Check Your Understanding

For each question, first decide whether the event is possible. When it is, use the binomial formula and verify the count by subtracting paths under adjacent maximum bounds.

For $n=3$, calculate $\mathbb{P}(S_3=1,M_3=1)$. How many paths contribute?
For $n=4$, why is $\mathbb{P}(S_4=1,M_4=2)=0$, regardless of the proposed maximum?
For $n=4$, calculate $\mathbb{P}(S_4=-4,M_4=0)$, and explain why this is an endpoint boundary case.
When counting paths with maximum at most $m$, which level must excluded paths reach before reflection?
Explain why a proposed exact maximum $m$ must satisfy both $m\ge0$ and $j\le m$ for the event $S_n=j,M_n=m$ to occur.

Worked Calculations for Walk Maxima

What You'll Learn