Suppose $X_1,\ X_2,\ldots$ are i.i.d. symmetric random variables on $\{\pm 1\}$, i.e. $\mathbb{P}(X_k = +1) =1/2$.
Define $S_n = X_1+X_2+\ldots+X_n$.
Use martingale techniques to compute $\mathbb{P}(S_n\text{ hits }-3 \text{ before hitting }+7)$; i.e. compute $\mathbb{P}( \exists n \geq 1 \text{ such that } S_n=-3 \text{ and }-2\leq S_k\leq+6\ \ \forall k=1,…,n-1)$ .
I tried to solve this by the following way:
Define $T=\inf \{n : n \geq 1 \text{ and }S_n=-3\text{ or }+7\}$, where $\inf(\emptyset) = \infty$.
Now I will show that $T$ is an extended stopping time with respect to $\{\sigma(X_1),\sigma(X_1,X_2), \ldots\}$ and that $S_1,S_2,..$ is a martingale with respect to those $\sigma$-fields.
But I have no idea how to use the martingale convergence theorem to solve this question. Can anyone help me with the solution to this question?
Best Answer
Hint: Compute $E[S_T]$ in two ways.
On the one hand, $T$ is a stopping time, and $S$ is martingale, so $E[S_T]=E[S_0]$.
On the other hand, $S_T$ is either equal to $-3$ or $7$, so we have the simple expression $E[S_T]=(-3)\cdot P(S_T=-3)+7\cdot P(S_T=7)$.
Combining these observations lets you solve for $P(S_T=-3)$.
To prove that $T$ is a stopping time, you just need to show that the event $\{T\le k\}$ is contained in $\sigma(X_1,X_2,\dots,X_k)$. This is clear, since by looking at the first $k$ values of the sequence $X_1,\dots,X_k$, you can determine whether or not the process has hit $-3$ or $7$ by that point.
Proving $E[T]<\infty$ is a bit more involved. I gave a sketch of the proof in this answer.
To show that $P(T<\infty)=1$, consider the stopped martingale $\tilde X_n=X_{\min(n, T)}$. Since $\tilde X_n$ is a bounded martingale, the martingale convergence theorem implies that the sequence $\tilde X_n$ converges with probability one. But the only way an integer valued sequence can converge is if it is eventually constant, which implies that $T$ is finite.