# First exit time of a simple random walk

Let $$S_n=\displaystyle\sum_{i=1}^{n}X_i$$ be the simple random walk with $$S_0=0$$. Now define the stopping time $$\tau=\inf\{n>0| S_n\notin (a,b)\}.$$

I am trying to follow some steps in a book and just need to understand how it ends up with the following inequalities with the goal of showing that $$E(\tau)<\infty$$.

$$P(S_{b-a}\notin (a,b))\geq2^{-(b-a)}$$ and supposedly iterating this gives $$P(\tau>n(b-a))\leq (1-2^{-(b-a)})^n.$$

Can someone explain how we can derive these inequalities? Thank you!

First, $$a<0 are integers and the first inequality should be $$\mathsf{P}(x+S_{b-a}\notin (a,b))\ge 2^{-(b-a)}, \quad x\in (a,b).$$ This inequality holds because $$\{X_i=1 \text{ for all } 1\le i\le (b-a)\}\subset \{x+S_{b-a}\notin (a,b)\}$$ for any $$x\in(a,b)$$. As for the second inequality, \begin{align} \mathsf{P}(\tau> 1(b-a))&\le \mathsf{P}(S_{b-a}\in(a,b))\le 1-2^{-(b-a)}, \\[1em] \mathsf{P}(\tau>2(b-a))&=\mathsf{P}(\tau>2(b-a),S_{b-a}\in (a,b)) \\ &=\mathsf{E}[\mathsf{P}(\tau>2(b-a)\mid S_{b-a})1\{S_{b-a}\in (a,b )\}] \\ &\le \mathsf{E}[\mathsf{P}(S_{b-a}+(S_{2(b-a)}-S_{b-a})\in (a,b)\mid S_{b-a})1\{S_{b-a}\in(a,b)\}] \\ &\le (1-2^{-(b-a)})\mathsf{P}(S_{b-a}\in (a,b))\le (1-2^{-(b-a)})^2, \\[1em] &\ldots \end{align}
• hello, how do you come up with the (considering the last paragraph, where you replace $1$ by $2$), the second equality and third inequality. For now I know : $$E( X 1_{Y=k} ) = E ( X | Y = k ) P(Y = k)$$ do you use something similar to this? – Marine Galantin Oct 15 at 12:24
• (1) For random variables $X$ and $Y$, $\mathsf{E}[Yf(X)]=\mathsf{E}[\mathsf{E}[Yf(X)\mid X]]=\mathsf{E}[\mathsf{E}[Y\mid X]f(X)]$, where $f$ is any measurable function satisfying $\mathsf{E}|Yf(X)|<\infty$. Now set $Y=1\{\tau>2(b-a)\}$, $X=S_{b-a}$, and $f(x)=1\{x\in(a,b)\}$. – d.k.o. 2 days ago
• (2) The third inequality uses the Markov property, i.e. for $x\in (a,b)$, $$\mathsf{P}(S_{b-a}+(S_{2(b-a)}-S_{b-a})\in (a,b)\mid S_{b-a}=x)=\mathsf{P}(x+S_{b-a}\in(a,b))$$ because conditionally on $S_{b-a}$, $(S_{(b-a)+n}-S_{b-a})$, $n\ge 0$, is a random walk started at $0$. Consequently, we use the first inequality to bound the RHS, i.e. $\mathsf{P}(x+S_{b-a}\in(a,b))\le 1-2^{-(b-a)}$. – d.k.o. 2 days ago
• No. $x$ in the second line doesn't make sense. – d.k.o. 2 days ago
• @MarineGalantin Let $\phi(x):=\mathsf{P}(x+S_{b-a}\in (a,b))$. Then \begin{align} &\mathsf{E}[\mathsf{P}(S_{b-a}+(S_{2(b-a)}-S_{b-a})\in (a,b)\mid S_{b-a})1\{S_{b-a}\in(a,b)\}] \\ &\qquad=\mathsf{E}[\phi(S_{b-a})1\{S_{b-a}\in(a,b)\}]\le \mathsf{E}[(1-2^{(b-a)})1\{S_{b-a}\in(a,b)\}] \\ &\qquad=(1-2^{(b-a)})\phi(0)\le (1-2^{(b-a)})^2. \end{align} – d.k.o. yesterday