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

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!

• This looks like application of the strong Markov property (en.wikipedia.org/wiki/Markov_property#Strong_Markov_property). In more detail, suppose $\mathbb{P}(\tau < \infty) = 1$. Then the chain returns to 0 (or lower) with probability $1$ and because $\tau$ is a stopping time the SMP says the chain starts afresh from there. Then apply the same argument again. So $S_n \not\to \infty$ a.s. May 18 '18 at 8:47
• That is a good argument. Does this hold for the general non-i.i.d. case? May 19 '18 at 0:47
• @SpawnKilleR - the key required property for the argument I had in mind is the Strong Markov Property. Unfortunately this doesn't hold for the general non-i.i.d case. Indeed, if you allow dependent $X_i$ you can make your chain recurrent until it first returns to ($\leq$) $0$ and then drift off to infinity after that (then you'd have $\mathbb{P}(\tau < \infty)=1$ and $S_n\to\infty$!). May 21 '18 at 15:57

The random walk $(S_n; n \ge 0)$ satisfies the strong Markov property. In more detail, the random variable $\tau$ is a stopping time, i.e. adapted to the process, so the strong Markov property implies the trajectory $(S_{\tau+n}; n \ge 1)$ after $\tau$ is independent of $(S_k; 0\le k < \tau)$ given $S_\tau$. Also, the random walk is homogeneous in time and space so the distribution of the trajectory after $\tau$ is also the same.
Suppose that $\mathbb{P}(\tau = \infty) = 0$, i.e. $\mathbb{P}(\tau < \infty) = 1$ and the Markov chain a.s. goes $\le 0$ in finite time. The idea is to use this and the SMP to show the chain repeatedly goes $\le 0$ and thus $S_N \not\to \infty$.
Let $\tau_0 = \tau$ and recursively define $\tau_{n+1} = \inf\{\tau > \tau_n: S_\tau \le S_{\tau_n}\}$. Note that by construction $0 \ge S_{\tau_0} \ge S_{\tau_1} \ge \ldots$. Moreover, $\tau_0$ is a.s. finite by supposition. The SMP implies $(S_{\tau_0 + n}; n \ge 1)$ is independent of the past (given $S_{\tau_0}$, and the precise value $\le 0$ doesn't matter) and homogeneity of the random walk implies $\tau_1$ has the same distribution* as $\tau_0$ and in particular is finite a.s. Applying the argument repeatedly shows $\tau_n$ is finite a.s. So $\tau_n \to \infty$ and so $S_{\tau_n} \le 0$. Hence $S_n \not\to \infty$.
Regarding relaxed assumptions- Do you have a specific scenario in mind for the non-i.i.d case? (You can prove something along the lines of my answer for time homogenous Markov chains with extra conditions when starting from $\le 0$ at step *)
• One specific case would be the case of this question for a Gaussian distribution. For that case we have that the random walks is given by $S_n = S_{n-1} + \{ X^2_n - (X_1 + \dots + X_{n-1})^2 \}$ where $X_n$ are i.i.d Gaussian with mean $\mu$ and variance equal to $1$. May 22 '18 at 18:31
• Sorry, it should have been $S_n= S_{n-1} + \frac{1}{2}\bigg\{\frac{2X_n(X_1+\dots+X_{n-1})}{n-1} - \Big[\frac{X_1 +\dots +X_{n-1}}{n-1}\Big]^2\bigg\}$ May 22 '18 at 19:20