\documentclass[12pt,a4paper]{report}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{algorithmic}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{eepic}
\usepackage{booktabs}
\usepackage{tabularx}
\usepackage{multirow}
\usepackage{dcolumn}
\usepackage{booktabs}

%\usepackage{algorithm, algorithmic}
%\title{{\LARGE \bf This is the title }}

%\setlength{\topmargin}{-0.5 in}
%\setlength{\textwidth}{6in}
%\setlength{\oddsidemargin}{0.5in}
%\setlength{\evensidemargin}{-0.01in}
%\setlength{\textheight}{9.5in}

\title{{\Huge \bf Numerical Valuation of Discrete Barrier Options with the Adaptive Mesh Model and Other Competing Techniques}}
\author{
    \\
    \\
    \\
    \\
    \\
    \\
    \\
    \\
    Advisor: Prof. Yuh-Dauh Lyuu
    \\
    \\
    Chih-Jui Shea\\
    \\
    Department of Computer Science and Information Engineering
    \\
    National Taiwan University
    \\
    \\
}

\date{}



\normalsize
\begin{document}
\maketitle \sloppy
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{comment}[lemma]{Comment}
\newtheorem{example}[lemma]{Example}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{fact}[lemma]{Fact}
\newtheorem{defn}[lemma]{Definition}
\newenvironment{proof}{{\flushleft\textbf{\textsl{Proof.\ }}}}{\hfill $\Box$\vspace{-0.2 cm}\\}


\pagenumbering{arabic}

\begin{abstract}
This thesis develops an Adaptive Mesh Model for pricing discrete
double barrier options. Adaptive Mesh Model is a kind of trinomial
tree lattice that applying higher resolution to where nonlinearity
errors occur. After the Adaptive Mesh Model for discrete single
barrier options was proposed in 1999 by Ahn, Figlewski, and Gao,
there is no further research has been done in Adaptive Mesh Model
for discrete barriers. Furthermore, numerical data are also scarce
in the paper of Ahn et al.. This thesis bases on the lattice
structure of Ahn et al. and extends the Adaptive Mesh Model to
price discrete double barrier options. Besides, there is no
close-form solution for discrete barrier options such that many
methods have been suggested and declared to price discrete barrier
options fast and accurately but no one can tell exactly that what
method is the best. We also make a complete comparisons of the
Adaptive Mesh Model with other methods no matter in accuracy or in
efficiency. Our numerical data shows that the Adaptive Mesh Model
is generally surpassed the other tree lattice methods and the BGK
formula approach, and exceed the quadrature method in efficiency
with accurate enough outcomes. \vspace*{0.5cm}

\noindent {\bf Keywords:} Adaptive Mesh, numerical valuation
techniques, discrete barrier options, double barrier options,
trinomial trees, enhanced trinomial trees, BGK model, quadrature
method, option pricing
\end{abstract}

\pagebreak

\tableofcontents \listoffigures \listoftables

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}
% <-- not finish
\par
Barrier options have become more and more popular. They are not
only desirable in speculation but also in risk management because
of lower costs than their plain vanilla counterparts. The typical
analytic pricing formulas for single barrier options are derived
assuming continuously monitoring of the barrier. However, in real
market barrier conditions of options are generally monitored
discretely but there is no close-form solution. Many numerical
methods have been proposed to price discrete monitored barrier
options including the Adaptive Mesh Model. Since the Adaptive Mesh
Model for pricing discrete single barrier options is first
proposed in 1999 \cite{Figlewski(1999b)}, the concept of adaptive
mesh has been widely discussed but further research is absence.
Also, numerical results of the Adaptive Mesh Model is rare in the
original paper. Hence, in this thesis we do not only implement the
Adaptive Mesh Model of Ahn et al. but also extend it to price
discrete double barrier options. Besides, we compare the Adaptive
Mesh Model to other competing methods with extensive numerical
data both in efficiency and accuracy.
\par
In Chapter 1 and Chapter 2, we shortly set the background and the
concept of barrier options. Chapter 3 introduces the Adaptive Mesh
Model starting from two kinds of approximation errors (i.e.
distribution error and nonlinearity error) generally existing in
lattice models and then using Adaptive Mesh Model to ease the
nonlinearity error in both European and American puts. In the
latter part of Chapter 3, we propose the Adaptive Mesh Model for
pricing not only single but also discrete double barrier options.
At Last in Chapter 4 we compare the Adaptive Mesh with other
competing methods in pricing discrete barrier options numerically
and end up with the conclusions in Chapter 5.
\par

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Barrier Options}
\section{Barrier Option Basics}

A barrier option is a kind of path-dependent options that comes
into existence or is terminated depending on whether the
underlying asset's price $S$ reaches a certain price level $H$
called "barrier". A knock-out option ceases to exist if the
underlying asset reaches the barrier, whereas a knock-in option is
activated if the barrier is reached by underlying asset. According
to the relative position of $H$ and $S$, there are four kinds of
typical barrier, which are outlined below.
\begin{enumerate}
    \item Down and Out: knock-out options with $H<S$.
    \item Down and In: knock-in options with $H<S$.
    \item Up and Out: knock-out options with $H>S$.
    \item Up and In: knock-in options with $H>S$.
\end{enumerate}
\par
Besides, based on how frequently the barrier condition is checked,
one barrier can be continuous or discrete. Once a continuously
monitored barrier is reached the option is immediately knocked in
or out, while in discretely monitored conditions, barriers only
come into effect in those monitored time, e.g. close of every
market day, every quarter, every month, or every half year.

