Proving that a random walk that diverges to infinity may not become negative

Question

Consider a random walk $S_n= \sum_{k=1}^n X_k$, where $\{X_k\}_{k=1}^\infty$ are independent and identically distributed random variables. Assume that $S_n \rightarrow \infty$ almost surely as $n \rightarrow \infty$. Let $$\tau = \inf\{n \geq 1: S_n \leq 0\}.$$

In the book "Stopped Random Walks - Limit Theorems and Applications" by Allan Gut I found a theorem stating that under the assumptions above $\tau$ is defective, i.e., $$\mathbb{P}(\tau = \infty)>0.$$ However, no proof for the theorem is provided. Could anyone provide any hints on how to prove this theorem? Also, does anyone know if there are any generalizations of the theorem for the case that $\{X_k\}_{k=1}^\infty$ are not i.i.d.? Thank you for your time!

Answer 1

In this answer I will present a proof which uses martingale methods; however, the proof works only for random walks with iid increments which satisfy certain integrability conditions (see the remark at the very end); for simplicity, I will assume that the increments are bounded, i.e. that there exists a constant $K>0$ such that

$$\mathbb{P}(|X_i| \leq K)=1. \tag{1}$$

---

For $\lambda>0$ set $$\phi(\lambda) := \mathbb{E}\exp(-\lambda X_1).$$

Since, by assumption, $S_n \to \infty$ almost surely, it follows from the Chung-Fuchs theorem that

$$\mathbb{E}(X_1)>0. \tag{2}$$

As $-\mathbb{E}(X_1) = \phi'(0)$ we find that $\phi'(0)<0$ and therefore we can find $\lambda>0$ such that $\phi(\lambda)<1 = \phi(0)$. Define

$$M_n := \exp(-\lambda S_n)$$

Using that the increments are independent and identically distributed, it is not difficult to see that $(M_n)_{n \geq 1}$ is a supermartingale. Applying the optional stopping theorem, we find that

$$\mathbb{E}(M_{n \wedge \tau})\leq \mathbb{E}(M_1) = \phi(\lambda) \tag{3}$$

for all $n \geq 1$. By the definition of $\tau$ we have

$$S_{n \wedge \tau}(\omega) \xrightarrow[]{n \to \infty} S_{\tau}(\omega) \leq 0 \quad \text{for $\omega \in \{\tau<\infty\}$}.$$

On the other hand, $S_n \to \infty$ a.s. implies that

$$S_{n \wedge \tau}(\omega) \xrightarrow[]{n \to \infty} \infty \quad \text{for $\omega \in \{\tau=\infty\}$}.$$

Combining both considerations and using that $\lambda$ is strictly positive, we find that

$$M_{t \wedge \tau_n} = \exp(-\lambda S_{n \wedge \tau}) \xrightarrow[]{n \to \infty} \exp(-S_{\tau}) 1_{\{\tau<\infty\}} = M_{\tau} 1_{\{\tau<\infty\}}.$$

Applying Fatous lemma we get

$$\begin{align*} \mathbb{E}(M_{\tau} 1_{\{\tau<\infty\}}) = \mathbb{E} \left( \lim_{n \to \infty} M_{n \wedge \tau} \right) &\leq \liminf_{n \to \infty} \mathbb{E}(M_{n \wedge \tau}) \\ &\stackrel{(3)}{\leq} \phi(\lambda) < 1. \tag{4} \end{align*}$$

As $\lambda>0$ and $S_{\tau}(\omega) \leq 0$ for any $\omega \in \{\tau<\infty\}$, we have

$$M_{\tau}(\omega) = \exp(-\lambda S_{\tau}(\omega)) \geq 1, \qquad \omega \in \{\tau<\infty\}$$

and therefore we conclude from (4) that

$$\mathbb{P}(\tau<\infty) \leq \phi(\lambda)<1$$

which is equivalent to saying that

$$\mathbb{P}(\tau=\infty)>0.$$

Remark: In the above proof, integrability conditions on the increments $X_i$ are needed for two reasons:

• to apply the Chung Fuchs theorem
• to know that the moment generating function $\phi$ is finite for $\lambda \in [0,\lambda_0]$ for some $\lambda_0>0$.

In particular, we can weaken the assumption $(1)$; it suffices to assume that that $\mathbb{E}(|X_1|)<\infty$ and that the negative part of $X_1$ has certain exponential moments.