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_ns 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.

This entry was posted in Probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s