\par
Barrier options have become quite popular especially in the
foreign exchange markets. One of the barrier option's advantage is
its cheaper price. Take a down-and-out barrier call option for
example, a trader with a bull perspective view on the market may
regard the condition of the barrier being reached as quite
unlikely and be more interested in it than the regular one. Or a
hedger may buy a barrier contract to hedge a position with a
natural barrier, e.g. the foreign currency exposure on a deal that
will take place only if the exchange rate remains above a certain
level.
\section{Pricing of Barrier Options}
Barrier options were first traded on the OTC market in the late
60s, but the first analytical formula for a down and out call
option was proposed by Merton (1973) \cite{Merton(1973)} which was
followed by the more detailed paper by Reiner \& Rubinstein (1991)
\cite{Reiner(1991)} providing the formulas for all 4 types of
barrier on both call and put options. However, the analytic
formulas mentioned above only present methods to price barrier
options in continuous time, but often in the market, the asset
price is discretely monitored. In other words, they specify fixed
times for monitored of the barrier.
\par
Although discretely monitored barrier options are popular and
important, pricing them is not as easy as their continuous
counterparts. There is essentially no closed solution, except
using m-dimensional normal distribution function ($m$ is the
number of monitored points), which can hardly be computed easily
if, for example, $m>5$ ( see Reiner (2000) \cite{Reiner(2000)} and
closed-form valuation equations for discrete barrier options in
Heynen and Kat (1996) \cite{Heynen(1996)}). When it comes to
Direct Monte Carlo simulation, it takes too much time to produce
accurate enough results.
\par
To deal with these difficulties, Broadie, Glasserman and Kou
(1997) propose a continuity correction for discretely monitored
barrier options, and justify the correction both theoretically and
numerically. They adjust the barrier in the closed-form equations
of continuous barrier options to account for discrete sampling as
follows:
\[
H'=He^{\alpha\sigma\sqrt{\frac{T}{m}}}
\]
\par
It is so-called BGK barrier adjustment model. For up-barrier
options, the value of $\alpha$ is $0.52826$, whereas for
down-barrier options, the value of $\alpha$ is $-0.5826$, where
$m$ is the number of times the underlying asset price is monitored
over the time period $T$ \cite{Broadie(1997)}.
\par
Like most other path-dependent models, barrier options can be
priced by tree lattice techniques such as binomial or trinomial by
solving the PDE using a generalized finite difference method.
However, even in continuously monitored barrier options the
convergence of lattice approach is very slow and require a quite
large number of time steps to obtain a reasonably accurate result.
It is because the barrier being assumed by the tree is different
from the true barrier. Define the inner barrier as the barrier
formed by nodes just on the inside of the true barrier and the
outer barrier as the barrier formed by nodes just outside the true
barrier. Fig.~\ref{fig.barrier} shows the inner and outer barrier
for a binomial and trinomial tree when the true barrier is
horizontal and constantly monitored. The usual tree calculations
implicitly assume the outer barrier is the true barrier because
the barrier condition is first met on the outer barrier.



\setlength{\unitlength}{.018in}
\begin{figure}[htb]
\begin{center}
{
\begin{picture}(260,165)
\filltype{black}

%% binomial lattice
\put(-15,65){\circle*{4}} \multiput(15,80)(0,-30){2}{\circle*{4}}
\multiput(45,95)(0,-30){3}{\circle*{4}}
\multiput(75,110)(0,-30){4}{\circle*{4}}
\multiput(105,125)(0,-30){5}{\circle*{4}}

\put(-15,65){\line(2,1){30}}\put(-15,65){\line(2,-1){30}}

\multiput(15,80)(0,-30){2}{\line(2,1){30}}\multiput(15,80)(0,-30){2}{\line(2,-1){30}}
\multiput(45,95)(0,-30){3}{\line(2,1){30}}\multiput(45,95)(0,-30){3}{\line(2,-1){30}}
\multiput(75,110)(0,-30){4}{\line(2,1){30}}\multiput(75,110)(0,-30){4}{\line(2,-1){30}}

\linethickness{.02in}\qbezier(15,80)(17,79)(45,65)
\qbezier(45,65)(47,66)(75,80) \qbezier(75,80)(73,79)(105,65)


\qbezier(45,95)(47,96)(75,110) \qbezier(75,110)(77,109)(105,95)
\thinlines \put(5,88){\linethickness{.02in}\line(1,0){110}}

\put(50,105){\vector(0,-1){5}}
\put(30,105){\makebox(30,10){\scriptsize Outer barrier}}

\put(13,94){\vector(0,-1){5}}
\put(-2,94){\makebox(30,10){\scriptsize True barrier}}

\put(20,71){\vector(0,1){5}}
\put(0,61){\makebox(30,10){\scriptsize Inner barrier}}

\put(45,0){\makebox(0,0){$\text{(a)}$}}

%% trinomial lattice
\thinlines \put(150,65){\circle*{4}}
\multiput(190,85)(0,-20){3}{\circle*{4}}
\multiput(230,105)(0,-20){5}{\circle*{4}}
\multiput(270,125)(0,-20){7}{\circle*{4}}

\put(150,65){\line(2,1){40}}\put(150,65){\line(1,0){40}}\put(150,65){\line(2,-1){40}}
\multiput(190,85)(0,-20){3}{\line(2,1){40}}\multiput(190,85)(0,-20){3}{\line(1,0){40}}\multiput(190,85)(0,-20){3}{\line(2,-1){40}}
\multiput(230,105)(0,-20){5}{\line(2,1){40}}\multiput(230,105)(0,-20){5}{\line(1,0){40}}\multiput(230,105)(0,-20){5}{\line(2,-1){40}}

\put(170,85){\linethickness{.02in}\line(1,0){105}}
\put(175,80){\vector(0,1){4}}
\put(170,90){\linethickness{.02in}\line(1,0){105}}
\put(175,97){\vector(0,-1){6}}
\put(200,105){\linethickness{.02in}\line(1,0){75}}
\put(205,112){\vector(0,-1){6}}

\put(165,80){\line(1,0){10}}\put(130,75){\makebox(30,10){\scriptsize
Inner barrier}} \put(165,95){\makebox(30,10){\scriptsize True
barrier}} \put(195,110){\makebox(30,10){\scriptsize Outer
barrier}}

\put(210,0){\makebox(0,0){$\text{(b)}$}}
\end{picture}
}
\end{center}
\caption[{\mdseries Barrier assumed by tree
lattice.}]{\label{fig.barrier}{\bf Barrier assumed by tree
lattice}}(a) Barriers assumed by binomial trees. (b) Barriers
assumed by trinomial trees.
\end{figure}


