# A question from the martingale

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?

• Have you seen other problems that use martingale methods before? If so, do any of the tricks they use help here? Commented Mar 17, 2022 at 22:40
• @user6247850 I did not use martingale method before. I am studying this topic first time. Commented Mar 17, 2022 at 22:50

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.

• I got $0 = (-3) . P(S_T =-3) +7 . P(S_T =7)$. Since, we have $P(S_T =-3) +P(S_T =7)=1$, this implies, $P(S_T =-3) = 7/10$. Is that correct? Commented Mar 18, 2022 at 0:29
• That is correct! :^) Commented Mar 18, 2022 at 0:32
• I have one last question. We can get $E[S_T]=E[S_0]$ either by using Optional stopping time theorem or by first Wald's identity. For optional stopping time theorem, how do I show that $P(T < \infty)=1$ and $T$ is a stopping time? Commented Mar 18, 2022 at 12:13
• @User124356 It would be a good idea to ask those as a separate question instead of adding on to your original question in the comments. However, to show $P(T<\infty) = 1$, you might consider showing that the probability that $P(X_k = 1 \text{ for 10 consecutive }k, i.o.)=1$. Commented Mar 18, 2022 at 13:15
• @User124356 See edits. Commented Mar 18, 2022 at 17:27