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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.