\par
 Bolye and Lau \cite{Boyle(1994)}
describe this condition and propose a method to constrain the time
steps that make the true barrier coincide with or occur just above
 the underlying asset price level in trees. Nevertheless, the
time step constraint makes the lattice impracticable to compute
because of the incredible large number of time steps when the
initial asset price is too close to the barrier. On the other
hand, the constraint of time step number is also annoying. In
1995, Derman et al. propose an adjusting for nodes not lying on
barriers by assuming the barrier calculated by the tree is
incorrect\cite{Derman(1995)}. Ritchken (1995)
\cite{Ritchken(1995)} offers another approach under trinomial
framework introducing a "stretch" parameter into the lattice,
which changes the price step just enough to place nodes on the
barrier. Cheuk and Vorst \cite{Cheuk(1995)} also introduce a
deformation of the trinomial tree permitting one to adjust the
location of nodes differently in each time period, and allows
great flexibility in matching a time-varying barrier. Although
those methods have been proposed, a quite slow convergence rate
still occur when they are used to price discretely monitored
barrier options.
\par
For pricing discrete barrier options, Wei (1998) \cite{Wei(1998)}
offers an approximation approach based on interpolating between
the formula for a barrier option with the highest number of
monitored points that can be handled with the analytic formula and
the continuous case (infinite monitored dates). Broadie,
Glasserman and Kou (1999) develop the \emph{enhanced trinomial
model} from Ritchken's lattice framework. Like their earlier paper
in 1997 \cite{Broadie(1997)}, they shift the discrete barrier at
level $H$ to a new barrier at level $H' =
He^{\pm0.5\lambda^{*}\sigma\sqrt{h}}$ (with + for an up option and
- for a down option), where $\lambda^{*}\triangleq\sqrt{3/2}$ and
$h$ is the size of one time step \cite{Broadie(1999)}. Both these
techniques, however, can be used only for European options, and in
Broadie et al.'s model, the "barrier-too-close" problem still
exists.
\par
Figlewski and Gao (1999) \cite{Figlewski(1999a)} present the
adaptive mesh model (AMM) as an efficient trinomial lattice
approach to deal with "barrier-too-close" problem in continuous
barrier options. Furthermore, in the same year, an another kind of
adaptive mesh model is proposed for pricing discrete barrier
options by Ahn, Flglewski, and Gao \cite{Figlewski(1999b)}. The
AMM model is very powerful in both efficiency and flexibility and
is going to be discussed further in this thesis.
\par
Besides, there is the quadrature method presented by Andricopoulos
et al. (2003) \cite{Andricopoulos(2003)} using somewhat
multinomial-like integral method to price discrete barrier options
with speed and accuracy which can also deal with barrier-too-close
problem. We will numerically compare it with the AMM model later.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{The Adaptive Mesh Model}
\section{Approximation Error in Lattice Models}
Although lattice models provide powerful, intuitive and
asymptotically exact approximations to the theoretical option
values under Black-Scholes assumptions, there are essentially two
related but distinct kinds of approximation errors in any pricing
techniques of lattice framework, which we refer to as distribution
error and nonlinearity error, where the latter can be minimized by
the adaptive mesh model with slight computation increase.

\begin{enumerate}
    \item \textbf{Distribution error}: The lattice model approximates
    the true asset price distribution with continuous lognormal
    density by a finite set of nodes with probabilities. Even though the mean
    and variance of the continuous distribution are matched by the
    discrete distribution of lattice model, the
    discrepancy between discrete and continuous distribution still
    produces distribution error in option value.
    \item \textbf{Nonlinearity error}: The finite set of nodes
    with probabilities used by lattice model can be thought as a
    set of probability weighted average option price over a range
    of the continuous price space around the node. If the
    option payoff function is highly nonlinear, evaluating the
    nonlinear region with only one or several nodes would gives a
    poor approximation to the average value over the whole
    interval.
\end{enumerate}

\begin{figure}[h]
%\centerline{\psfig{figure=approxi_error.eps,bbllx=20pt,bblly=200pt,height=500pt}}
\begin{center}
\includegraphics{approxi_error.eps}
\caption[{Distribution error and nonlinearity error around the
at-the-money nodes at maturity date.}]{\label{fig.approximation
error} {\bf Distribution error and nonlinearity error around the
at-the-money nodes at maturity date.}}
\end{center}
\end{figure}

\par
Fig.~\ref{fig.approximation error} illustrates the two sources of
error graphically around at the money nodes of a one year European
put at expiration date with the initial asset price $S_{0}=100$,
the exercise price $X=100$, riskless rate $r=0.1$ and volatility
$\sigma=0.25$. The solid line represents the option payoff. The
gray shaded bars represent the nodes in the trinomial lattice,
corresponding to asset prices of 99.0, 99.5, 100.0, and 100.5. The
heavy dashed line represents the lognormal density over this
region of the price space. The light dashed bars indicate how the
probability density is discretized over this price range. The
contribution of a particular node to the option value equals the
value of the node probability multiplies the option payoff at the
asset price for that node. The distribution error arises from the
difference between the heavy dashed line and the light dashed
line. At the $S=100$ node, the nonlinearity error is caused by
undervaluing the probability weighted average payoff to zero in
this interval \cite{Figlewski(1999a)}.
\par
The adaptive mesh model presented in this thesis can significantly
reduce the nonlinear error over a given region of the tree.

