Suppose we have a simple random walk starting from $S_0=0$, and $S_n=X_1+\dots+X_n$ such that $$\mathbb{P}(X_i=1)=p \hspace{1em}\mathbb{P}(X_i=0)=r \hspace{1em} \mathbb{P}(X_i=-1)=q$$ for positive $p,q$ and $r$ with $p+q+r=1$ and suppose $p \neq q$. For any integer $x$, let $T_x = \text{min}\{n \geq 1: S_n = x\}$ be the stopping time that is the first time the random walk hits $x$.
For $a<0<b$, I want to use Doob's Optional Stopping Theorem to compute both $\mathbb{P}(T_a < T_b)$ and $\mathbb{P}(T_b < T_a)$. That is, the probability that the random walk hits $a$ in less moves than it takes to hit $b$, and vice-versa.
My understanding of this Theorem is not the best and I think that the general idea is to find one of the conditions in the theorem to be satisfied, to then deduce that the expected value of the stopped process is equal to the initial value of our martingale. I am not sure where I would go from here so I would appreciate any hints please!
Best Answer
We find a martingale that will make things work out. Define $S_n=X_1+...+X_n$, we define $(c^{S_n})_{n \in \mathbb{N}}$ and find $c$ which makes the process a martingale; since the jumps are bounded, $c^{S_n}$ is bounded $\forall n$ thus it is integrable $\forall n$. Now $$E[c^{S_n-S_{n-1}}|\mathscr{F}_{n-1}]=pc+(1-p-q)+qc^{-1}=1\implies c=\frac{q}{p}$$ Now suppose $p>q$; then $0 < c<1$ and by strong LLN, a.s. $$S_n=n\cdot (S_n/n)\stackrel{n \to \infty}{\to}\infty \cdot \underbrace{(p-q)}_{>0}=+\infty$$ Then $b>0$ is hit a.s. by $S_n$, so that $P(T_b<\infty)=1$. So we get $P(T_a\wedge T_b<\infty)=1$: indeed $$P(T_a\wedge T_b=\infty)=P(T_a=\infty,T_b=\infty)\leq P(T_b=\infty)=0$$ and so we proceed with $$1\stackrel{\textrm{Doob's OST}}{=}E[c^{S_{n\wedge T_a\wedge T_b}}]=E[\underbrace{c^{S_{T_a\wedge T_b}}\mathbf{1}_{\{T_a\wedge T_b<n\}}}_{\to c^{S_{T_a\wedge T_b}},\textrm{ a.s.}}]+E[\underbrace{c^{S_n}\mathbf{1}_{\{T_a\wedge T_b\geq n\}}}_{\in [c^b,c^a],\to 0 \textrm{ a.s.}}]\stackrel{n \to \infty}{\to}E[c^{S_{T_a\wedge T_b}}]$$ by dominated convergence. Now we can claim: $$1=E[c^{S_{T_a\wedge T_b}}]=c^aP(T_a<T_b)+c^bP(T_b<T_a)\implies P(T_a<T_b)=\frac{1-c^b}{c^a-c^b}$$ We can proceed similarly for $q>p$.