Proving the expectation of a stopping time of a random walk is finite

Question

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!

Answer 1

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.