Stochastic Processes and Financial Mathematics
(part one)
8.2 The optional stopping theorem \(\msconly \)
Adaptedness, from Definition 3.3.2, captures the idea that we cannot see into the future. This leaves us with the question: as time passes, in what circumstances can we tell if an event has already occurred?
A stopping time is a random time with the property that, if we have only information from \(\mc {F}_n\) accessible to us at time \(n\), we are able to decide at any \(n\) whether or not \(T\) has already happened. It is straightforward to check that \(T\) is a stopping time if and only if \(\{T=n\}\) is \(\mc {F}_n\) measurable for all \(n\). This is left for you as exercise 8.4.
-
Example 8.2.2 Let \(S_n=\sum _{i=1}^nX_i\) be the simple symmetric random walk, with \(\P [X_i=1]=\P [X_i=-1]=\frac {1}{2}\). Let \(\mc {F}_n=\sigma (X_1,\ldots ,X_n)\). Then, for any \(a\in \N \), the time
\[T=\inf \{n\geq 0\-S_n=a\},\]
which is the first time \(S_n\) takes the value \(a\), is a stopping time. It is commonly called the ‘hitting time’ of \(a\). To see that \(T\) is a stopping time we note that
\(\seteqnumber{0}{8.}{0}\)\begin{align*} \{T\leq n\} =\{\text {for some }i\leq n\text { we have }S_i=a\} =\bigcup _{i=0}^n\{S_i=a\} =\bigcup _{i=0}^nS_i^{-1}(a) \end{align*} Since \(S_i\) is \(\mc {F}_n\) measurable for all \(i\leq n\), the above equation shows that \(\{T\leq n\}\in \mc {F}_n\).
You will have seen hitting times before – for most of you, in MAS2003 in the context of Markov chains. You might also recall that the random walk \(S_n\) can be represented as Markov chains on \(\Z \). You will probably have looked at a method for calculating expected hitting times by solving systems of linear equations. This approach is feasible if the state space of a Markov chain is finite; however \(\Z \) is infinite. In this section we look at an alternative method, based on martingales.
Recall the notation \(\wedge \) and \(\vee \) that we introduced at the start of this chapter. That is, \(\min (s,t)=s\wedge t\) and \(\max (s,t)=s\vee t\).
Proof: Note that
\[\{S\wedge T\leq n\}=\{S\leq n\}\cup \{T\leq n\}.\]
Since \(S\) and \(T\) are stopping times, both the sets on the right hand side of the above are events in the \(\sigma \)-field \(\mc {F}_n\). Hence, the event on the left hand side is also in \(\mc {F}_n\). ∎
If \(T\) is a stopping time and \(M\) is a stochastic process, we define \(M^T\) to be the process
\[M^T_n=M_{n\wedge T}.\]
Here \(a\wedge b\) denotes the minimum of \(a\) and \(b\). To be precise, this means that \(M^T_n(\omega )=M_{n\wedge T(\omega )}(\omega )\) for all \(\omega \in \Omega \). In Example 8.2.2, \(S^T\) would be the random walk \(S\) which is stopped (i.e. never moves again) when (if!) it reaches state \(a\).
Proof: Let \(C_n:=\1\{T-1\ge n\}\). Note that \(\{T-1\ge n\}=\Omega \sc \{T\le n-1\}\), so \(\{T\ge n\}\in \mc {F}_{n}\). By Lemma 2.4.2 \(C_n\in m\mc {F}_{n-1}\). That is, \((C_n)\) is an adapted process. Moreover,
\[ (C\circ M)_n = \sum _{k=1}^n \1_{k-1\le T-1} (M_k-M_{k-1}) = \sum _{k=1}^n \1_{k\le T} (M_k-M_{k-1}) = \sum _{k=1}^{n\wedge T} (M_k-M_{k-1}) = M_{T\wedge n}-M_{0}. \]
The last equality holds because the sum is telescoping (i.e. the middle terms all cancel each other out). Hence, by Theorem 7.1.1, if \(M\) is a martingale (resp. submartingale, supermartingale), \(C\circ M\) is also a martingale (resp. submartingale, supermartingale). ∎
-
Theorem 8.2.5 (Doob’s Optional Stopping Theorem) Let \(M\) be martingale (resp. submartingale, supermartingale) and let \(T\) be a stopping time. Then
\[\E [M_T]=\E [M_0]\]
(resp. \(\geq \), \(\leq \)) if any one of the following conditions hold:
-
(a) \(T\) is bounded.
-
(b) \(\P [T<\infty ]=1\) and there exists \(c\in \R \) such that \(|M_n|\leq c\) for all \(n\).
-
(c) \(\E [T]<\infty \) and there exists \(c\in \R \) such that \(|M_n-M_{n-1}|\leq c\) for all \(n\).
-
Proof: We’ll prove this for the supermartingale case. The submartingale case then follows by considering \(-M\), and the martingale case follows since martingales are both supermartingales and submartingales.
Note that
\(\seteqnumber{0}{8.}{0}\)\begin{equation} \label {eq:opt_stop_pre} \E [M_{n\wedge T}-M_0]\le 0, \end{equation}
because \(M^T\) is a supermartingale, by Lemma 8.2.4. For (a), we take \(n=\sup _\omega T(\omega )\) and the conclusion follows.
For (b), we use the dominated convergence theorem to let \(n\to \infty \) in (8.1). As \(n\to \infty \), almost surely \(n\wedge T(\omega )\) is eventually equal to \(T(\omega )\) (because \(\P [T<\infty ]=1\)), so \(M_{n\wedge T}\to M_T\) almost surely. Since \(M\) is bounded, \(M_{n\wedge T}\) and \(M_T\) are also bounded. So \(\E [M_{n\wedge T}]\to \E [M_T]\) and taking limits in (8.1) obtains \(\E [M_T-M_0]\leq 0\), which in turn implies that \(\E [M_T]\leq \E [M_0]\).
For (c), we will also use the dominated convergence theorem to let \(n\to \infty \) in (8.1), but now we need a different way to check its conditions. We observe that
\[ |M_{n\wedge T}-M_0| =\left |\sum _{k=1}^{n\wedge T} (M_k-M_{k-1}) \right | \le T\;\sup _{n\in \N } |M_n-M_{n-1}|. \]
Since \(\E [T(\sup _n |M_n-M_{n-1}|)]\leq c\E [T]<\infty \), we can use the Dominated Convergence Theorem to let \(n\to \infty \), and the results follows as in (b). ∎
These three sets of conditions (a)-(c) for the optional stopping theorem are listed on the formula sheet, in Appendix B. Sometimes none of them apply! See Remark 9.3.5 and the lemma above it for a warning example.