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!

  • 2
    $\begingroup$ 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. $\endgroup$ – P.Windridge May 18 '18 at 8:47
  • $\begingroup$ @P.Windridge why not post that as an answer? $\endgroup$ – Juho Kokkala May 18 '18 at 18:41
  • $\begingroup$ That is a good argument. Does this hold for the general non-i.i.d. case? $\endgroup$ – SpawnKilleR May 19 '18 at 0:47
  • $\begingroup$ @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$!). $\endgroup$ – P.Windridge May 21 '18 at 15:57
  • $\begingroup$ @JuhoKokkala - I didn't have time to fill in/check the details but intend to asap! $\endgroup$ – P.Windridge May 21 '18 at 16:03

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 *)

  • $\begingroup$ Well, my question was inspired by another question I am trying to solve: stats.stackexchange.com/questions/345184/… $\endgroup$ – SpawnKilleR May 22 '18 at 18:08
  • $\begingroup$ 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$. $\endgroup$ – SpawnKilleR May 22 '18 at 18:31
  • $\begingroup$ 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\}$ $\endgroup$ – SpawnKilleR May 22 '18 at 19:20

Your Answer

