\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 $HS$. \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}