Optimal stopping

Sub and Super Martingales

Definition 1. Let $M$ be an adapted, integrable process.

  1. We say $M$ is a super-martingale if $\E_n M_{n+1} \leq M_n$.
  2. We say $M$ is a sub-martingale if $\E_n M_{n+1} \geq M_n$.

Proposition 2. Let $f \colon \R \to \R$ be a function, and $M$ be an adapted process such that $f(M_n)$ is integrable for every $n \in \N$.

  1. If $M$ is a martingale and $f$ is convex, then $\set{f(M_n)}_{n \in \N}$ is a sub-martingale.
  2. If $M$ is a sub-martingale and $f$ is convex and increasing, then $\set{f(M_n)}_{n \in \N}$ is a sub-martingale.

Proposition 3. Let $X$ be an adapted process and $\tau$ be a bounded stopping time.

  1. If $X$ is a super-martingale, then $\E_n X_\tau \leq X_{\tau \varmin n}$.
  2. If $X$ is a sub-martingale, then $\E_n X_\tau \geq X_{\tau \varmin n}$.

Remark 4. The above theorem can be generalized to unbounded stopping times under the same conditions stated in this remark.

The proof of Proposition 3 uses a lemma that’s more useful than the proposition itself.

Theorem 5 (Doob decomposition). Any adapted integrable process can be uniquely expressed as the sum of a martingale and a predictable process that starts at $0$. That is, if $X$ is an adapted process there exists a unique pair of process $M, A$ such that $M$ is a martingale, $A$ is predictable, $A_0 = 0$ and $X = M + A$.

Remark 6. Expressing $X = M + A$ as above is called the Doob decomposition of $X$.

Proposition 7. Let $X$ be an integrable adapted process, and $X = M + A$ be its Doob decomposition.

  1. $X$ is a super-martingale if and only if $A$ is decreasing (i.e. $A_n \geq A_{n+1}$).
  2. $X$ is a sub-martingale if and only if $A$ is increasing (i.e. $A_n \leq A_{n+1}$).

Proof of Proposition 3. If $X$ is a sub-martingale then the Doob decomposition gives $\E_n X_\tau = \E_n A_\tau + M_{\tau \varmin n} \geq A_{\tau \varmin n}$.

Definition 8. If $X$ is an adapted process (such that $X^2$ is integrable), the predictable quadratic variation of $X$ is defined by $$ \ip{X}_0 \defeq 0 \quad\text{and}\quad \ip{X}_{n+1} = \ip{X}_n + \E_n (X_{n+1} - X_n)^2 $$

Problem 9. If $M$ is a martingale such that $M^2$ is integrable, show that $\ip{M}$ is the predictable increasing process $A$ in the Doob decomposition of $M^2$.

Super-martingale envelopes and optimal stopping

Suppose $\set{X_n}$ is an adapted process representing the reward you get from playing a game. When should you stop playing to maximize your expected winnings? Here are two examples:

Example 10 (American put options). Let $\set{S_n}_{n \in \N}$ be the price of a stock at time $n$, and for simplicity suppose we can borrow / lend money without interest. An American put-option allows the holder to sell the stock at price $K$ before the maturity time $N$. When exercised at time $n$, the option will pay the holder $(K - S_n)_{+}$. What is the optimal time to exercise this option?

Example 11. A game show host has $N$ sealed envelopes. Each envelope contains some money chosen uniformly at random, up to some set maximum amount $M$. You’re shown the contents of each envelope in order, and can decide to accept it and leave or refuse it and look at the next one. Once you refuse an envelope, you can’t go back to it. What’s your strategy to accept / refuse an envelope?

Problem 12 (Optimal stopping problem). Given a time horizon $N \in \N$, and an adapted reward process $\set{X_n}_{n \leq N}$, find the stopping time $\sigma$ which maximizes $\E X_\sigma$ over all stopping times $\sigma \leq N$.

Theorem 13 (Snell). Let $N \in \N$, and let $\set{X_n}_{n \leq N}$ be an adapted reward process. Define $$ V_N = X_N \,, \quad V_n = \max \set{ E_n V_{n+1}, X_n } \,, \quad \sigma^* = \min\set{n \st X_n = V_n } \,. $$ Then $\sigma^*$ is the minimal solution to the optimal stopping problem for $X$. That is for any stopping time $\sigma \leq N$ we have $\E X_{\sigma^*} \geq \E X_\sigma$, and if $\E X_{\sigma^*} = \E X_\sigma$, then $\sigma \geq \sigma^*$.

Lemma 14. The process $V$ is the smallest super-martingale larger than $X$. That is, $V$ is a super-martingale, $V_n \geq X_n$ for every $n$, and if $W$ is any super-martingale such that $W_n \geq X_n$ for every $n$, then $W_n \geq V_n$ for every $n$.

Remark 15. The process $V$ is called the super-martingale envelope of $X$.

Lemma 16. The process $V_{\sigma^* \varmin n}$ is a martingale.

Proof sketch of Theorem 13. TODO