The Exact Endpoint Distribution

From a Path to an Endpoint Probability

For a simple symmetric random walk, the endpoint after $n$ steps is determined by how many steps went up and how many went down. Counting the paths that produce a given endpoint therefore gives its probability directly. This turns a question about the whole distribution into a binomial-coefficient calculation, and it also tells us exactly which endpoints can occur at a specified time.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(\xi_k)_{k\ge1}$ be independent random variables with $\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12$, and define the discrete-time process $(S_n)_{n\ge0}$ by $S_0=0$ and $S_n=\sum_{k=1}^n\xi_k$. Its state space is $S=\mathbb{Z}$. From any state $i$, the transition probabilities are $p_{i,i+1}=\tfrac12$ and $p_{i,i-1}=\tfrac12$, with all other transition probabilities zero. Each row sums to $\tfrac12+\tfrac12=1$.

Fix a horizon $n\ge0$. If $U_n$ is the number of up-steps among the first $n$ increments, then there are $n-U_n$ down-steps. Thus the endpoint is $U_n-(n-U_n)=2U_n-n$. For an endpoint $j$, this equation requires $U_n=(n+j)/2$. A candidate endpoint is attainable exactly when this required number is an integer from $0$ through $n$.

Theorem (Exact endpoint distribution): For $n\ge0$ and $j\in\mathbb{Z}$, define $p_n(j)=\mathbb{P}(S_n=j)$. Then $$ p_n(j)= \begin{cases} 2^{-n}\binom{n}{(n+j)/2}, & \text{if } (n+j)/2 \text{ is an integer in } \{0,1,\ldots,n\},\\ 0, & \text{otherwise}. \end{cases} $$ Consequently, the support of $S_n$ is exactly $\{-n,-n+2,\ldots,n-2,n\}$, with the understanding that for $n=0$ this set is $\{0\}$.

Proof. Assume first that $k=(n+j)/2$ is an integer between $0$ and $n$. The event $S_n=j$ occurs precisely when exactly $k$ of the $n$ increments equal $1$. There are $\binom{n}{k}$ choices of the positions of these up-steps. Each specified sequence of $n$ increments has probability $(\tfrac12)^n=2^{-n}$, by independence. These sequences are disjoint events, so their probabilities add to $\binom{n}{k}2^{-n}$. If $k$ is not an integer in this range, no sequence can have exactly $k$ up-steps, and the probability is zero. For every integer $k$ from $0$ through $n$, choosing $k$ up-step positions produces endpoint $2k-n$; these are exactly the listed endpoints. This also covers $n=0$: there is one empty sequence, its endpoint is $0$, and its probability is $2^0\binom00=1$. $\square$

The theorem gives both a probability and a membership test. To calculate $\mathbb{P}(S_n=j)$, first solve for the required number of up-steps. If that number is an integer in the allowed range, count the paths and multiply by the probability of one path. Otherwise the probability is zero. The test is exact: it does not approximate a probability or discard any paths.

Worked Endpoint Calculations

Worked Example: Returning to Zero at Time Six

Find $\mathbb{P}(S_6=0)$. The transition rule at each state has probabilities $\tfrac12$ up and $\tfrac12$ down, so its row sum is $\tfrac12+\tfrac12=1$.

To end at $0$, the number of up-steps must be $$ k=\frac{6+0}{2}=3. $$ This is an integer between $0$ and $6$, so the endpoint is attainable. The number of paths is $$ \binom{6}{3}=\frac{6\cdot5\cdot4}{3\cdot2\cdot1}=20. $$ Every path has probability $2^{-6}=\tfrac1{64}$. Therefore $$ \mathbb{P}(S_6=0)=20\cdot\frac1{64}=\frac{20}{64}=\frac5{16}. $$

Check by the one-step recursion. At time $5$, reaching $1$ requires $3$ up-steps, so $p_5(1)=\binom53/2^5=10/32=5/16$. Reaching $-1$ requires $2$ up-steps, so $p_5(-1)=\binom52/2^5=10/32=5/16$. The last step gives $$ p_6(0)=\tfrac12p_5(-1)+\tfrac12p_5(1) =\tfrac12\cdot\tfrac5{16}+\tfrac12\cdot\tfrac5{16} =\frac5{16}, $$ matching the path count.

Worked Example: Endpoint Two at Time Eight

Find $\mathbb{P}(S_8=2)$. From every state, the two possible next-step probabilities sum to $\tfrac12+\tfrac12=1$.

The required up-step count is $$ k=\frac{8+2}{2}=5. $$ Since $5$ is an integer in $\{0,1,\ldots,8\}$, the endpoint is attainable. There are $$ \binom85=\binom83=\frac{8\cdot7\cdot6}{3\cdot2\cdot1}=56 $$ paths with five up-steps. Each of the eight increments has two equally likely possibilities, so each path has probability $2^{-8}=\tfrac1{256}$. Thus $$ \mathbb{P}(S_8=2)=\frac{56}{256}=\frac7{32}. $$