\section{Building the Model}
Now we start to build a lattice model to price plain vanilla
options using adaptive mesh mechanism around the nonlinear payoff
region of exercise price at maturity. The essence of the AMM is to
use a relatively coarse lattice throughout the option life and
insert meshes with higher resolution into the tree where the
nonlinear error is contributed. It is important for the fine mesh
structure (higher resolution mesh) to be isomorphic so that
additional, still finer mesh can be added using the same
procedure. This allows increasing resolution in a given region of
the lattice as much as one wishes without requiring the step size
changes elsewhere.
\par
Here we introduce an isomorphic AMM structure that can be easily
applied to each region of the lattice. Trinomial tree is chose as
the base lattice to approximate the risk neutral distribution
because it has more degrees of freedom and has proven to be more
useful and adaptable for many derivative applications. Because the
asset price is assumed to be lognormal, the tree is based on the
log of asset price $S$. Define $X=\ln(S)$, which implies that $X$
is normally distributed. Under risk neutral assumption, $X$
follows the standard diffusion process:
\[
dX(t)=\alpha dt+\sigma dz
\]
where $\alpha=r-q-\sigma^{2}/2$, $\sigma$ denotes volatility, $dz$
is standard Brownian motion, and $r$ and $q$ are the riskless
interest rate and dividend yield.
\par
In trinomial tree, there are three different branches for any node
to move to next time state, which are called up (u), down (d), and
middle (m). For deduction's convenience, we change the variable
$X$ by $X'=X-\alpha t$. $X'$ is the mean-adjusted value of the log
of asset price and the mean of $X'$ would be $0$ at any time
state. Hence, The trinomial tree of $X'$ is symmetric. Let $k$
denote the length of a time step (decided by the option's maturity
$T$, and the number of time steps $N$ to be used for the tree with
$k=T/N$) and $h$ be the size of an up and down move. Thus over one
time period $X$ goes to $X+h$ with probability $p_{u}$, to $X-h$
with probability $p_{d}$, and remain unchanged with probability
$p_{m}$.
\par
Matching the mean, variance, and summing up all probabilities to
be one, there are three constraints must be obeyed by the three
next state prices and three probabilities at each node of tree.

\begin{equation}
\begin{split}
&1 = p_{u}+p_{m}+p_{d},\\
&E[X'(t+k)-X'(t)]=0=p_{u}h+p_{m}0+p_{d}(-h),\\
&E[(X'(t+k)-X'(t))^{2}]=\sigma^{2}k=p_{u}h^{2}+p_{m}0+p_{d}(-h)^{2}\label{eq.prob1}.
\end{split}
\end{equation}

\par
By solving Eq. (\ref{eq.prob1}) we can get the following
relations:
\begin{eqnarray}
p_{u}&=&\frac{\sigma^{2}k}{2h^{2}},\nonumber\\
p_{m}&=&1-\frac{\sigma^{2}k}{h^{2}},\label{eq.probresult1}\\
p_{u}&=&\frac{\sigma^{2}k}{2h^{2}}.\nonumber
\end{eqnarray}


 Besides, because the tree of $X'$ is symmetric distributed,
all odd-numbered moments of the trinomial will be zero, as they
are for the normal. Therefore, we can set the kurtosis in the tree
equal to that of the normal.
\begin{equation}
E[(X'(t+k)-X'(t))^{4}]=3\sigma^{4}k^{2}=p_{u}h^{4}+p_{m}0+p_{d}(-h)^{4}\label{eq.prob2}.
\end{equation}

Applying the relations in Eq. (\ref{eq.probresult1}) into Eq.
(\ref{eq.prob2}) for the probabilities yields:

\begin{eqnarray}
h&=&\sigma\sqrt{3k},\nonumber\\
p_{m}&=&2/3,\label{eq.probresult2}\\
p_{u}&=&p_{d}\:\:\:=1/6.\nonumber
\end{eqnarray}


This is the trinomial process approximating the asset price
distribution:

