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

In order to solve a puzzle in correspondence with a friend, I am using a simple random walk hitting time calculation based upon the reflection principle as it is expressed in this University of Chicago document, here. However the author skips over a step and I haven't been able to fill in the gap.

Let $S_n$ be a random walk starting at zero and $\tau(m)$ be the first time it reaches $m\geq1$. Then define a new path, for $n\geq0$: \begin{align} S_n^*= \begin{cases} S_n, & \text{if }n\leq \tau(m) \\ 2m-S_n, & \text{if }n> \tau(m) \end{cases} \end{align} It is easy to see that $S_n^*$ is also a random walk. In the event $\tau(m)< n$, the two walks are on opposite sides unless they are both on $m$. We are interested in the event $S_n=m+k$ with $k\geq0$, which depends upon $\tau(m)< n$ to be non zero in probability. Thus: \begin{align} P(S_n=m+k) \begin{cases} 0, & \text{if }n\leq \tau(m) \\ P(S_n=m+k, \tau(m)< n), & \text{if }n> \tau(m) \end{cases} \end{align} This is equivalent in probability to $P(S_n^*=m+k, \tau(m)< n)$, which is equivalent in position to $P(S_n=m-k, \tau(m)< n)$. Therefore we can marginalize out $P(S_n=m+k)$ to compute the marginal probability $P(\tau(m)< n)$ as follows. \begin{align} P(\tau(m)< n)=\sum_{k=-\infty}^{\infty}P(S_n=m+k, \tau(m)< n)=P(S_n=m)+2P(S_n >m) \end{align} It is the very last equality that I don't see an obvious approach to. \begin{align} \sum_{k=-\infty}^{\infty}P(S_n=m+k, \tau(m)< n)=P(S_n=m)+2P(S_n >m) \end{align}

share|cite|improve this question
up vote 3 down vote accepted

Note that $$P(S_n\gt m,\tau(m)\lt n)=P(S_n\lt m,\tau(m)\lt n),$$ which explains all the sum except the $k=0$ term, hence the identity holds if and only if $$P(S_n=m,\tau(m)\lt n)=P(S_n=m), $$ which is wrong in general. My guess is that the question is to show \begin{align} P(\tau(m)\leqslant n)=\sum_{k=-\infty}^{\infty}P(S_n=m+k, \tau(m)\leqslant n)=P(S_n=m)+2P(S_n \gt m), \end{align} which holds thanks to the first identity above and $$P(S_n=m,\tau(m)\leqslant n)=P(S_n=m), $$ since $[S_n=m]\subseteq[\tau(m)\leqslant n]$.

share|cite|improve this answer
You are correct. $P(\tau(m)<n)$ is $P(\tau(m)\leqslant n)$ in the original document. I had assumed it was an error but I can see now that it wasn't. – Meadowlark Bradsher Nov 11 '12 at 23: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.