Check by the one-step recursion. To reach $1$ at time $7$, the walk needs $4$ up-steps, giving $p_7(1)=\binom74/2^7=35/128$. To reach $3$ at time $7$, it needs $5$ up-steps, giving $p_7(3)=\binom75/2^7=21/128$. Therefore $$ p_8(2)=\tfrac12p_7(1)+\tfrac12p_7(3) =\tfrac12\cdot\tfrac{35}{128}+\tfrac12\cdot\tfrac{21}{128} =\frac{56}{256}=\frac7{32}. $$ This agrees with the direct count.

Worked Example: The Extreme Endpoint at Time Five

Find $\mathbb{P}(S_5=5)$. At each state, the probabilities of moving up and down are $\tfrac12$ and $\tfrac12$, so the transition probabilities sum to $1$.

The required number of up-steps is $$ k=\frac{5+5}{2}=5. $$ There is exactly one way to choose all five steps as up-steps: $\binom55=1$. A specified five-step path has probability $2^{-5}=\tfrac1{32}$. Hence $$ \mathbb{P}(S_5=5)=\binom55\,2^{-5}=1\cdot\frac1{32}=\frac1{32}. $$

Check by the one-step recursion. At time $4$, reaching $4$ requires four up-steps, so $p_4(4)=\binom44/2^4=1/16$. Reaching $6$ in four steps is impossible, so $p_4(6)=0$. Consequently, $$ p_5(5)=\tfrac12p_4(4)+\tfrac12p_4(6) =\tfrac12\cdot\tfrac1{16}+\tfrac12\cdot0 =\frac1{32}. $$ The only path reaching $5$ is the all-up path, as the direct count also showed.

A Recursion as an Independent Check

The endpoint probabilities also obey a one-step recursion. This gives a second way to compute them and a useful way to check binomial calculations. Define $p_n(j)=\mathbb{P}(S_n=j)$ for every integer $j$, including endpoints with probability zero.

Proposition (Endpoint recursion): For every $n\ge0$ and $j\in\mathbb{Z}$, $$ p_{n+1}(j)=\tfrac12p_n(j-1)+\tfrac12p_n(j+1), $$ with initial values $p_0(0)=1$ and $p_0(j)=0$ for $j\ne0$.

Proof. For $S_{n+1}=j$, the position at time $n$ must be either $j-1$, followed by an up-step, or $j+1$, followed by a down-step. These two events are disjoint. The increment $\xi_{n+1}$ is independent of the first $n$ increments, and each of its two possible values has probability $\tfrac12$. Therefore the probability of the first event is $p_n(j-1)\tfrac12$, and that of the second is $p_n(j+1)\tfrac12$; adding them proves the recursion. At time zero, the defining sum is empty and $S_0=0$, which gives the stated initial values. $\square$

This recursion is consistent with the exact binomial formula, including at the boundaries of the support. To see the calculation, set $k=(n+1+j)/2$. When $k$ is an integer, the two probabilities on the right use the up-step counts $k-1$ and $k$, respectively. With the convention that $\binom nr=0$ when $r$ is outside the integers $0,\ldots,n$, their sum is $$ \tfrac12\,2^{-n}\binom{n}{k-1}+\tfrac12\,2^{-n}\binom{n}{k} =2^{-(n+1)}\left(\binom{n}{k-1}+\binom{n}{k}\right) =2^{-(n+1)}\binom{n+1}{k}. $$ The last equality is Pascal’s identity, which follows by separating the $k$-element subsets of an $(n+1)$-element set according to whether they contain its last element. If $k$ is not an integer, neither $j-1$ nor $j+1$ is attainable at time $n$, so both terms in the recursion are zero, as is $p_{n+1}(j)$. Thus the recursion agrees with the formula in all cases.

Common Error and Why the Count Works

A frequent error is to use the endpoint itself as the number of up-steps. For example, for $n=8$ and $j=2$, the incorrect count $\binom82=28$ treats the walk as if it had two up-steps. But two up-steps and six down-steps end at $2-6=-4$, not at $2$. The correct equation is $2k-8=2$, which gives $k=5$; hence the correct count is $\binom85=56$, and the probability is $56/256=7/32$, not $28/256=7/64$.

The binomial formula works because all length-$n$ increment sequences are equally likely, and the endpoint event groups together exactly those sequences with the required number of up-steps. It is important that the walk is symmetric and starts at $0$ for the formula in this form. If the initial state were a fixed integer $i$, the endpoint would be $i+2U_n-n$, so the same path count would be centered at $i$, not at $0$. The formula describes the distribution at a fixed time; it does not assert that endpoint distributions at different times are the same.

For a specified horizon, the practical order of operations is: solve $2k-n=j$; check that $k$ is an integer with $0\le k\le n$; evaluate $\binom nk$; and multiply by $2^{-n}$. If the check fails, the probability is zero. Keeping the support check separate from the arithmetic prevents applying a binomial coefficient to a non-existent path count.

Check Your Understanding

For each calculation, first determine whether the endpoint is attainable, then use the path count or the recursion to verify the probability.

At time $n=6$, find $\mathbb{P}(S_6=2)$. How many up-steps are required?
At time $n=5$, is endpoint $j=4$ attainable? Use the required up-step count to justify your answer.
Use the endpoint recursion to compute $p_3(1)$ from probabilities at time $2$.
Explain why the probability of any one specified length-$n$ path is $2^{-n}$.
For $n=4$, list the support of $S_4$ and calculate the probability of its largest endpoint.

The Exact Endpoint Distribution

What You'll Learn