Consider a discrete random walk taking values +1 or -1 with probabilities p and q, respectively. Let $S_n = \sum_{k=1}^{n}X_k$. Let $[-A,B]$ be an interval, $A,B \geq 1$. Now define
$$\tau =\min(n:n \geq 0, S_n \leq -A \cup S_n \geq B).$$
I need to show that $\tau$ is finite almost surely.
What I am trying:
$P_0(\tau < \infty) = P_0(\exists n<\infty \mbox{ so that } {S_n=-A}\mbox{ or }{S_n=B})$
Can someone put me in the right direction here? My hint was to use strong law of large numbers.
Best Answer
Consider the following extremely useful proposition "What always stands a reasonable chance of happening will (almost surely) happen - sooner rather than later."
Let $T$ a stopping time such that for some $N$ and $\epsilon>0$ we have for all $n$ that $P(T \leq n + N|\mathcal{F}_n) > \epsilon$ a.s., then $E[T] < \infty$, and in particular $T<\infty$ a.s.
Hint: Using induction and $P(T > kN) = P(T>kN; T>(k-1)N)$ show $P(T > kN) \leq (1-\epsilon)^k$.
Now how can we apply the proposition (which is exercise E10.5 in David Williams' Probability with Martingales)? No matter where you are in your random walk, you always have a fixed positive probability $p^{A+B}>0$ that the next $A+B$ coin flips are heads, in which case you stop in at most $A+B$ steps. Thus the proposition implies $E[\tau] < \infty$.