# Almost surely finite stopping time for a random walk

We consider a simple symmetric random walk $(S_n)_{n \in \mathbb{N}}$ on $\mathbb{Z}$ which starts at 1 :

$S_0 = 1$ and there exists an iid sequence $(X_n)_{n \geq 1}$ such that $\mathbb{P}(X_1 = -1) = \mathbb{P}(X_1 = 1) = 1/2$ and $\forall n \in \mathbb{N}$ $S_{n+1} = S_n + X_{n+1}$

And we look at the stopping time $T = inf \{ n \geq 0, S_n = 0 \}$

Show that $S_{ min(T,n) }$ converges almost surely towards a random variable X but that it does not converge in $\mathbb{L}^1$. What is the distribution of X?

My first guess is that this convergence occurs iff $\: \: \mathbb{P} ( T < \infty ) = 1$ but how do we compute this probability? We could try to find an upper bound for $\: \: \mathbb{P} ( T = \infty )$ ? Borel-Cantelli doesn't seem to work here either.

If that works then we could use Doob's convergence theorem.

Thanks for any insight on this.

Hints:

1. Show that $$M_n := \frac{1}{(L(\theta))^n} e^{-\theta S_n}$$ is a martingale for any $\theta >0$ where $$L(\theta) := \frac{1}{2} (e^{\theta}+e^{-\theta}).$$
2. Conclude that $(M_{n \wedge T})_{n \geq 1}$ is a martingale; in particular, $$\mathbb{E}(M_{n \wedge T}) = 1.$$
3. Apply the dominated convergence theorem to show that $$1=\lim_{n \to \infty} \mathbb{E}(M_{n \wedge T}) = \mathbb{E} \left( 1_{\{T < \infty\}} \frac{1}{L(\theta)^T} \right)$$ for any $\theta>0$.
4. Let $\theta \downarrow 0$ to show that $$1 = \lim_{\theta \downarrow 0} \mathbb{E} \left( 1_{\{T < \infty\}} \frac{1}{L(\theta)^T} \right) = \mathbb{P}(T<\infty).$$
• Thank you! I have seen that hyperbolic cosine martingale before and so it's a good idea of linking it to random walks . – Psylex Dec 23 '17 at 15:10
• @Psylex You are welcome. – saz Dec 23 '17 at 15:24

We have $$S_n = S_0 + \sum_{k=1}^n X_k$$ then $$\tilde{S}_n = S_n - S_0 = \sum_{k=1}^n X_k$$ is a standard random walk and we can use the reflection principle (e.g. asked here) and we get:

\begin{align*}P(T = \infty) &= P\left( \bigcap_{n=0}^\infty \{S_n > 0\}\right) \\ &= P\left( \bigcap_{n=0}^\infty \{\tilde{S}_n > -1\}\right) \\&= \lim_{m\to\infty} P\left(\bigcap_{k=1}^m \{\tilde{S}_n \ge 0\}\right) \\ &= \lim_{m\to\infty} P\left(\max_{1 \le n \le m} \tilde{S}_n \ge 0\right) \\ &= \lim_{m\to \infty}\left( P(\tilde{S}_m \ge 0) + P(\tilde{S}_m \ge 1)\right) \\ &= \frac{1}{2} + \frac{1}{2} = 1 \end{align*}

• Thanks, i'll be sure to remember this reflection principle as of now. – Psylex Dec 23 '17 at 15:11