# Martingale: Show $p\{T<+\infty \}=1$.

Let $$(X_i)$$ i.i.d. such that $$p\{X_i=+1\}=p\{X_i=-1\}=\frac{1}{2}$$ and let $$(S_n)$$ the martingale define by $$S_0=0$$ and $$S_n= X_1+...+X_n$$. Moreover, let $$T=\begin{cases}\inf\{n\geq 0\mid S_n\in\{-a,b\}\}& \\+\infty & \text{ if there is no such } n\end{cases}$$ where $$a,b\in \mathbb N\backslash \{0\}.$$

$$T$$ is clearly a stopping time. I have to prove that $$p\{T<\infty \}=1$$. This is how I do:

$$p\{T> n\}=p\{\min_{0\leq m\leq n} S_m\geq -a+1, \max_{0\leq m\leq n}S_m\leq b-1\}.$$

I'm stuck here. Any idea for continuing ?

For $-a \leq i \leq b$ we define a "shifted" martingale by $S_n^i := i+S_n$ and set

$$T^i := \inf\{n \geq 0; S_n^i \in \{-a,b\}\}.$$

Moreover, $u(i) := \mathbb{P}(T^i< \infty)$, i.e. $u(i)$ is the probability that the the stopping time is finite if the martingale starts at $S_0^i=i$. It follows directly from the definition that

$$u(-a) = u(b) = 1. \tag{1}$$

Suppose that we start at $S_0^i = i \in \{-a+1,\ldots,b-1\}$. Then, by definition, the process moves in the next step to $i+1$ or $i-1$ with probability $\frac{1}{2}$. Consequently, we get

$$u(i) = \frac{1}{2} u(i-1) + \frac{1}{2} u(i+1). \tag{2}$$

This is equivalent to

$$\frac{1}{2} u(i) - \frac{1}{2} u(i+1) = \frac{1}{2} u(i-1) - \frac{1}{2} u(i) \iff u(i)-u(i+1) = u(i-1) - u(i).$$

By iteration, we find

$$u(i)-u(i+1) = u(i-2)-u(i-1) = \ldots = u(-a)-u(-a+1).$$

This implies

$$u(i) = \sum_{j=-a}^{i-1} (u(j+1)-u(j)) + 1 = (i-1+a) \cdot (u(a)-u(-a+1)) +1. \tag{3}$$

In particular, for $i=b$, it follows from $(1)$ that

$$u(a)-u(-a+1) \stackrel{!}{=} 0.$$

Hence, by $(3)$,

$$u(i)=1 \qquad \text{for all -a \leq i \leq b}.$$

For $i=0$ this proves the claim.

• Very last equation should say $u(i)=1$. – Ramen Jun 27 '18 at 19:29
• @Ramen You are right, thank you. – saz Jun 27 '18 at 19:44