Let $(X_n)_{n\in\mathbb{N}}$ be iid with $P(X_1=1)=P(X_1=-1)=\frac{1}{2}$. Define $S_0:=0$ and $S_n:=\sum_{i=1}^nX_i$, $a,b\in\mathbb{Z}$ with $a<0<b$ and $S(a,b):=\min\{n\in\mathbb{N}:S_n\in\{a,b\}\}$.
Now I want to show by induction that $$P(S(a,b)>n(b-a))\le\bigg(1-\frac{1}{2^{b-a}}\bigg)^n$$
Can someone give me a hint?
I tried to think about $$P(S(a,b)\le(b-a))\le \frac{1}{2^{b-a}}$$
Because then it would follow
$$P(S(a,b)>(b-a))=1-P(S(a,b)\le(b-a))\le\bigg(1-\frac{1}{2^{b-a}}\bigg),$$ right? But still I don't get it...
Thanks in advance!
Update: As mentioned in the comment of the answer of E-A I could show this.
Moreover I was able to show that
$$E[S(a,b)]<\infty,$$
$$P(S(a,b)=a)=\frac{b}{b-a}.$$
Last one by using Wald's equation.
Now I shall consider $S(a):=\min\{n\in\mathbb{N}:S_n=a\}.$ By using the last result I want to show, that
$$P(S(a)<\infty)=1,\quad\text{but } E[S(a)]=\infty.$$
Also there, it may be useful to use Wald's equation. As $E[S(a)]<\infty$ is needed for Wald's equation to be true, I thought about to show this by contradiction, but I do not get how I can use $P(S(a,b)=a)=\frac{b}{b-a}$ to prove the statement.
Again thanks in advance for any hints or help!
You messed up your inequality; you need to show that $P(S(a,b) \leq (b-a)) \geq \frac{1}{2^{b-a}}$ (don't forget the minus sign!)
Think of a really bad event that can happen between rounds $0$ and $(b-a)$, such that you will definitely be out of the given interval if that event happens. That will lower bound that probability, and you can then proceed with induction.