2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

First, $a<0<b$ 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}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Marine Galantin Oct 15 at 12:24
  • 1
    $\begingroup$ (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)\}$. $\endgroup$ – d.k.o. 2 days ago
  • 1
    $\begingroup$ (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)}$. $\endgroup$ – d.k.o. 2 days ago
  • 1
    $\begingroup$ No. $x$ in the second line doesn't make sense. $\endgroup$ – d.k.o. 2 days ago
  • 1
    $\begingroup$ @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} $\endgroup$ – d.k.o. yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.