Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For an $n$-step symmetric simple random walk (start at origin 0 and each step 1 unit towards left or right with equal probability,) an interesting fact is that the probability that you stop exactly at $r$ is equal to the probability that in the whole walk you've never reached $r+1$ but you've been to $r$. Is there a intuitive way to see this? Here, $n$ and $r$ are positive even numbers.

share|cite|improve this question
the reflection principle, combined with $\mathbb P(S_n = r+1) = 0$ – mike Oct 29 '12 at 18:39

Let $M_n$ denote the maximum distance to the right reached by the walk. Let $X_n$ denote the ending position of the random walk. The question is asking for an intuitive explanation for why $P(M_n = r) = P(X_n = r)$.

I think it's more intuitive to look at why $P(M_n \geq r) = P(X_n \geq r) + P(X_n \geq r+1)$ first. The walks with $M_n \geq r$ can be broken into two categories, depending on the point $s$ where they end: (1) $s \geq r$ and (2) $s < r$. In the latter case, you can take the part of the path after the first step that reaches $r$ and reflect it across the point $r$ so that it ends at a new point $s' > r$. This is the reflection principle that mike mentions in a comment, and the process is reversible. Since every path that reaches a point $s \geq r$ must have $M_n \geq r$, we have $$P(M_n \geq r) = P(X_n \geq r) + P(X_n \geq r+1).$$

Now, to the OP's question. $$\begin{align*} P(M_n = r) &= P(M_n \geq r) - P(M_n \geq r+1) \\ &= P(X_n \geq r) + P(X_n \geq r+1) - P(X_n \geq r+1) - P(X_n \geq r+2) \\ &= P(X_n = r) + P(X_n = r+1). \end{align*}$$ Since $n$ is even, the walk cannot stop on an odd number. Since $r$ is also even, this means $P(X_n = r+1) = 0$ (as mike also mentions in a comment). Therefore, $$P(M_n = r) = P(X_n = r).$$

share|cite|improve this answer
Can you explain how the reflection principle is being used here? For the case s<r, it is possible that such a random walk never crossed s even once. Where we accounting for such probability? – karmanaut Sep 11 '15 at 14:37
@karmanaut: We're looking at the case $M_n \geq r$, which means that the maximum distance to the right reached by the walk after $n$ steps is greater than or equal to $r$. If $s$ is the ending point, and $s < r$, then the walk must have reached both $r$ and $s$ at some point in order to have a maximum distance greater than $r$ and yet end at $s$. – Mike Spivey Sep 15 '15 at 18:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.