\begin{equation*}
X'_{t+k}-X'_{t}= \left\{\begin{array}{c}
\:\:h, \:\:\:\:\:\:\:\text{with probability} \:p_{u}=1/6\\
\:\:\,0, \:\:\:\:\:\:\text{with probability} \:p_{m}=2/3\\
-h, \:\:\:\:\:\:\:\text{with probability} \:p_{d}=1/6.
\end{array}\right.
\end{equation*}

which implies the process of $X$
\begin{equation}
X_{t+k}-X_{t}= \left\{\begin{array}{c}
\alpha k+h, \:\:\:\:\:\:\:\text{with probability} \:p_{u}=1/6\\
\:\:\:\:\:\:\:\:\alpha k, \:\:\:\:\:\:\:\text{with probability} \:p_{m}=2/3\\
\:\alpha k-h, \:\:\:\:\:\:\:\text{with probability} \:p_{d}=1/6.
\end{array}\right.\label{eq.probx}
\end{equation}

The option value at a given asset price and time, $V(X,t)$ is
computed from the values at the three successor nodes as:

\begin{align}
V(X,t)&=\text{exp}(-rk)[p_{u}V(X+\alpha k+ h,t+k)+p_{m}V(X+\alpha k,t+k)\nonumber\\
&\quad+p_{d}V(X+\alpha k-h,t+k)].\label{eq.reduction} \end{align}

Note that for generality Eq. (\ref{eq.reduction}) allows that the
probabilities may vary with h and k, even though in the current
case of Eq. (\ref{eq.probx}) they are fixed.

\section{Application of the Adaptive Mesh Model to Plain Vanilla Options}
For a European option, nonlinearity error is around the exercise
price at expiration. It turns out that an American option's
nonlinearity error is also largely accounted for by the error in
the last time step, for the prices that bracket the strike price.
Besides, for an American option there is also an approximation
error with regard to where the early exercise occur. However, by
"smooth pasting" property \cite{smooth pasting} of the American
option value, this kind of approximation error does not translate
into significant error in valuing option because the values of
option price nodes is not highly nonlinear around the early
exercise boundary.

\begin{figure}[h]
\begin{center}
\includegraphics{AMM_put.eps}
\caption[{\mdseries An AMM for a put option around exercise price
at expiration.}]{\label{fig.AMM_put} {\bf An AMM for a put option
around exercise price at expiration.}}
\end{center}
\end{figure}

\par
While there is already a well-known analytic solution by Black and
Sholes for pricing European option, we do not only take an
European put option but also take an American put option with AMM
mechanism applied around exercise price at maturity date as
examples. Fig.~\ref{fig.AMM_put} illustrate the critical region of
Adaptive Mesh trinomial tree that we wish to construct to value a
put option. The base coarse lattice, with price and time steps $h$
and $k$, is represented by heavy lines, and light lines represent
the finer mesh with price step size $h/2$ and time step size
$k/4$. The finer mesh covers all coarse nodes at time state $T-k$,
from which there are both fine-mesh paths that end up in-the-money
and out of-the money at expiration, i.e. $A_{2}$, $A_{3}$,
$A_{4}$, and $A_{5}$ in this figure. $X$ is the strike price, and
$X^{+}$ and $X^{-}$ are the two date T coarse-mesh node asset
price that bracket the strike price. In finer mesh, $X^{+}$ is the
highest out of-the money node that branches from $A_{2}$ whereas
$X^{-}$ is the lowest in-the-money price node from $A_{2}$. Since
all branches starting from nodes below $A_{1}$ all end up
in-the-money and paths start from nodes above $A_{6}$ are all
expired at the end, there is no need to fine the mesh.

\par
The finer mesh is set up with one-half price size of the previous
coarser mesh. To cut the price step size in half with maintaining
the relationship in Eq. (\ref{eq.probx}), the time step price must
be set one-quarter of the size of the coarser one. By the
isomorphism of AMM, the trinomial tree lattice introduced in
Fig.~\ref{fig.AMM_put} can cut into any finer level as one wish in
the same manner. Thus, if we set the base mesh as level $0$, then
the finer mesh of level $M$ has price step size $h_{M}=h/2^{M}$
and time step size $k_{M}=k/2^{M}$.


\begin{figure}
\begin{center}
\includegraphics{Convergence_Plain_APut.eps}
\caption[{\mdseries The AMM model convergence for at-the-money
American put}]{\label{fig.Convergence_Plain_APut} {\bf The AMM
model convergence for at-the-money American put.}} $S=100$,
$X=100$, $\sigma=20\%$, $r=10\%$, dividend yield $q=0\%$, and
$T=0.5$ year.
\end{center}
\end{figure}
\par
In the traditional trinomial tree model, there are $(N+1)^{2}$
nodes of price computation in total, where $N$ is the number of
price steps. Therefore, cutting the price step in half to reduce
the nonlinear error makes $N$ become quadrupled ($h$ is
proportional to $\sqrt{k}$) which implies $16$ times computation
amount than before. On the other hand, as we can see in
Fig.~\ref{fig.AMM_put} adding one level of adaptive mesh model to
cut the nonlinearity error down only needs 40 more nodes of price
computation in critical region (9, 11, 13, and 7 for time states
$T-3/4k$, $T-2/4k$, $T-1/4k$, and $T$).
\par
Fig.~\ref{fig.Convergence_Plain_APut} shows the convergence
behavior of an in-the-money American put which is priced by
Adaptive Mesh Model. The Label of AMM-M means the AMM model of
level M. The yellow line represents the Traditional Trinomial
Approach, while the blue line is the convergence behavior of
Adaptive Mesh Model of level 2. Although there is the
approximation error contributed by early exercise, AMM model still
can improve the convergence behavior with a little more
calculations in American put options. If we rule out the influence
of early exercise, it comes to the European put option whose
convergence behavior is presented in
Fig.~\ref{fig.Convergence_Plain_EPut} where we can see that a
higher level of AMM model gives rise to a better convergence rate.


\begin{figure}
\begin{center}
\includegraphics{Convergence_Plain_EPut.eps}
\caption[{\mdseries The AMM model convergence for at-the-money
European put.}]{\label{fig.Convergence_Plain_EPut} {\bf The AMM
model convergence for at-the-money European put.}} $S=100$,
$X=100$, $\sigma=20\%$, $r=10\%$, dividend yield $q=0\%$, and
$T=0.5$ year.
\end{center}
\end{figure}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Numerical Results}
In this chapter we compare the AMM model with other mechanisms
divided into three different categories: trinomial tree lattice
mechanisms, the BGK formula approach, and the quadrature method.
There are three trinomial tree mechanisms to compete with AMM
model. The first is the trinomial method for ordinary options
provided by Kamrad and Ritchken (1991) \cite{Kamrad(1991)}. The
second is a tree lattice with a stretch parameter proposed by
Ritchken (1995) \cite{Ritchken(1995)} for continuously monitored
not only single but also double barrier options. However, with
only a little modification the same mechanism can be also applied
to discrete barrier options where this paper is mainly focused. At
last, the Broadie, Glasserman, and Kou's Enhanced Trinomial Tree
mechanism \cite{Broadie(1999)} is implemented to compare with AMM.
In the category of formula-based approach, Broadie, Glasserman,
and Kou also propose a continuity correction to the formula of
continuous barrier option which is called BGK model for pricing
discrete barrier options\cite{Broadie(1997)}. Finally, the
quadrature method firstly suggested by Andricopoulos et al. (2003)
is carried out. The quadrature method has characteristics of
multinomial lattice and finite difference method and is especially
powerful in pricing of discretely monitored derivatives.
\par
All competing methods in this chapter are implemented in C++
programs running on a PC with an Intel Pentium 4 3.2GHz CPU and
1.0 GB of RAM.

\section{Trinomial Tree Lattice Mechanisms}
\subsection{The Ritchken Trinomial Tree Mechanism}
In \cite{Ritchken(1995)} Ritchken proposes an approximated tree
lattice for continuous barrier options. Let us set
 $X=\ln S$, where $S$ is the underlying asset price.
 The Ritchken's trinomial process is defined as below:
\begin{equation}
X_{t+\Delta t}-X_{t}= \left\{\begin{array}{c}
\:\:\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with probability} \:p_{u}\\
\:\:\:\:\:\:\:\:\:\:\:\:\:\:0, \:\:\:\:\:\:\:\text{with probability} \:p_{m}\\
-\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with
probability} \:p_{d}.
\end{array}\right.\label{eq.ritchkenlambda}
\end{equation}
and $p_{u}$, $p_{m}$, and $p_{d}$ are
\begin{eqnarray}
p_{u}&=& \frac{1}{2\lambda^{2}}+\frac{\alpha\sqrt{\Delta
t}}{2\lambda\sigma},\nonumber\\
p_{m}&=&1-\frac{1}{\lambda^{2}},\nonumber\\
p_{d}&=&\frac{1}{2\lambda^{2}}-\frac{\alpha\sqrt{\Delta
t}}{2\lambda\sigma}.\nonumber
\end{eqnarray}
where $1\leq\lambda<2$ and $\alpha$ and $\sigma$ are defined as
before.

