# How to calculate the probability at a stopping time?

Let $\{X_n:n\geq 1\}$ be a sequence of iid random variables with distribution: $P(X_1 = 1) = \frac{2}{3},P(X_1 = -1) = \frac{1}{3}$.

Let $S_0 = 0$ and $S_n = X_1 + X_2 + \dots+X_n$. Let $\tau=\inf\{n\geq0:|S_n|=M\}$ for some integer $M>0$. Calculate $P(S_\tau = M)$

• Presumably all the random variables have the same distribution. You did not specify any after the first. – Ross Millikan Dec 22 '17 at 20:29
• @RossMillikan The question says they are iid. – B. Mehta Dec 22 '17 at 20:30

Let $\mathbb{P}(X =1) = p$. Note that $R_n = \left(\dfrac{1-p}{p}\right)^{S_n} = 2^{-S_n}$ is a martingale. Using the martingale optional stopping theorem, $$\mathbb{E}[R_\tau] = \mathbb{E}[R_0]=1$$$$\Rightarrow \mathbb{P}(S_\tau = M)2^{-M} + [1-\mathbb{P}(S_\tau = M)]2^M = 1 \Rightarrow \mathbb{P}(S_\tau = M) = \frac{2^M-1}{2^M - 2^{-M}}$$
• In $[1-\mathbb{P}(S_\tau=M)]2^M$, why $2^M$? I understand the first part which is $2^{-M}$ times the probability of $S_\tau=M$. The second is something times the probability when $S_\tau$ is not $M$, but why $2^M$? – Jango Dec 24 '17 at 4:15
• @Jango At $\tau$, $S_n = \pm M$. $2^M$ is the value of the martingale if $S_\tau = -M$, and $[1-\mathbb{P}(S_\tau = M)] = \mathbb{P}(S_\tau = -M)$ is the corresponding probability. – ChargeShivers Dec 24 '17 at 14:22
• At $\tau$, if $S_\tau$ is not $M$, $S_\tau$ can be $M-1$, $M-2$, why it has to be $-M$? In another words, at $\tau$, why $S$ has only two possible values $\pm M$? – Jango Dec 24 '17 at 18:57
• @Jango See your definition of $\tau$. – ChargeShivers Dec 24 '17 at 19:02
Hint: $\tau$ is the first time you have a sum of $M$. As $M \gt 0$ you will get to $M$ with probability $1$.