Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
the reflection principle, combined with $\mathbb P(S_n = r+1) = 0$ –  mike Oct 29 '12 at 18:39

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

share|improve this answer

Your Answer

 
discard

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.