Showing stopping is finite almost surely

Question

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.

Answer 1

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$.

Answer 2

We need notation. Say $X_1,\dots$ are iid with the specified distribution, and $$S_n=X_1+\dots+X_n.$$

Say $N=A+B$. Note that if there exists $n$ with $$X_n=X_{n+1}=\dots=X_{n+N-1}=1$$then $\tau<\infty$ (because why, exactly?).

So let $E_n$ be the event $$X_{nN}=X_{nN+1}=\dots=X_{(n+1)N-1}=1.$$The events $E_n$ are independent, and $\bigcup_n E_n$ implies $\tau<\infty$. So it's enough to show $$P\left(\bigcup_nE_n\right)=1.$$This follows from Borel-Cantelli.