Say there is a random walk $\{S_n\}$ with $S_0=0$ and $0<p=P(S_1=1)<\frac{1}{2}$. We know such a random walk would go to $-\infty$ eventually. Define the stopping time $T=\inf\{n: S_n=-\infty\}$, how can we argue that the stopping time is finite a.s., i.e., $P(T<\infty)=1$?

I know we definitely will use $0<p=P(S_1=1)<\frac{1}{2}$, and I know for such $p$, the returning time is not finite, which is transient. How can I apply this to show the stopping time $T$ is finite a.s.? Or is there another approach to this?


You have not told us enough to reach your conclusions.

If you are saying each independent step is $+1$ with probability $p$ and $-1$ with probability $1-p$, with $p \lt \frac12$, then $S_n \not = -\infty$ for finite $n$, since $-n \le S_n \le n$. So $\Pr(T \lt \infty)=0$.

Since $p \lt \frac12$ you could conclude that $$\lim_{n \to +\infty} S_n = -\infty$$ with probability $1$ but that is not the same thing at all.

  • $\begingroup$ Thanks for your answer! You are right about all the assumptions that I don't mention in my question (each independent step is +1 with probability p and −1 with probability 1−p, with p<1/2) From your argument, I think maybe we cannot reach the conclusion that the stopping time is finite a.s. The reason I asked this I want to check the conditions of Optional stopping theorem, so I can use it to reach another conclusion. $\endgroup$ – Qomo Apr 25 '12 at 23:30

Considering $\:\:S_n=\sum_{j=1}^nX_j,\:\:X_j\:\text{ i.i.d},\:X_j\in\mathbb Z.$

If $\:\:\mathbb E[X_j]<0,\:$ by the strong law of large numbers : $$\lim_{n\to\infty}\frac{S_n}{n}\overset{a.s}{\longrightarrow}\mathbb E[X_j]<0\\\implies S_n\overset{n\to\infty}{\longrightarrow}-\infty.$$

Thus, $$\inf\{n: S_n=-\infty\}<\infty,$$

So that the random walk will eventually reach its stopping time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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