Joint Probabilities of the Endpoint and Maximum

Endpoint Probabilities Under a Barrier

A walk can end at a particular location while having followed many different routes to get there. Requiring that it avoid a level removes some of those routes, and the number removed depends on both the endpoint and the barrier. For a simple symmetric walk, reflection turns the excluded paths into an unrestricted endpoint count. This gives a direct formula for the joint event involving the endpoint and the running maximum.

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 $S_n=\sum_{k=1}^n \xi_k$, with state space $\mathbb{Z}$ and $S_0=0$. Use the filtration $\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. Its running maximum through time $n$ is $M_n=\max_{0\le k\le n}S_k$. In particular, $M_n\ge0$, because the starting position is included.

Write $q_n(x)=\mathbb{P}(S_n=x)$. Reaching $x$ in $n$ steps requires $r=(n+x)/2$ upward steps. Thus define

q_n(x)= \begin{cases} 2^{-n}\binom{n}{(n+x)/2}, & |x|\le n\ \text{and } n+x\text{ is even},\\ 0, & \text{otherwise}. \end{cases}

The two conditions in the first case are the support restrictions: the endpoint cannot be farther than $n$ from zero, and its parity must match $n$. The zero convention will also make the barrier formulas concise when a reflected endpoint is unreachable.

Theorem (Strict-barrier reflection formula): For an integer barrier $a>0$, integer endpoint $b<a$, and integer time $n\ge0$, $$ \mathbb{P}(S_n=b,\ M_n<a)=q_n(b)-q_n(2a-b). $$ If $a\le0$, then $\mathbb{P}(S_n=b,\ M_n<a)=0$ for every $b$, since $M_n\ge0$. For $a>0$, endpoints $b\ge a$ also give probability zero.

The strict inequality matters: $M_n<a$ means the walk never visits $a$ or any larger level. Since the walk moves in steps of size one and starts below $a$, avoiding level $a$ is equivalent to staying strictly below it.

Proof. Fix $a>0$ and $b<a$. Consider all length-$n$ paths from $0$ to $b$ that visit $a$. For such a path, let $\tau=\inf\{k\ge0:S_k=a\}$, its first visit to $a$. Keep the path unchanged through time $\tau$, and reflect the part after that time across level $a$: set $S'_k=S_k$ for $k\le\tau$ and $S'_k=2a-S_k$ for $k>\tau$. The reflected path still has steps of size one, starts at zero, and ends at $2a-b$. This operation is reversible: any path from $0$ to $2a-b$ must visit $a$, because $2a-b>a>0$ and the walk has nearest-neighbor steps. Reflecting after its first visit to $a$ recovers the original path. Hence this is a bijection between paths from $0$ to $b$ that visit $a$ and all paths from $0$ to $2a-b$. Each length-$n$ path has probability $2^{-n}$, so the probability of ending at $b$ after visiting $a$ is $q_n(2a-b)$. Subtracting this from the probability $q_n(b)$ of ending at $b$ leaves exactly the paths that do not visit $a$, which is the event $M_n<a$. If $a\le0$, then $M_n\ge0\ge a$, so the strict-barrier event is empty. If $b\ge a$, then $S_n=b$ itself implies $M_n\ge a$. $\square$

When the reflected endpoint is outside the support, its probability is simply zero; no separate adjustment is needed. For $a>0$ and $b<a$, the reflected endpoint $2a-b$ is strictly greater than $|b|$: if $b\ge0$, it is greater than $b$, and if $b<0$, it is greater than $-b$. It also has the same parity as $b$. Thus if $b$ is unreachable because $|b|>n$ or its parity is wrong, the reflected endpoint is unreachable as well. The formula then correctly gives zero.

Worked Example: Ending at Zero Below Level Two

For $n=4$, find the probability that the walk ends at $b=0$ and stays strictly below $a=2$. The endpoint satisfies $b<a$, and the barrier is positive, so the theorem applies. The endpoint $0$ is in the support because $|0|\le4$ and $4+0$ is even. The reflected endpoint is $2a-b=4$, also in the support.

q_4(0)=2^{-4}\binom{4}{2}=\frac{6}{16}, \qquad q_4(4)=2^{-4}\binom{4}{4}=\frac{1}{16}.

Subtracting gives

\mathbb{P}(S_4=0,\ M_4<2) =\frac{6}{16}-\frac{1}{16} =\frac{5}{16}.

Check by counting paths. Ending at zero in four steps requires two upward and two downward steps, so there are $\binom42=6$ equally likely paths. Of these, only the path with increments $+1,+1,-1,-1$ reaches level $2$. The other five stay below $2$, giving $5/16$, as in the formula.

Worked Example: A Barrier That Leaves Few Paths

For $n=3$, find the probability of ending at $1$ without reaching level $2$. Here $a=2>0$ and $b=1<2$. Both endpoints in the formula satisfy the support restrictions: $1$ and $3=2a-b$ have the same parity as $n=3$, and both have absolute value at most $3$.

q_3(1)=2^{-3}\binom{3}{2}=\frac{3}{8}, \qquad q_3(3)=2^{-3}\binom{3}{3}=\frac{1}{8}.

Therefore

