## A brief note on the soundness of Bermudan option pricing via cubature

### November 27, 2006

Abstract
The subject of this study is an iterative Bermudan option pricing algorithm based on (high-dimensional) cubature. We show that the sequence of Bermudan prices (as functions of the underlying assets’ logarithmic start prices) resulting from the iteration is bounded and increases monotonely to the approximate perpetual Bermudan option price; the convergence is linear in the supremum norm with the discount factor being the convergence factor. Furthermore, we prove a characterisation of this approximated perpetual Bermudan price as the smallest fixed point of the iteration procedure.
When Nicolas Victoir studied “asymmetric cubature formulae with few points” [2for symmetric measures such as the Gaussian measure, the idea of (non-perpetual) Bermudan option pricing via cubature in the log-price space was born. In the following, we will discuss the soundness and convergence rate of this approach when used to price perpetual Bermudan options.
Consider a convex combination $\left({\alpha }_{1},...,{\alpha }_{m}\right)\in \left[0,1{\right]}^{d}$  (that is, ${\sum }_{k=1}^{m}{\alpha }_{k}=1$  ) and ${x}_{1},...,{x}_{m}\in {\mathbb{R}}^{d}$  . Then there is a canonical weighted arithmetic average operator $A$  associated with $\stackrel{⃗}{\alpha },\stackrel{⃗}{x}$  given by $\forall f\in {\mathbb{R}}^{\mathbb{R}}Af={\sum }_{k=1}^{m}{\alpha }_{k}f\left(\cdot -{x}_{k}\right).$  Now suppose $c\in \left(0,1\right)$  , $g,h:{\mathbb{R}}^{d}\to \mathbb{R}$  , $Ag\ge g$  , $Ah=h$  and $0\vee g\le h$  . Define an operator $\mathcal{D}$  on the cone of nonnegative measurable functions by $\mathcal{D}:f↦\left(c\cdot Af\right)\vee g.$  Since $A$  is positive and linear, thus monotone (in the sense that for all ${f}_{0}\le {f}_{1}$  , $A{f}_{0}\le A{f}_{1}$  ), it follows that $\mathcal{D}$  must be monotone as well. Furthermore, whenever $Af\ge f$  , we have that $A\mathcal{D}f\ge \mathcal{D}f$  , as the linearity and positivity of $A$  combined with our assumption on $g$  imply $A\mathcal{D}f\ge c{A}^{2}f\vee g\ge \left(c\cdot Af\right)\vee g=\mathcal{D}f.$  Finally, due to our assumptions on $h$  and $g$  , we have for all nonnegative $f\le h$  , $\mathcal{D}f\le cAh\le h.$  Summarising this, we are entitled to state
Lemma 1. Adopting the previous paragraph’s notation and setting $Q:=\left\{f\le h:Af\ge h\right\},$  we have that $\mathcal{D}:Q\to Q,$  $\mathcal{D}$  is monotone (i e order-preserving), and $A\mathcal{D}-\mathcal{D}$  is nonnegative.
This is sufficient to prove
Theorem 1. For all $n\in {\mathbb{N}}_{0}$  ,
 $\begin{array}{c}{\mathcal{D}}^{n+1}\left(g\vee 0\right)\ge {\mathcal{D}}^{n}\left(g\vee 0\right)=:{q}_{n}.\end{array}$ (1)
Furthermore, $q:={lim}_{n\to \infty }{\mathcal{D}}^{n}\left(g\vee 0\right)={sup}_{n\in {\mathbb{N}}_{0}}{\mathcal{D}}^{n}\left(g\vee 0\right)\in Q$  and $q$  is the smallest nonnegative fixed point of $\mathcal{D}$  .
• Proof.
• 1. The proof of equation ( 1 ) is a straightforward induction on $n$  where we have to use the monotonicity of $\mathcal{D}$  in the induction step.
• 2. Since $\mathcal{D}$  maps $Q$  itself, the whole sequence ${\left({\mathcal{D}}^{n}\left(g\vee 0\right)\right)}_{n\in {\mathbb{N}}_{0}}$  is bounded by $h$  . This entails $q\le h$  as well. Using the linearity of $sup$  and our previous observation that $A\mathcal{D}-\mathcal{D}\ge 0$  (Lemma  1 ), we can show  $\begin{array}{ccc}\forall y\in {\mathbb{R}}^{d}Aq\left(y\right)& =& {sup}_{n\in {\mathbb{N}}_{0}}A\left({\mathcal{D}}^{n}\left(g\vee 0\right)\right)\left(y\right)\end{array}$
 $\begin{array}{ccc}& \ge & {sup}_{n\in {\mathbb{N}}_{0}}{\mathcal{D}}^{n}\left(g\vee 0\right)\left(y\right)=q\left(y\right),\end{array}$
which means $Aq\ge g$  . As we have already seen, $q\le h$  , so $q\in Q$  .
• 3. Again, due to the linearity of $sup$  , $\mathcal{D}$  and ${sup}_{n\in {\mathbb{N}}_{0}}$  commute for bounded monotonely increasing sequences of functions. Thereby $\mathcal{D}q={sup}_{n\in {\mathbb{N}}_{0}}\mathcal{D}{\mathcal{D}}^{n}\left(g\vee 0\right)={sup}_{n\in \mathbb{N}}{\mathcal{D}}^{n}\left(g\vee 0\right)=q.$
• 4. Any nonnegative fixed point $p$  of $\mathcal{D}$  must be greater or equal $g\vee 0$  .
Therefore by the monotonicity of $sup$  and $\mathcal{D}$  , ${sup}_{n\in {\mathbb{N}}_{0}}{\mathcal{D}}^{n}p\ge {sup}_{n\in {\mathbb{N}}_{0}}{\mathcal{D}}^{n}\left(g\vee 0\right)=q.$
Lemma 2. Using the previous Theorem’s notation, we have for all $x\in {\mathbb{R}}^{d}$  and $n\in {\mathbb{N}}_{0}$  , if ${q}_{n+1}\left(x\right)=g\left(x\right)$  , then ${q}_{n}\left(x\right)=g\left(x\right)$  .
• Proof. By the monotonicity of the sequence $\left({q}_{n}{\right)}_{n\in {\mathbb{N}}_{0}}$  (Theorem  1 ), we have $g\left(x\right)\le {q}_{0}\left(x\right)\le {q}_{n}\left(x\right)\le {q}_{n+1}\left(x\right).$
Theorem 2. For all $n\in \mathbb{N}$  , ${\parallel {q}_{n+1}-{q}_{n}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}\le c\cdot {\parallel {q}_{n}-{q}_{n-1}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}.$
• Proof. The preceding Lemma  2 yields  $\begin{array}{ccc}{\parallel {q}_{n+1}-{q}_{n}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}& =& {\parallel {q}_{n+1}-{q}_{n}\parallel }_{\left\{{q}_{n+1}>g\right\}}\end{array}$
 $\begin{array}{ccc}& =& {\parallel c\cdot A{q}_{n}-\left(\left(c\cdot A{q}_{n-1}\right)\vee g\right)\parallel }_{{C}^{0}\left(\left\{c\cdot A{q}_{n}>g\right\},\mathbb{R}\right)}\end{array}$
via the definition of ${q}_{i+1}$  as $\left(cA{q}_{i}\right)\vee g$  for $i=n$  and $i=n+1$  . But the last equality implies  $\begin{array}{ccc}{\parallel {q}_{n+1}-{q}_{n}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}& \le & {\parallel c\cdot A{q}_{n}-c\cdot A{q}_{n-1}\parallel }_{{C}^{0}\left(\left\{c\cdot A{q}_{n}>g\right\},\mathbb{R}\right)}\end{array}$
 $\begin{array}{ccc}& \le & {\parallel c\cdot A{q}_{n}-c\cdot A{q}_{n-1}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}.\end{array}$
Since $A$  is linear as well as an ${L}^{\infty }$  -contraction (and therefore a ${C}^{0}$  -contraction, too), we finally obtain ${\parallel {q}_{n+1}-{q}_{n}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}\le c{\parallel A\left({q}_{n}-{q}_{n-1}\right)\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}\le c{\parallel {q}_{n}-{q}_{n-1}\parallel }_{{C}^{0}\left({\mathbb{R}}^{d},\mathbb{R}\right)}.$
Example 1 (Bermudan put option with equidistant exercise times in $t\cdot {\mathbb{N}}_{0}$  on the weighted arithmetic average of a basket in a discrete Markov model with a discount factor $c={e}^{-rt}$  for $r>0$  ). Let ${\beta }_{1},...,{\beta }_{d}\in \left[0,1\right]$  be a convex combination and assume that $A$  is such that
 $\begin{array}{c}\forall i\in \left\{1,...,d\right\}{\sum }_{k=1}^{m}{\alpha }_{k}{e}^{-\left({x}_{k}{\right)}_{i}}=1,\end{array}$ (2)
then the functions $g:x↦K-{\sum }_{i=1}^{d}{\beta }_{i}exp\left({x}_{i}\right)$  and $h:=K$  (where $K\ge 0$  ) satisfy the equations $Ah=h$  and $Ag=g$  , respectively. Moreover, by definition $g\le h$  . Then we know that the (perpetual) Bermudan option pricing algorithm that iteratively applies $\mathcal{D}$  to the payoff function $g\vee 0$  on the $log$  -price space, will increase monotonely and will have a limit which is the smallest nonnegative fixed point of $\mathcal{D}$  . Moreover, the convergence is linear and the contraction rate can be bounded by $c$  .
The condition ( 2 ) can be achieved by a change of the time scale (which ultimately leads to different cubature points for the distribution of the asset price)
Acknowledgements. This work originates from research conducted by the author for his doctoral thesis at the University of Oxford. The author gratefully acknowledges funding from the German Academic Exchange Service (Doktorandenstipendium des Deutschen Akademischen Austauschdienstes) and helpful discussions with Professor Terry Lyons. References

1. J Stoer, R Bulirsch, Introduction to numerical analysis, 3rd ed, Texts in Applied Mathematics 12, Springer, Berlin 2002.
2. N Victoir, Asymmetric cubature formulae with few points in high dimension for symmetric measures, SIAM Journal on Numerical Analysis 42 (2004), 209 – 227.