Counting Symmetric Random Walk Endpoints with Binomial Coefficients

Summary

The document clarifies how to calculate the endpoint probability for a simple symmetric random walk, in the context of applying the reflection principle. The number of paths ending at a given location is determined by the required counts of up and down moves, not by treating the endpoint itself as the number of up moves. If the walk has n steps and ends at x, solving for the number of up moves gives (n + x)/2, so the endpoint probability is the corresponding binomial coefficient multiplied by the probability of each path.

This resolves the stated confusion when the reflection principle maps an event involving the maximum and endpoint to a probability at a reflected endpoint. The formula also makes clear that reachable endpoints must have the same parity as the number of steps and lie within the walk’s possible range. The response is an algebraic explanation; it does not discuss extensions to biased walks or other step distributions.

Key ideas

• For a symmetric walk, an endpoint is determined by the difference between the numbers of up and down moves.
• The number of paths to endpoint x after n steps uses (n + x)/2 as the count of up moves.
• The endpoint probability is that binomial path count multiplied by the probability of an individual path.
• A reachable endpoint must satisfy the walk’s parity and range constraints.

Tags

# Random walks and using the reflection principle


# Random walks and using the reflection principle












Consider exercise 5.5 from Shreve volume 1:

For part (I), I understand how you can use reflection to show that $P(M_n^*\geq m, M_n=b)=P(M_n=2m-b)$. However, it seems to me that this latter probability is just a binomial, and hence:

$$P(M_n=2m-b)={n\choose 2m-b}(1/2)^n$$

This is not equal to the equation given; for example $n=6,m=2,b=0$ is a counterexample. What am I missing?

## Answer by AFK (score 1, accepted)

https://quant.stackexchange.com/a/17629

If you go up $u$ times and down $d$ times, your random walk ends up at $u-d$ at time $u+d$. Since there are ${u+d \choose u}$ ways to distribute the $u$ up moves among the $u+d$ moves $$ P(M_{u+d} = u-d) = {u+d \choose u} \frac{1}{2^{u+d}} $$ Setting $n = u+d$, $x = u-d = 2u-n$, so $u = n+x/2$, this is equivalent to $$ P(M_n = x) = {n \choose (n+x)/2} \frac{1}{2^n}. $$ So $$ P(M_n = 2m-b) = {n \choose (n-b)/2+m} \frac{1}{2^n} $$ as announced.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.