# Bounds on random walk with a negative drift

Consider a random walk $S_n = a_1+\dots+a_n$ where $a_n$ are iid random variables with $Ea_1 = a$ and $E|a_1|<\infty$.

By application of the Law of Large Numbers for $a<0$ we obtain that $$S_n/n\to a<0 \Rightarrow S_n\to-\infty \text{ P-a.s.} \quad (1)$$ and hence $S_n$ bounded from above with probability one: $$P(\sup\limits_nS_n(\omega) < \infty) = 1\quad (2)$$

My thoughts are the following: assume contrary, i.e. $$P(\omega:\sup\limits_nS_n(\omega) = \infty) = p>0,\quad (3)$$ then for this $\omega$ we have either that limit of $S_n$ does not exist, or that it is $+\infty$, which contradicts with $(1)$.

On the other hand, Didier Piau stated in When random walk is upper unbounded that $$P(\sup\limits_n S_n \geq M)<1 \quad(4)$$ for every positive $M$ - and I do not know how to prove it since the way I proved $(2)$ is based on the contradiction with $(3)$, while I cannot justify that $(3)$ contradicts with $(4)$. So my question is how to prove $(4)$?

-

## 1 Answer

If the walk were to almost surely exceed $M>0$, it would then go on to almost surely exceed $2M$, since the probability for that event is at least the product of two probabilities of exceeding $M$, both of which are $1$. By induction, for all positive integer multiples $nM$ of $M$ the walk would almost surely exceed $nM$.

Now let $p_n$ be the probability that $nM$ is the first positive integer multiple of $M$ that the walk doesn't exceed. By countable additivity, the probability that the walk is bounded from above is given by $\sum_{n=1}^\infty \,p_n$. Since $p_n=0$ for all $n$, this is zero, contrary to the fact that the walk is almost surely bounded from above.

-
Et voilà ! :-) –  Did Jul 13 '11 at 18:41
Comment voulez-vous dire? –  joriki Jul 13 '11 at 18:51