Proving the expectation of a stopping time of a random walk is finite Let $X_1,X_2,...$ be i.i.d. with $\mathbb{P}(X_i=\pm1)=1/2$. Let $a<0<b$ be integers and let $N=\min\{n:S_n\notin(a,b)\}$. I need to prove that $\mathbb{E}[N]<\infty$. I found this reference: If $t\in(a,b)$, then:
$$\mathbb{P}\{t+S_{b-a}\notin(a,b)\}\geq2^{-(b-a)}$$
I understand why this is true - since if $X_i=+1$ for every $i\in[1,b-a]_{\mathbb{N}}$, then $S_{b-a}=b-a=|(a,b)|$, and therefore $t+S_{b-a}\notin(a,b)$. The probability of this happening is of course $2^{-(b-a)}$. But then, the reference claims that if the last inequality is iterated, then:
$$\mathbb{P}\{N>n(b-a)\}\leq(1-2^{-(b-a)})^n$$
I have two problems with this:

*

*I cannot understand what is being iterated here. I guess the iteration happens $n$ times, and every time we substitute a different $t$, but I couldn't figure out exactly what is $t$ equal to each time.

*Since $N\geq0$:

$$\mathbb{E}[N]=\sum_{n=0}^{\infty}\mathbb{P}\{N>n\}$$
So actually, in order to prove $\mathbb{E}[N]$ is bounded, I need to find a bound for $p=\mathbb{P}\{N>n\}$. But this is not equivalent to the probability $q=\mathbb{P}\{N>n(b-a)\}$. Assuming $n$ is a positive integer, $q\leq p$. If the contrary were true ($p\leq q$) then it would've been easier.
Thanks!
 A: Here are some explanations:

*

*Note that $$\mathbb{P}\{N>n(b-a)\}\leq \mathbb{P}\{S_{n(b-a)}\in (a,b), S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\}.$$
Now
$$
\mathbb{P}\{S_{n(b-a)}\in (a,b), S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\} =\mathbb{P}\{S_{n(b-a)}\in (a,b)\,| \,S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\} \mathbb{P}\{S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\} \\
=\mathbb{P}\{S_{n(b-a)}\in (a,b)\,| \,S_{(n-1)(b-a)}\in (a,b)\} \mathbb{P}\{S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\}.
$$
The last equality above is due to Markov property. Now use your estimate, and few lines of calculations will give you
$$
\mathbb{P}\{S_{n(b-a)}\in (a,b)\,| \,S_{(n-1)(b-a)}\in (a,b)\}\leq (1-2^{-(b-a)}).
$$
Therefore you get the recursion
$$
\mathbb{P}\{S_{n(b-a)}\in (a,b), S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\} \leq (1-2^{-(b-a)})\mathbb{P}\{S_{(n-1)(b-a)}\in (a,b),\ldots,S_{(b-a)}\in (a,b)\}. 
$$

*

*Let me change notations slightly and write
$$
\mathbb{E}[N]=\sum_{i=0}^{\infty}\mathbb{P}\{N>i\}\leq  (b-a)\mathbb{P}\{N>0\} + (b-a) \mathbb{P}\{N>b-a\} + (b-a)\mathbb{P}\{N>2(b-a)\}+\ldots\\
=(b-a)\sum_{i=0}^{\infty}\mathbb{P}\{N>i(b-a)\}.
$$
In the above inequality first $(b-a)$ terms are clubbed together and then the probabilities are replaced by the largest term. Let me know if this clarifies your doubts.