\begin{figure}
\begin{center}
\psfrag{x}{$\sigma\sqrt{\Delta t}$}
\psfrag{y}{$\lambda\sigma\sqrt{\Delta t}$}
\psfrag{z}{$\gamma\lambda\sigma\sqrt{\Delta t}$}
\includegraphics[width=\textwidth]{ritchken.eps}
\caption[{\mdseries The Ritchken Trinomial Tree for continuous
barrier options.}]{\label{fig.ritchken} {\bf  The Ritchken
Trinomial Tree for continuous barrier options.}} (a)Single barrier
options. (b)Double barrier options.
\end{center}
\end{figure}

\par
$\lambda$ is the stretch parameter that controls the gap between
layers of prices on the lattice and can be adjusted to make the
lattice "hit" a single barrier as shown in Fig. (a). As to double
barrier options, Ritchken in the same paper also proposes an
additional stretch parameter, $\gamma$, to make the second barrier
be hit by lattice. The tree lattice of Ritchken for the double
barrier option is presented in Fig. (b). Let $X^{a}$ denotes the
variable $X$ at level a. We have the process
\begin{equation}
X^{a}_{t+\Delta t}-X^{a}_{t}= \left\{\begin{array}{c}
\:\:\:\:\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with probability} \:p_{u}'\\
\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0, \:\:\:\:\:\:\:\text{with probability} \:p_{m}'\\
-\gamma\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with
probability} \:p_{d}'.
\end{array}\right.\label{eq.ritchkengamma}
\end{equation}
where $1\leq\gamma<2$.
\par
Matching up the mean and variance for these nodes leads to
\begin{eqnarray}
p_{u}'&=& \frac{b+a\gamma}{1+\gamma},\nonumber\\
p_{m}'&=&1-p_{u}'-p_{d}',\nonumber\\
p_{d}'&=&\frac{b-a}{\gamma(1+\gamma)}.\nonumber
\end{eqnarray}
where $a=\frac{\alpha\sqrt{\Delta t}}{\lambda\sigma}$ and
$b=\frac{1}{\lambda^{2}}$.
\par
However, those mechanism proposed by Ritchken are all for
continuous barrier options. For those barriers monitored
discretely we should not only calculate lattice nodes between
price levels of up-barrier and down-barrier but also take into
account those nodes above up-barrier and below down-barrier. It
would be no problem for us using the process in Eq.
(\ref{eq.ritchkenlambda}) except for nodes at the same level of
down-barrier. The process for the nodes at down-barrier level
should be as follows:
\begin{equation}
X^{Hd}_{t+\Delta t}-X^{Hd}_{t}= \left\{\begin{array}{c}
\:\:\:\:\gamma\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with probability} \:p_{u}''\\
\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0, \:\:\:\:\:\:\:\text{with probability} \:p_{m}''\\
-\lambda\sigma\sqrt{\Delta t}, \:\:\:\:\:\:\:\text{with
probability} \:p_{d}''.
\end{array}\right.\label{eq.ritchkengamma}
\end{equation}
where
\begin{eqnarray}
p_{u}''&=& \frac{a+b}{\gamma(\gamma-1)},\nonumber\\
p_{m}''&=&1-p_{u}''-p_{d}'',\nonumber\\
p_{d}''&=&\frac{b-a\gamma}{\gamma+1}.\nonumber
\end{eqnarray}
with $a$ and $b$ defined as earlier.

\subsection{The Enhanced Trinomial Tree Mechanism}
Broadie et al. followed their continuity correction concept
\cite{Broadie(1997)} and proposed a barrier-shifted lattice
mechanism for discrete barrier options called \emph{enhanced
trinomial method} in 1999\cite{Broadie(1999)}. They use the same
trinomial approach of Ritchken's method described just above but
shift the discrete barrier at level $H$ to
$H'=He^{\pm0.5\lambda^{*}\sigma\sqrt{\Delta t}}$(with $+$ for an
up barrier and $-$ for a down barrier). The
$\lambda^{*}=\sqrt{3/2}$ is recommended by Boyle
\cite{Boyle(1988)} and Omberg \cite{Omberg(1988)}, and
$0.5\lambda^{*}\sigma\sqrt{\Delta t}$ is the average overshoot
over a boundary for the random walk process. Broadie et al.
suggest a procedure producing an $n$ (time step number) which is
divisible by $m$ (barrier monitoring frequency), a $\lambda$
(stretch parameter) which is close to $\lambda^{*}$, and a layer
of nodes which coincides with the shifted barrier, and then use
those parameters to construct the enhanced trinomial tree.

\par
Nevertheless, for the convenience of comparing with other
mechanisms, the time step number $n$ should be free for input.
Hence, we use a different procedure against Broadie et al.. Let
$\lambda_{k}=|log(H/S)|/(k\sigma\sqrt{\Delta t})$, for $k=1$, $2$,
...,$k'$, where $k'$ corresponds to the first time a layer of
nodes crosses the shifted barrier without stretch of price step
size (i.e. $\lambda=1$). Then we choose the $\lambda$ from
$\lambda_{k}$ which minimizes $|\lambda_{k}-\lambda^{*}|$ for
$k=1$, $2$, ...,$k'$, no matter what kind of $n$ is input. But the
$\lambda$ we choose here can only make one barrier be matched by a
price level of enhanced trinomial tree so we apply the Ritchken's
second stretch parameter technique described above to the enhanced
trinomial tree making the second barrier be hit.
\par
Finally, there is a noteworthy point. Broadie et al. remark by
themselves that the enhanced trinomial method preforms better with
less frequent monitoring of the barrier.

\subsection{Numerical Comparisons}
Since the competing mechanisms have been shortly introduced, now
we can turn our focus onto the numerical comparisons of these
methods.

