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?

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

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – User124356
    Commented Mar 18, 2022 at 0:29
  • $\begingroup$ That is correct! :^) $\endgroup$ Commented Mar 18, 2022 at 0:32
  • $\begingroup$ 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? $\endgroup$
    – User124356
    Commented Mar 18, 2022 at 12:13
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Mar 18, 2022 at 13:15
  • $\begingroup$ @User124356 See edits. $\endgroup$ Commented Mar 18, 2022 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .