## Martingale Theory III: Optional stopping theorem

This is a sequel to Martingale Theory II: Conditional Expectation. Our aim here is to prove the main theorems about discrete time martingales. More advanced probability texts (e.g. those on stochastic calculus) assume that these theorems are well known to the reader.

*******************************

6. Optional stopping theorem

(Basically we follow [S].) Suppose you buy a stock at time 0, and the price process $\{S_n\}$ is a martingale. Suppose that you are going to sell the stock before next year, at a future date $T$ that you may decide (i.e. $T$ is a random time). Roughly speaking, (a version of) the optional stopping theorem says that if $T$ does not contain information about the future, then no matter how you choose $T$, you will not earn money on the average, i.e. ${\mathbb{E}}(S_T) = {\mathbb{E}}(S_0)$. Similar results, sometimes called the gambling system theorems, were proved to show the impossibility of devising a “winning strategy” for typical casino games. All these are initial motivations of martingale theory.

*******************************

How to formulate a “random time that does not contain information about the future”? First, we should have a filtration $\{{\mathcal{F}}_n\}$ to represent our available information at each time. (In the above example, we may pick ${\mathcal{F}}_n = {\mathcal{F}}^0_n = \sigma(S_0, ..., S_n)$.) Then, for each time $n$, the choice $\{T = n\}$ should be decidable using the information at time $n$. In other words, we should have $\{T = n\} \in {\mathcal{F}}_n$. This motivates the following

6.1 Definition. Let $T: \Omega \rightarrow {\mathbb{N}}_0 \cup \{\infty\}$ be measurable. $T$ is a stopping time with respect to the filtration $\{{\mathcal{F}}_n\}$ if for all $n \in {\mathbb{N}}_0 = \{0, 1, 2, ...\}$, $\{T = n\} \in {\mathcal{F}}_n$. (We also write: $T$ is an ${\mathcal{F}}_n$-stopping time. Sometimes we omit the filtration if it is understood.)

If you want to practice, do:

6.2 Exercise. Prove that $T$ is a ${\mathcal{F}}_n$-stopping time if and only if $\{T \leq n\} \in {\mathcal{F}}_n$ for all $n$.

6.3 Exercise. Any $n \in {\mathbb{N}}_0$ (as a constant random variable) is a stopping time. If $T$ and $S$ are $\{{\mathcal{F}}_n\}$-stopping times, and $k \in {\mathbb{N}}$, then $T + S, \max\{T, S\}, \min\{T, S\}, T + k$ are ${\mathcal{F}}_n$-stopping times. Find an example that $T$ is a stopping time, but $T - 1$ is not.

6.4 Example. Recall the gambler’s ruin problem (see I), where $S_n = x + X_1 + ... + X_n$ and ${\mathcal{F}}_n = {\mathcal{F}}^0_n(S)$. Consider the first hit $T: \Omega \rightarrow {\mathbb{N}}_0 \cup \{\infty\}$ to $0$ or $N$:

$T(\omega) = \inf \{n \in {\mathbb{N}}_0: S_n(\omega) = 0 \text{ or } S_n(\omega) = N\}$.

For each $n$, we have the decomposition (check!)

$\{T = n\} = \bigcap_{i = 0}^{n - 1} \{S_i \in \{1, 2, .., N - 1\}\} \cap \{S_n = 0 \text{ or } N \} \in {\mathcal{F}}_n$.

This shows $T$ is (measurable and is) an ${\mathcal{F}}_n$-stopping time. $\blacksquare$

Now we prove that in Example 6.4,  ${\mathbb{P}}(T < \infty) = 1$. That is, you will leave the casino in finite time almost surely. More importantly, this implies that $S_T$ is defined everywhere on $\Omega$ except on a null set. The proof is beautiful probabilistic thinking: if something is possible, and you try it again and again, it will certainly happen (see Chapter 1 of [S]).

Proof: We partition the time set ${\mathbb{N}}_0$ into

${\mathbb{N}}_0 = \{0\} \cup \{1, ..., N\} \cup \{N+1, ..., 2N\} \cup ... = \{0\} \cup \bigcup_{k = 0}^{\infty} \{kN + 1, ..., (k+1)N\}$.

We write $\Lambda_k = \{kN + 1, ..., (k+1)N\}$. Now, observe that

$\bigcup_{k = 0}^{\infty} \{X_n = 1 \text{ for all } n \in \Lambda_k\} =: \bigcup_{k = 0}^{\infty} E_k \subset \{T < \infty\}$.

That is, the walk $S$ will certainly hit the boundary $N$ (and hence triggers $T$) if there are $N$ consecutive heads. We partition time in the above way because we now have:

The events $E_k, k = 0, 1, ...$ are independent. (Check)

Also, ${\mathbb{P}}(E_k) = (\frac{1}{2})^N > 0$. Hence, from

$\sum_{k = 0}^{\infty} {\mathbb{P}}(E_k) = \sum_{k = 0}^{\infty} (\frac{1}{2})^N = \infty$

we may conclude from the second half of Borel-Cantelli lemma that with probability 1, $E_k$ occurs infintely often, i.e.

${\mathbb{P}}(\bigcap_{k = 0}^{\infty} \bigcup_{n = k}^{\infty} E_n) = 1$.

In particular, $1 \geq {\mathbb{P}}(T < \infty) \geq {\mathbb{P}}(\bigcap_{k = 0}^{\infty} \bigcup_{n = k}^{\infty} E_n) = 1$. $\blacksquare$

*******************************

To prove the optional stopping theorem, we introduce two auxillary concepts (which are also quite important themselves).

6.5 Definition. Let $\{{\mathcal{F}}_n\}$ be a filtration on $(\Omega, {\mathcal{F}})$. A stochastic process $\{A_n\}_{n = 1}^{\infty}$ is said to be non-anticipating with respect to $\{{\mathcal{F}}_n\}$ if $A_n \in {\mathcal{F}}_{n-1}$ for all $n$.

6.6 Definition. Let $(X_n, {\mathcal{F}})$ be a martingale, and $\{A_n\}$ be a stochastic process. The martingale transform of $\{X_n\}$ by $\{A_n\}$ is the stochastic process $\{M_n\}$ defined by

$M_0 = 0$,  $M_n = A_1(X_1 - X_0) + A_2(X_2 - X_1) + ... + M_n(X_n - X_1)$.

To motivate the definition, suppose that $\{S_n\}$ is the stock price over time, and suppose you hold $A_n$ shares to stock between the time interval $[n -1, n]$. The process $\{A_n\}$ represents your strategy. Clearly, $A_n$ should depend no extra information beyond ${\mathcal{F}}_{n-1}$. So $\{A_n\}$ is non-anticipating. Your accoumated profit/loss (P&L) is then the martingale transform of $S_n$ by $A_n$. You may also think about it as a discrete time stochastic integral $M = \int A dX$.

6.7 Martingale transform theorem. If $\{X_n\}$ is a martingale and $\{A_n\}$ is non-anticipating and each $A_n$ is bounded, then the martingale transform $\{M_n\}$ is also a martingale (all with respect to a filtration $\{{\mathcal{F}}_n\}$).

Proof: Since $\{A_n\}$ is non-anticipating, it is easy to see that $\{M_n\}$ is adapted to $\{{\mathcal{F}}_n\}$. Also, since the $A_n$s are bounded, each $M_n$ is integrable. Hence, it remains to verify that ${\mathbb{E}}(M_{n+1} | {\mathcal{F}}_n) = M_n$. We have

${\mathbb{E}}(M_{n+1} | {\mathcal{F}}_n) = {\mathbb{E}}(M_n + A_{n+1}(M_{n+1} - M_n) | {\mathcal{F}}_n) = M_n + {\mathbb{E}}(A_{n+1}(M_{n+1} - M_n) | {\mathcal{F}}_n)$.

Since $A_{n+1} \in {\mathcal{F}}_n$, we may pull it out and get

${\mathbb{E}}(A_{n+1}(M_{n+1} - M_n) | {\mathcal{F}}_n) = A_{n+1} {\mathbb{E}}(M_{n+1} - M_n | {\mathcal{F}}_n) = 0$.

This shows that $\{M_n\}$ is a martingale. $\blacksquare$

6.8 Remark. There are two ways to interpret the martingale transform theorem. First, it is a gambling system theorem, stating that you cannot hope to profit in a “fair game”. (Think about $\{X_n\}$ as the stock price, and $\{A_n\}$ your strategy.) Second, it says that the class of martingale is closed under martingale transforms (or stochastic integration) by appropriate processes.  This property motivates generalization in continuous time.

*******************************

For a martingale $\{X_n\}$, we always have ${\mathbb{E}}(X_n) = {\mathbb{E}}(X_0)$. The optional stopping theorem says that we may replace $n$ by a bounded stopping time. We will prove it using the martingale transform theorem. The idea is the following. Given a stopping time $T$, we may choose a non-anticipating strategy $\{A_n\}$ that says: sell at time $T$.

6.9 Optional stopping theorem. Let $\{X_n\}$ be a martingale and $T$ be a bounded stopping time, with respect to a filtration $\{{\mathcal{F}}_n\}$. Then ${\mathbb{E}}(X_T) = {\mathbb{E}}(X_0)$.

We recall that, in general, $X_T$ is defined by $X_T(\omega) = X_{T(\omega)}(\omega) = \sum_{n = 0}^{\infty} X_n(\omega) 1_{\{T = n\}}(\omega)$ on the (measurable) set $\{T < \infty\}$.

(There are optional stopping theorems for sub/supermartingales, which we skip here.)

Proof: Let $T$ be a stopping time bounded by $N$, i.e. $T(\omega) \leq M$ for all $\omega$. For each time $n$, we let

$A_n(\omega) = 1$ if $T(\omega) > n - 1$, and $A_n(\omega) = 0$ if $T(\omega) \leq n - 1$.

In other words, $A_n = 1_{\{T > n - 1\}} = 1_{\{T \geq n\}}$. Note that, since $\{T > n - 1\} = \{T \leq n - 1\}^c \in {\mathcal{F}}_{n-1}$, $\{A_n\}$ is (bounded and) non-anticipating.

Next, we observe that the (shifted) martingale transform

$X_0 + M_n = X_0 + A_1(X_1 - X_0) + ... + A_n(X_n - X_{n-1})$

equals the stopped process $X_{T \wedge n} = X_{\min(n, T)}$. For, on the set $\{T \geq n\}$ we have

$X_0 + M_n = X_0 + 1 (X_1 - X_0) + ... + 1 (X_n - X_{n-1}) = X_n$,

while on the set $\{T < n\}$ we have

$X_0 + M_n = X_0 + 1 (X_1 - X_0) + ... + 1 (X_T - X_{T - 1}) + 0 (X_{T+1} - X_T) + ... + 0(X_n - X_{n-1}) = X_T$.

The martingale transform theorem then implies that the process $Y_n = X_{T \wedge n}$ is a martingale (verify that the shift does not matter). So ${\mathbb{E}}(Y_n) = {\mathbb{E}}(Y_0) = {\mathbb{E}}(X_0)$ for all $n$. Now since $T \leq N$, we have $Y_M = X_T$. Finally we put $n = M$ to get

${\mathbb{E}}(X_T) = {\mathbb{E}}(X_0)$.

The theorem is proved. $\blacksquare$

6.10 Remark. To see that boundedness of $T$ is necessary, consider the simple random walk $S_n$ starting at $0$ and $T = \inf\{n \geq 0: S_n = 1\}$. It can be shown that $T$ is a stopping time and is finite with probability $1$. Then $S_T = 1$ and ${\mathbb{E}}(S_T) = 1 > 0 = {\mathbb{E}}(S_0)$.

*******************************

Solution of the gambler’s ruin problem

Now we can solve the gambler’s ruin problem (see Section 1) rigorously. Recall that we would like to find ${\mathbb{P}}_x(S_T = 0)$, where $T = \inf\{n \geq 0: S_n = 0 \text{ or } N\}$. We have shown above that ${\mathbb{P}}_x(T < \infty) = 1$, hence $S_T$ is well-defined on a set with probability 1.

At first sight, the optional stopping theorem is not applicable because $T$ is obviously not bounded above ($S_n$ can go up and down, up and down, etc…). The following trick (or technique) is frequently used:

To deal with this, let $m \in {\mathbb{N}}$ be fixed. Then $T \wedge m = \min\{T, m\}$ is a bounded stopping time (see Exercise 6.3). Now we may apply the optional stopping theorem and get

${\mathbb{E}}_x(S_{T \wedge m}) = {\mathbb{E}}_x(S_0) = x$.

Now, since ${\mathbb{P}}_x(T < \infty) = 1$, almost surely we have $\lim_{m \rightarrow \infty} T \wedge m = T$. Hence $\lim_{m \rightarrow \infty} S_{T \wedge m} = S_T$ almost surely. Moreoveer, $0 \leq S_{T \wedge m} \leq N$ for all $m$. Hence by the classical bounded convergence theorem we obtain

${\mathbb{E}}_x(S_T) = \lim_{n \rightarrow \infty} {\mathbb{E}}_x(S_{T \wedge m}) = x$.

On the other hand we have, by definition of $S_T$,

${\mathbb{E}}_x(S_T) = 0 \times {\mathbb{P}}_x(S_T = 0) + (1 - {\mathbb{P}}_x(S_T = 0)) \times N$.

Combining, we have ${\mathbb{P}}_x(S_T = 0) = \frac{N - x}{N}$. $\blacksquare$

6.11 Exercise. Consider the martingale $(S_n - x)^2 - n$ and show that ${\mathbb{E}}_x(T) = x(N - x)$. What else can be calculated by martingale method?

*******************************

In the next post we will treat the martingale convergence theorems.