\par
Table. ~\ref{tb.methods_comparison_single} shows numerical
comparisons of AMM with its competitors in a down-and-out option
under different barriers and different condition monitoring
frequencies. We choose the benchmark as the AMM with AMM level of
8 and time step number $n=1,000,000$. It's because we can find
from our research data that AMM contributes the best convergence
rate, and result prices of all other methods are getting closer to
AMM-8's value while time step number is increasing. We see an
example of this phenomenon in Table. ~\ref{tb.data_of_convergence}
by numerical data, and also there are some figures of convergence
rate in Fig. ~\ref{fig.Convergence_DO_ECall_Frequencies}.

\begin{table}
\fontsize{8}{12.5pt}\selectfont \tabcolsep=3.5pt
\begin{tabularx}{13.6cm}{@{}cccrcrcrcr@{}}
\toprule
\multirow{3}*{\bf Barrier}&\multirow{3}*{\bf Benchmark$^{a}$}&&&&&\multicolumn{2}{c}{{\bf Enhanced}} & &\\[-2pt]
&&\multicolumn{2}{c}{{\bf Trinomial$^{b}$}}
&\multicolumn{2}{c}{{\bf Ritchken$^{c}$}}&\multicolumn{2}{c}{{\bf
Trinomial$^{d}$}}&\multicolumn{2}{c}{{\bf AMM-8}}\\
\cmidrule(l){3-10}
&&value$^{e}$&error(\%)$^{f}$&value&error(\%)&value&error(\%)&value&error(\%)\\
\midrule
\multicolumn{10}{c}{\emph{monitoring frequency=2}}\\
80&8.2566 &8.2559 &$-0.0093$ &8.2561 &$-0.0063$ &8.2561 &$-0.0068$ &8.2566 &$-0.0001$\\
90&8.1273 &8.1393 &0.1473 &8.1160 &$-0.1390$ &8.1272 &$-0.0015$ &8.1272 &$-0.0020$ \\
95&7.8092 &7.8208 &0.1486 &7.7752 &$-0.4346$ &7.8092 &0.0017 &7.8091 &$-0.0006$ \\
99&7.3019 &7.3348 &0.4516 &7.2202 &$-1.1186$ &7.3097 &0.1065 &7.3022 &0.0047 \\

\multicolumn{10}{c}{\emph{monitoring frequency=5}}\\
80&8.2535 &8.2526 &$-0.0099$ &8.2525 &$-0.0115$ &8.2529 &$-0.0063$ &8.2535 &0.0000 \\
90&7.9118 &7.9463 &0.4365 &7.8799 &$-0.4027$ &7.9123 &0.0060 &7.9117 &$-0.0008$ \\
95&7.0217 &7.0542 &0.4633 &6.9293 &$-1.3158$ &7.0226 &0.0131 &7.0214 &$-0.0047$ \\
99&5.7210 &5.8010 &1.3978 &5.5310 &$-3.3207$ &5.7398 &0.3277 &5.7219 &0.0158 \\

\multicolumn{10}{c}{\emph{monitoring frequency=25}}\\
80&8.2435 &8.2426 &$-0.0116$ &8.2414 &$-0.0256$ &8.2431 &$-0.0050$ &8.2435 &0.0001 \\
90&7.5882 &7.6530 &0.8527 &7.5305 &$-0.7614$ &7.5904 &0.0285 &7.5881 &$-0.0020$ \\
95&5.9302 &5.9946 &1.0871 &5.7524 &$-2.9982$ &5.9335 &0.0563 &5.9297 &$-0.0080$ \\
99&3.4393 &3.5885 &4.3374 &3.1095 &$-9.5892$ &3.4748 &1.0329 &3.4382 &$-0.0335$ \\

\multicolumn{10}{c}{\emph{monitoring frequency=125}}\\
80&8.2350 &8.2340 &$-0.0120$ &8.2322 &$-0.0346$ &8.2347 &$-0.0032$ &8.2350 &0.0001\\
90&7.3683 &7.4530 &1.1482 &7.2996 &$-0.9335$ &7.3729 &$0.0618$ &7.3684 &0.0004 \\
95&5.3370 &5.4211 &1.5745 &5.1280 &$-3.9177$ &5.3470 &$0.1866$ &5.3370 &$-0.0007$ \\
99&2.1829 &2.3881 &9.4019 &1.7717 &$-18.8369$ &2.2230 &1.8374 &2.1801 &$-0.1284$ \\
\midrule
\multicolumn{10}{l}{It is an down-and-out call with $T=0.5$ year, $r=5\%$, $q=0\%$, $\sigma=25\%$, $S=100$, and $X=100$.}\\
\multicolumn{10}{l}{All methods are calculated with time steps $n=750$.}\\
\multicolumn{10}{l}{$^{a}$The Benchmark comes from the AMM-8 lattice with $1,000,000$ steps.}\\
\multicolumn{10}{l}{$^{b}$The Trinomial is the standard trinomial tree proposed by Kamrad and Ritchken\cite{Kamrad(1991)} with }\\[-2pt]
\multicolumn{10}{l}{$\lambda=1.2533136$\cite{Lyuu(2002)}.}\\
\multicolumn{10}{l}{$^{c}$The Ritchken is the Ritchken Trinomial Tree Mechanism\cite{Ritchken(1995)} with modification described above.}\\
\multicolumn{10}{l}{$^{d}$The Enhanced Trinomial is proposed by Broadie et al.\cite{Broadie(1999)} with modification described above.}\\
\multicolumn{10}{l}{$^{e}$All the values are rounded off to the forth decimal place.}\\
\multicolumn{10}{l}{$^{f}$The error(\%) field is the percentage pricing error $=[$approximation/(benchmark)$-1]100\%$ rounded}\\[-2pt]
\multicolumn{10}{l}{ to the forth decimal place with all the values computed before rounding.}\\
 \bottomrule
\end{tabularx}
\caption[{\mdseries Numerical comparisons of AMM with other tree
lattice methods in single discrete barrier
options.}]{\label{tb.methods_comparison_single} {\bf Numerical
comparisons of AMM with other tree lattice methods in single
discrete barrier options.}}
\end{table}



