Is there an intuitive way to see this property of random walks?

Question

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.

Answer 1

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).$$