# Proof of optimal exercise time theorem for American derivative security in N-period binomial asset-pricing model

At least two textbooks (Shreve's Stochastic Calculus for Finance - I, theorem 4.4.5 or Campolieti & Makarov's Financial Mathematics, proposition 7.8) prove the optimal exercise theorem that says that the stopping time $\tau^* = min \{n; V_n = G_n\}$ maximizes $$V_n = \max_{\tau \in S_n} \tilde{\mathrm{E}}\Big[\mathrm{I}_{\tau \leq N}\frac{1}{(1+r)^{\tau-n}}G_{\tau}\Big] \qquad (1)$$ by demonstrating that stopped process $\frac{1}{(1+r)^{n \wedge \tau^*}}V_{n \wedge \tau^*}$ is a martingale under the risk-neutral probability measure.

But how can someone conclude from this fact that $\tau^*$ is actually maximizing the right-side of $(1)$?

• You need the optional sampling theorem for that – Ami44 Aug 14 '16 at 22:33
• As much as I understand the optional sampling theorem says for example that a stopped supermartingale is still a supermartingale, but does not say anything about the relationship between two stopped processes with different stopping times. So I don't understand how it can be used to prove that $\tau^*$ is maximizing $(1)$ above – zer0hedge Aug 15 '16 at 7:25

I think the proof has already been provided at the end of the proof in Shreve's Theorem 4.4.5. Specifically, note that, since \begin{align*} \frac{1}{(1+r)^{n \wedge \tau^*}}V_{n \wedge \tau^*}. \end{align*} is a martingale, \begin{align*} \tilde{\mathbb{E}}\left(\frac{1}{(1+r)^{N \wedge \tau^*}}V_{N \wedge \tau^*}\right) &= V_0 = \max_{\tau \in S_0} \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau \leq N\}}\frac{1}{(1+r)^{\tau}}G_{\tau}\right).\tag{1} \end{align*} On the other hand, \begin{align*} &\ \tilde{\mathbb{E}}\left(\frac{1}{(1+r)^{N \wedge \tau^*}}V_{N \wedge \tau^*}\right) \\ =&\ \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau^* \leq N\}} \frac{1}{(1+r)^{\tau^*}}V_{\tau^*}\right) + \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau^* =\infty\}} \frac{1}{(1+r)^N}V_N\right)\\ =&\ \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau^* \leq N\}} \frac{1}{(1+r)^{\tau^*}}V_{\tau^*}\right),\tag{2} \end{align*} as, on $(\tau^* =\infty)$, $V_N=0$. Combining $(1)$ and $(2)$, we conclude that \begin{align*} \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau^* \leq N\}} \frac{1}{(1+r)^{\tau^*}}V_{\tau^*}\right) = \max_{\tau \in S_0} \tilde{\mathbb{E}}\left(\mathbb{I}_{\{\tau \leq N\}}\frac{1}{(1+r)^{\tau}}G_{\tau}\right), \end{align*} that is, the maximum is achieved at $\tau^*$.

A year ago, I was not able to understand the following.

First Shreve defines $V_n$ as follows:

Definition 4.4.1. For each $n, n = 0,1,\cdots, N$, let $G_n$ be a random variable depending on the first $n$ coin tosses. An American derivative security with intrinsic value process $G_n$ is a contract that can be exercised at any time prior to and including time $N$ and, if exercised at time $n$, pays off $G_n$. We define the price process $V_n$ for this contract by the American risk-neutral pricing formula $$V_n= \max_{\tau \in \mathcal{S}_n} \widetilde{\mathbb{E}}_n\Big[\mathbb{I}_{\{\tau \leq N\}}\frac{G_\tau}{(1+r)^{\tau-n}} \Big], \: n = 0, 1, \cdots, N$$

Then important properties of $V_n$ (as defined above!) are proved in

Theorem 4.4.2. The American derivative security price process given by Definition 4.4.1 has the following properties:

(i) $V_n \geq \max\{G_n, 0\}$ for all $n$

(ii) The discounted process $\frac{V_n}{(1+r)^n}$ is a supermartingale

(iii) if $Y_n$ is another process satisfying $Y_n \geq \max\{G_n, 0\}$ for all $n$ and for which $\frac{Y_n}{(1+r)^n}$ is a supermartingale then $Y_n \geq V_n$ for all $n$

We summarize property (iii) by saying that $V_n$ is the smallest process satisfying (i) and (ii)

Then, in the theorem 4.4.3 Shereve redefines $V_n$ as a Snell envelope process (though Shreve does not use this term):