\chapter{Conclusions}
This thesis does not only implement the Adaptive Mesh Model for
single discrete barrier options but also extend the Adaptive Mesh
Model to price double discrete barrier options. Besides, we also
comprehensively implement other competitive methods with detailed
numerical results to compare with AMM such as the standard
trinomial tree, Ritchken's trinomial lattice, the enhanced
trinomial tree, the BGK formula approach, and the quadrature
method. Reducing nonlinearity error by applying higher resolution
lattices in critical area makes AMM converge to accurate option
price more efficiently than other tree lattice methods. Comparing
with the BGK formula approach, AMM is more precise under the
barrier-too-close situation and lower barrier monitoring
frequency. Although the quadrature method is generally more exact
than AMM, AMM can beat the quadrature method in efficiency under
higher barrier monitoring frequency with accurate enough outcomes.
From our research data, we numerically prove the accuracy and the
efficiency of the Adaptive Mesh Model no matter where the barrier
price is or what barrier monitoring frequency it is.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{999}

\bibitem{Merton(1973)}
{\sc Merton, R.} (1973) Theory of Rational Option Pricing.
\emph{Bell Journal of Economics \& Management}

\bibitem{Reiner(1991)}
{\sc Reiner, E., and Rubinstein, M.} (Sep 1991) Breaking Down the
Barriers. \emph{Risk 4}, 8, pp. 28-35.

\bibitem{Reiner(2000)}
{\sc Reiner, E.} (2000) \emph{Convolution Methods for
Path-Dependent Options}. Preprint, UBS Warburg Dillon Read.

\bibitem{Heynen(1996)}
{\sc Heynen, R.C., and Kat, H.} (1996) Discrete Partial Barrier
Options with a Moving Barrier. \emph{Journal of Financial
Engineering}, 5, pp. 199-209.


\bibitem{Broadie(1997)}
{\sc Broadie, M., Glasserman, P., and Kou, S.G.} (1997) A
Continuity Correction For Discrete Barrier Options.
\emph{Mathematical Finance }, 7, pp. 325-49.

\bibitem{Boyle(1994)}
{\sc Boyle, P., and Lau, S.H.} (1994) Bumping Against the Barrier
with the Binomial Method. \emph{Journal of Derivatives}, 1, pp.
6-14.

\bibitem{Hull(2002)}
{\sc Hull, J.} (2002) \emph{Options, Futures and Other
Derivatives}, 5th Edition, Prentice-Hull.

\bibitem{Derman(1995)}
{\sc Derman, E., Kani, I., Ergener, D., and Bardhan, I.} (1995)
Enhanced numerical methods for options with barriers.
\emph{Goldman Sachs Quantitative Strategies Research Notes}.

\bibitem{Ritchken(1995)}
{\sc Ritchken, P.} (1995) On Pricing Barrier Options.
\emph{Journal of Derivatives}, 3, pp. 19-28.

\bibitem{Cheuk(1995)}
{\sc Cheuk, T.H.F., and Vorst, T.C.F.} (1995) Complex Barrier
Options. \emph{Journal of Derivatives}, 4, pp. 8-22.

\bibitem{Broadie(1999)}
{\sc Broadie, M., Glasserman, P., and Kou, S.G.} (1999) Connecting
discrete and continuous path-dependent options. \emph{Finance
Stochastics}, 3, pp. 55-82.

\bibitem{Wei(1998)}
{\sc Wei, J.} (1998) Valuation of Discrete Barrier Options by
Interpolations. \emph{Journal of Derivatives}, 6, pp. 51-73.

\bibitem{Figlewski(1999a)}
{\sc Figlewski, S., and Gao, B.} (1999) The Adaptive Mesh Model: A
New Approach to Efficient Option Pricing. \emph{Journal of
Financial Economics}, 53, pp. 313-351.

\bibitem{Figlewski(1999b)}
{\sc Ahn, D-G., Figlewski, S., and Gao, B.} (1999) Pricing
Discrete Barrier Options with an Adaptive Mesh Model.
\emph{Journal of Derivatives}, 6(4), pp. 33-44.

\bibitem{Andricopoulos(2003)}
{\sc Andricopoulos, A.D., Widdicks, M., Duck, P.W., and Newton,
D.P.} (2003) Universal option valuation using quadrature methods.
\emph{Journal of Financial Economics}, 67, pp. 447-471.

\bibitem{smooth pasting}
{\sc Tavella, D., and Randall, C.} (2000) \emph{Pricing Financial
Instruments}, 1th Edition, John Wiley \& Sons.

\bibitem{Kamrad(1991)}
{\sc Kamrad, B., and Ritchken, P.} (1991) Multinomial
Approximating Models for Options with k-State Variables.
\emph{Management Science}, 37, 12, pp. 1640-1652.

\bibitem{Boyle(1988)}
{\sc Boyle, P.} (1988) A lattice framwork for option pricing with
two state varaibles. \emph{Journal of Financial and Quantitative
Analysis}, 35, pp. 1-12.

\bibitem{Omberg(1988)}
{\sc Omberg, E.} (1988) Efficient discrete time jump process
models in option pricing. \emph{Journal of Financial and
Quantitative Analysis}, 23, pp. 161-174.

\bibitem{Lyuu(2002)}
{\sc Lyuu, Y.} (2002) \emph{Financial Engineering and
Computation}, 1th Edition, Cambridge University Press.

\bibitem{Tsai(2005)}
{\sc Tsai, Shao-Hwai.} (2004) Pricing discrete double-barrier
options with the quadrature method. Master's Thesis. Department of
Finance, National Taiwan University, Taiwan.

\bibitem{Ko(2003)}
{\sc Ko, Kun-Yi.} (2003) Fast accurate option valuation using
Gaussian quadrature. Master's Thesis. Department of Finance,
National Central University, Taiwan.

\bibitem{Moler(2004)}
{\sc Moler, C.} (2004) \emph{Numerical Computing with MATLAB},
Mathworkd, New York.


\end{thebibliography}

\appendix

%\chapter{Properties of the Interpolated Option Value}
%\label{appendix_convex}


%\chapter{Derivation of the State Count} \label{appendix_bucket}

\clearpage



\end{document}