\mathbb{P}(S_3=1,\ M_3<2) =\frac{3}{8}-\frac{1}{8} =\frac{1}{4}.

Check by listing the endpoint paths. To end at $1$ in three steps, the walk must make two upward steps and one downward step. The increment sequences are $+1,+1,-1$, $+1,-1,+1$, and $-1,+1,+1$. The first reaches $2$; the other two do not. Thus two of the eight equally likely increment sequences qualify, giving $2/8=1/4$.

From a Barrier Event to an Exact Maximum

The strict-barrier formula also gives the joint probability of an endpoint and an exact maximum. Since $M_n$ is integer-valued, for an integer $m\ge0$, the event $M_n=m$ is the difference between $M_n<m+1$ and $M_n<m$. Subtracting the corresponding strict-barrier probabilities yields the following result.

Corollary (Endpoint and exact maximum): For $m\ge1$ and $b\le m$, $$ \mathbb{P}(S_n=b,\ M_n=m)=q_n(2m-b)-q_n(2m+2-b). $$ For $m=0$ and $b\le0$, $$ \mathbb{P}(S_n=b,\ M_n=0)=q_n(b)-q_n(2-b). $$ In both formulas $q_n(x)=0$ when $x$ is outside the support. If $b>m$, the joint probability is zero.

Proof. For $m\ge1$, both barriers $m+1$ and $m$ are positive. The event $\{S_n=b,M_n=m\}$ is $\{S_n=b,M_n<m+1\}\setminus\{S_n=b,M_n<m\}$, since the maximum is integer-valued. The theorem gives the first probability as $q_n(b)-q_n(2m+2-b)$, and the second as $q_n(b)-q_n(2m-b)$. Their difference is $q_n(2m-b)-q_n(2m+2-b)$. For $m=0$, the maximum is already at least zero, so $M_n=0$ is equivalent to $M_n<1$; applying the theorem with $a=1$ gives $q_n(b)-q_n(2-b)$ for $b\le0$. Finally, $b>m$ implies $M_n\ge S_n=b>m$, which makes the event impossible. $\square$

Worked Example: Ending at Zero with Maximum Exactly One

For $n=4$, compute the probability that $S_4=0$ and $M_4=1$. Here $m=1$ and $b=0$, so the exact-maximum formula gives $q_4(2)-q_4(4)$. Both endpoints are supported: $2$ and $4$ are even, and their absolute values are at most $4$.

q_4(2)=2^{-4}\binom{4}{3}=\frac{4}{16}, \qquad q_4(4)=2^{-4}\binom{4}{4}=\frac{1}{16}.

Thus

\mathbb{P}(S_4=0,\ M_4=1) =\frac{4}{16}-\frac{1}{16} =\frac{3}{16}.

Check by counting. There are six four-step paths ending at zero. The paths with maximum exactly one have increment sequences $+1,-1,+1,-1$, $+1,-1,-1,+1$, and $-1,+1,+1,-1$. Each has probability $1/16$, so the total is $3/16$.

Support Checks and a Common Pitfall

Before evaluating a binomial coefficient, check both the endpoint and its reflected value against the support of the $n$-step walk. For example, with $n=3$, $a=2$, and $b=0$, the endpoint $b=0$ is not reachable because it has the wrong parity. The reflected endpoint is $2a-b=4$, which is beyond distance $3$. Thus both terms are zero and the joint event has probability zero. This illustrates why the convention $q_n(x)=0$ outside the support is part of the formula, not merely shorthand for a calculation.

Common mistake: confusing a strict barrier with a weak one. For $n=2$, $a=1$, and $b=0$, the strict event $M_2<1$ has probability $q_2(0)-q_2(2)=\tfrac12-\tfrac14=\tfrac14$. The only qualifying path is down then up. Using this strict-barrier answer for the weak condition $M_2\le1$ would incorrectly give $\tfrac14$. In fact, the paths up then down and down then up both end at zero and have maximum at most one, so the weak-barrier probability is $\tfrac12$. The first path visits level $1$, which excludes it from the strict event but not the weak one.

The reflection argument is useful because it separates an endpoint constraint from a path-wide constraint: the unrestricted endpoint probability is easy to count, and the paths violating the barrier correspond exactly to paths ending at a reflected location. The support convention handles small times and extreme endpoints without exceptions in each calculation. For an exact maximum, taking a difference of two strict-barrier probabilities is often simpler than counting paths whose maximum equals a level directly. In every application, keep track of whether the barrier is strict and include $S_0=0$ when interpreting the maximum.

Check Your Understanding

For each question, state the support checks before evaluating the probability.

For $n=5$, $a=2$, and $b=1$, compute $\mathbb{P}(S_5=1,M_5<2)$.
For $n=4$, $a=1$, and $b=0$, compute the strict-barrier probability. Which reflected endpoint appears?
For $n=4$, find $\mathbb{P}(S_4=0,M_4=0)$ using the $m=0$ formula.
Explain why a path ending at $b\ge a$ cannot satisfy $M_n<a$.
For $n=3$, $a=2$, and $b=0$, use the support convention to evaluate the joint probability without attempting an invalid binomial coefficient.

Joint Probabilities of the Endpoint and Maximum

What You'll Learn