Theorem 4.4.3. We have the following pricing alogrithm for the path-dependent derivative security price process given by Definition 4.4.1:

$V_N(\omega_1 \cdots \omega_N) = \max{\{G_N, 0\}}$

$V_n(\omega_1 \cdots \omega_n) = \max\{ G_n(\omega_1 \cdots \omega_n), \frac{1}{1+r}[\tilde{p}V_{n+1}(\omega_1 \cdots \omega_nH) + \tilde{q}V_{n+1}(\omega_1 \cdots \omega_nT)]$

Shreve proves theorem showing that the redefined $V_n$ satisfies conditions of Theorem 4.4.2. and concludes that $$V_n = \max\{ G_n, \frac{1}{1+r}[\tilde{p}V_{n+1} + \tilde{q}V_{n+1}]\} = \max_{\tau \in \mathcal{S}_n} \widetilde{\mathbb{E}}_n\Big[\mathbb{I}_{\{\tau \leq N\}}\frac{G_\tau}{(1+r)^{\tau-n}} \Big] \tag{A}\label{A}$$

From now on Shreve uses the redefined $V_n$. The optimal exercise time is defined in

Theorem 4.4.5. The stopping time $$\tau^* = \min\{n; G_n = V_n\}$$ maximizes the righ-hand side of (4.4.1) when $n=0$; i.e. $$V_0 = \widetilde{\mathbb{E}}\Big[\mathbb{I}_{\{\tau^* \leq N\}}\frac{G_{\tau^*}}{(1+r)^{\tau^*}} \Big]$$

He proves that the stopped redefined $V_n$ is a martingale: $$V_{n\wedge \tau^*} = \mathbb{E}_n\frac{V_{n+1\wedge \tau^*}}{1+r} \tag{B}\label{B}$$

From $\eqref{A}$ we conclude: $$V_0 = \max_{\tau \in \mathcal{S}_0} \widetilde{\mathbb{E}}\Big[\mathbb{I}_{\{\tau \leq N\}}\frac{G_{\tau}}{(1+r)^{\tau-n}} \Big]$$

From $\eqref{B}$ we conclude: $$V_0 = V_{0 \wedge \tau^*} = \mathbb{E}\frac{V_{N\wedge \tau^*}}{{1+r}^{N\wedge\tau^*}}$$

so the reminder of the Shreve's proof should be clear now.

For another proof of the optimal exercise theorem and in general better explanation of the topic I highly recommend Musiela & Rutkowski's "Martingale Methods in Financial Modelling" referenced by @Gordon on many occasions.

For simplicity I assume all discount factors to be 1. $$V_{n}=E\left (G_{{\tau}'_{n}} \mid \mathscr{F}_{n} \right ) \: \text{with} \: {\tau}'_{n} \in S_{n} \: \text{maximizing} \: V_{n}$$ We define $$\tau^{\ast}_{n} = \min \left \{ m \geq n: V_{m} = G_{m} \right \}$$

We seek a proof that $\tau^{\ast}_{n}$ is a valid choice for ${\tau}'_{n}$. It's enough to prove that for n = 0, i.e. that it is possible to set $${\tau}'_{0} = \tau^{\ast}_{0}$$

The fact that the stopped process $V_{n\wedge \tau^{\ast}_{0}}$ is a martingale is not enough to prove the claim. E.g. $\tau^{\ast}_{0} = 0$ would cause the stopped process to be a martingale too, but would most probably not maximize $V_{n}$.

In fact I would not use the stopped process at all, but would rather prove the claim like this:

It seems clear, that the ${\tau}'_{n} \in S_{n}$ that maximizes $E\left(G_{\tau}\mid \mathscr{F}_{n} \right )$ also maximizes $E\left(G_{\tau}\mid \mathscr{F}_{0} \right )$ as long as we keep restricting ourselves to $S_{n}$.

From that we can conclude that ${\tau}'_{0} = n$ implies ${\tau}'_{n} = n$ and that leads to $${\tau}'_{0} = n \:\Rightarrow\: V_{n} = G_{n}$$ because ${\tau}'_{0} = n \:\Rightarrow\: {\tau}'_{n} = n$ and on the set $\left\{{\tau}'_{n} = n\right\}$ is $G_{{\tau}'_{n}}=G_{n}$ which is $\mathscr{F}_{n}$-measurable so that on this set holds: $$V_{n} = E\left (G_{{\tau}'_{n}} \mid \mathscr{F}_{n} \right ) = E\left (G_{n} \mid \mathscr{F}_{n} \right ) = G_{n}$$

Now we know, that $\left \{ {\tau}'_{0} = n\right \}$ and $\left \{ \tau^{\ast}_{0} = n\right \}$ are both a subset of $\left \{ V_{n} = G_{n} \right \}$. What is left is to prove, that choosing the minimal $n$ in the definition of ${\tau}'_{0}$ works.

We know that $V_{n}$ is a supermartingal: $$V_{n} = \max_{\tau \in S_{n}} E\left(G_{\tau}\mid\mathscr{F}_{n} \right)\geq \max_{\tau \in S_{m}} E\left(G_{\tau}\mid\mathscr{F}_{n} \right) \\ = E\left(\max_{\tau \in S_{m}} E\left(G_{\tau}\mid\mathscr{F}_{m} \right) \:\mid \mathscr{F}_{n}\right) = E\left(V_{m}\mid\mathscr{F}_{n}\right) \;for \: m \gt n$$ The inequality stems from the fact, that $S_{n} \supseteq S_{m}$ for $\: m \gt n$.

Lets assume we have $\tau^{\ast}_{n} = \min \left \{ m \geq n: V_{m} = G_{m} \right \}$ and another stopping time $\tau_{1}$ with $V_{n} = G_{n}$ if $\tau_{1}=n$ and $\tau_{1}\geq\tau^{\ast}_{0}$ We use the optional sampling theorem on the supermartingal $V_{n}$ $$V_{\tau^{\ast}_{0}}\geq E\left(V_{\tau_{1}}\mid\mathscr{F}_{\tau^{\ast}_{0}}\right)$$ $$\Rightarrow\: E\left(V_{\tau^{\ast}_{0}}\mid\mathscr{F}_{0}\right)\geq E\left(V_{\tau_{1}}\mid\mathscr{F}_{0}\right)$$ $$\Rightarrow\: E\left(G_{\tau^{\ast}_{0}}\mid\mathscr{F}_{0}\right)\geq E\left(G_{\tau_{1}}\mid\mathscr{F}_{0}\right)$$

which means that indeed $\tau^{\ast}_{0}$ and not $\tau_{1}$ maximizes $E\left(G_{\tau^{\ast}_{0}}\mid\mathscr{F}_{0}\right)$

Q.E.D.

• For me it doesn't seem clear, that the ${\tau}'_{n} \in S_{n}$ that maximizes $E\left(G_{\tau}\mid \mathscr{F}_{n} \right )$ also maximizes $E\left(G_{\tau}\mid \mathscr{F}_{0} \right )$ as long as we keep restricting ourselves to $S_{n}$ since ${\tau}'_{n} = {\tau}'_{n}(\omega_1, \cdots, \omega_n)$. I.e. there are plenty different ${\tau}'_{n} \in S_{n}$ while there is only one ${\tau}'_{0}$ – zer0hedge Aug 22 '16 at 13:44
• ${\tau}'_{0}$ is in $S_{0}$ and thus probably not element of $S_{n}$, so it is irrelevant here. What I meant is, that maximizing over all $\tau \in S_{n}$ the same ${\tau}'_{n}$ maximizes $E\left( G_\tau \mid \mathscr{F}_{n} \right)$ and $E\left( G_\tau \mid \mathscr{F}_{0} \right)$. Does that make it clearer? – Ami44 Aug 22 '16 at 19:13
• Also I think you are implying with ${\tau}'_{n}={\tau}'_{n}(\omega_{1}, ..., \omega_{n})$ that ${\tau}'_{n}$ is $\mathscr{F}_{n}$-measurable. But that is not the case. Only the set ${\tau}'_{n} \leq n$ is. – Ami44 Aug 22 '16 at 22:41
• I'm probably confused with the notation used. Do I understand correctly that $\tau_n$ refers to the set of stopping times $\tau \in S_n$? Then $\tau_0 \in S_n$ is nothing else but stopping times which are in $\tau_n$! Where am I wrong? – zer0hedge Aug 24 '16 at 13:45
• $S_{n}$ is the set of stopping times $\tau$ with $\tau (\omega) \geq n$ being true for all $\omega$. From that it follows that $S_{n} \subset S_{0}$. In my notation are the stopping times ${\tau}'_{n}$ and $\tau^{\ast}_{n}$ both elements of $S_{n}$ and thus also elements of $S_{0}$. But while ${\tau}'_{0}$ is element of $S_{0}$ it is not necessarily element of $S_{n}$. – Ami44 Aug 24 '16 at 18:22