13
$\begingroup$

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.

  • 1
    the reflection principle, combined with $\mathbb P(S_n = r+1) = 0$2012-10-29

1 Answers 1

7

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

  • 1
    @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$.2015-09-15