UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Willow tree Ho, Andy C.T. 2000

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2000-0424.pdf [ 1.43MB ]
Metadata
JSON: 831-1.0080017.json
JSON-LD: 831-1.0080017-ld.json
RDF/XML (Pretty): 831-1.0080017-rdf.xml
RDF/JSON: 831-1.0080017-rdf.json
Turtle: 831-1.0080017-turtle.txt
N-Triples: 831-1.0080017-rdf-ntriples.txt
Original Record: 831-1.0080017-source.json
Full Text
831-1.0080017-fulltext.txt
Citation
831-1.0080017.ris

Full Text

WILLOW  TREE  By A n d y C . T . Ho B . Sc. (Mathematics) S i m o n Fraser University M . Sc. (Mathematics) University of B r i t i s h C o l u m b i a P h . D . (Mathematics) University of B r i t i s h C o l u m b i a A  THESIS T H E  SUBMITTED  IN  PARTIAL FULFILLMENT  REQUIREMENTS F O R T H E D E G R E E M A S T E R  O F  O F  SCIENCE  in T H E  FACULTY  O F  G R A D U A T E  STUDIES  MATHEMATICS  We accept this thesis as conforming to the required standard  T H E  UNIVERSITY  O F BRITISH  COLUMBIA  M a y 2000 © A n d y C . T . H o , 2000  O F  U B C Special Collections - Thesis Authorisation Form  Page 1 of 1  In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d b y t h e h e a d o f my department o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . ....  Department o f The U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r , Canada —  Date  ,  .N.i,U|  M  |  LOOP  http://www.library.ubc.ca/spcoll/thesauth.html  2000/07/21  Abstract  We present a tree algorithm, called the willow tree, for financial derivative pricing. The setup of the tree uses a fixed number of spatial nodes at each time step. The transition probabilities are determine by solving linear programming problems. The willow tree method is radically superior in numerical performance when compared to the binomial tree method.  ii  Table of Contents  Abstract  ii  List of Figures  v  List of Tables  vi  Acknowledgment  1  2  3  4  vii  Introduction  1  B i n o m i a l Tree  3  W i l l o w Tree  8  3.1  Basic Setup  8  3.2  R a n k of constraint m a t r i x  12  3.3  Convergence of the willow tree  17  Option Pricing  21  4.1  European Option  21  4.2  C a l i b r a t i o n of  22  4.3  N u m e r i c a l Results for European Options  26  4.4  N u m e r i c a l Results for A m e r i c a n O p t i o n  27  iii  (  5  Extension  31  5.1  Extension to other models  31  5.2  Conclusion  33  Bibliography  35  iv  List of Figures  3.1  A discrete approximation of the standard normal distribution  4.2  Small variation of  \Zi(.l) - zj(l)| ~ 10"  v  3  20 28  List of Tables  4.1  European Call ;  4.2  E u r o p e a n C a l l : Percentage of  4.3  E u r o p e a n P u t : Percentage of  4.4  A m e r i c a n P u t : Percentage of  4.5  A m e r i c a n P u t : Average Percentage of  4.6  A m e r i c a n P u t : 50 nodes 20 time steps willow tree vs 200 time steps  s  ^ g  •  26  \V°-V°A  " \v°-v° I 1  28  c / l  y U  1  \  ^  29  ^"Jf^ !  29  0 0  binomial tree  ^"J^ " 0  1  29  30  vi  Acknowledgment  I would like to acknowledge Professor U l r i c h Haussmann for his advice and support through out my M a t h e m a t i c a l Finance P r o g r a m i n U B C . I would also like to thank m y parents for their support and encouragement.  vii  Chapter 1  Introduction  Since the celebrated option pricing model introduced by Black a n d Scholes [2] i n 1973, M a t h e m a t i c a l O p t i o n pricing theory has undergone tremendous revolutionary development.  T h e basis of many of these pricing models stems from incorporating random  diffusion processes generated from B r o w n i a n motion to describe the stochastic dynamics of various quantities i n the financial market.  For many of these models, the theoret-  ical price of an option can be determined by either solving a P D E or computing an expectation w i t h respect to a random process. For most situations, because of the unavailability of closed form solutions, option prices can only be determined numerically. A m o n g the many numerical approaches for option pricing models, a popular one is the binomial re-combining tree algorithms. T h i s algorithm was first developed by C o x , Ross, and Rubinstein [4] i n 1979.  T h e binomial tree generates branches of paths of prices  by bifurcating the prices recursively from one time step to the next. T h e value of the option can then be estimated by computing the risk neutral expectation of the payoff function on the security recursively backward from maturity. Because of its simple setup, this algorithm is widely used i n evaluating many non-path-dependent  options i n the fi-  nance industry. Since the first introduction of the binomial tree, there have been many successful variations of the algorithm applied to many different area of option pricing! In this paper, we would like to present a new type of re-combining tree algorithm, called the willow tree, which was first developed by Michael C u r r a n [3] i n 1998. T h e setup  1  2  Chapter 1. Introduction  of the willow tree is based on estimating the standard Brownian motion b y a discrete M a r k o v process. T h e transition probabilities are determined by solving a sequence of linear programming problems. These transition probabilities only need to be computed once a n d then they can be stored for future useage.  F r o m the M a r k o v process, other  more general processes can be constructed from suitable mappings. O n e distinct feature of the willow tree is that the number of nodes at each time step is constant. T h i s is i n contrast to the binomial tree where the number of nodes grows as 0(M ) 2  where M is  the number of time steps. This feature of the willow tree allows the computation process to be very efficient even w i t h a large number of time steps a n d this becomes especially advantageous for multi-factor models. T h e layout of this paper is as follows.  Chapter 2 describes briefly the b i n o m i a l  tree algorithm. W e show that under the setup for computing E u r o p e a n Options, i t is equivalent to a n explicit finite difference method. Chapter 3 describes the setup of the willow tree. Chapter 4 demonstrates how to apply the willow tree algorithm to compute prices for E u r o p e a n and A m e r i c a n vanilla options. Here, we will only concentrate our study on vanilla options, but the result can easily be extended to many other types of options. W e use the result computed from the binomial tree as a bench mark for comparison. It turns out that the computational time for the willow tree is at least ten times less t h a n that for the binomial tree for a given accuracy. Chapter 5 summarizes our results and discusses the various extensions of the basic setup of the willow tree.  Chapter 2  B i n o m i a l Tree  We would like to show that the binomial tree algorithm for computing E u r o p e a n option prices is equivalent to an explicit finite difference method under suitable setups.  Let  us first briefly describe the binomial tree setup for computing a E u r o p e a n option price. Please see Chapter 10 of [5] for more details. Let  denote the b i n o m i a l tree discrete  process where m is the time index and n is the node index. Starting w i t h an i n i t i a l stock price SQ, allow each stock price S™ to change into two possible prices cm+l °n+l  qm+1  „. cm —  U  O  n )  °n  ~  rlQ  m  a o  n  where u > 1 is the up move factor, d < 1 is the down move factor, 0 < m < M and 0 < n < m.  C o n t i n u i n g this process, we obtain a tree lattice of the price distribution.  Because this a recombining tree,  S™ = S° u d - . n  (1)  m n  Q  A t each node of the tree, we let p to be the probability of an up move and 1 - p of a down move.  m*1  S  n+1  Chapter 2.  Binomial Tree  4  B y choosing the appropriate parameters and letting the time step size 6t —> 0 , i t is possible to show that the tree process converges to the Black Scholes (geometric B r o w n i a n motion) continuous process  dS = S (rdt + adB ),  (2)  t  where r and a are the (risk-neutral) drift and instantaneous volatility respectively, and B  t  is the standard B r o w n i a n motion process. We match the first two moments of the  discrete process to that of the continuous process. B y matching the (risk-neutral) mean and variance of the two processes, we get  pu+(l-p)d  = e  pu + (l-p)d 2  (3)  rSt  = ( ° .  2  2r+  2)5t  e  (4)  Because there are only two equations here, there is still one degree of freedom left i n determining a choice of the parameters p, u, d. B y imposing the condition d = l/u, and the two conditions (3) and (4), we find  e  rdt  d  - d  = A-y/T^T,  u = A+y/A^l,  (5)  where  A = \ (e~  r5t  + ° ) {r+  2)5t  e  .  (6)  Let F(S, T) be the contingent payoff function at expiry time T for an European option and V  m n  be values of the option on the nodes of a binomial tree w i t h parameters p, u, d.  A t time T = M6t,  V  M n  = F(S?).  (7)  Chapter 2.  5  Binomial Tree  T h e subsequent V™ are computed by iterating the formula fStyrn  pV™? + (1 -  =  )V™  +1  P  "i/m+l , "  e  u — d *n+l  '  r6t  _^ T/m+1  u—~ d " V  r5t  0  0  i  u—d  (8)  ^ n  u — d  T h i s setup of the binomial tree is actually equivalent to an explicit finite difference method. M o r e explictly, let us consider the Black Scholes P D E of a European option w i t h variables t, x = In S  SV St  T  ,  1 SV  (  2  2  1 \ SV  .  2  (9)  where t is the time and S is the spot price of the underlying stock. B y w r i t i n g SV  6e- V H  T /  rt  rV — e  St  St '  (9) becomes  ,Se~ V St  1 SV  rt  (  2  2  1.  sv  (10)  Sx  We convert (10) into a finite difference equation by approximating the derivatives w i t h finite differences (See Chapter 10 of [5]). T h e corresponding finite difference equation for (9) is •,-rU  1+1  Km+1 _  grt ym m  (11)  t  ym+1 _ ym+1  1 2  n+l  n  v  x +\  T/m+1 _ ym+ n n—lm+1  y  + (r - -cr ) 2  7 1 + 1  _  n  v  Xr  2-n+l  n  Z  v  1  X  n  —\  = 0,  / 3^n+l %n—\  where *  m  = mft,  atftf = logfiEff,  C  + 1  = log^  + 1  >  <-x = log S T  (12)  Chapter  2.  Binomial  Tree  We would like to express the x's i n terms of u, d. F r o m (12) and (12), x  n + 1  -x  n  Xn-Xn-!  x x-x -x n+  n  tm+1  tin  =  loguS™ - l o g 5 ^ = l o g u  =  log S™ - log dS™ = - log d  =  log u/d  =  &t  and  <ft  logw/d \  logw  logd  Further rearrangment gives  where i  n  ° &t  {r - jo ) 6t  logw/dlogd  \ogu/d  2  cm+  = 1  3  \ogu/d \\ogu  7 1 + 1  logu/dlogd  logw/d  F r o m comparing (13) w i t h (8), we wish to show that  p  r < K  —  log a y  d  Chapter 2.  7  Binomial Tree  Let us expand A, u - 1, d - 1 i n terms of 8t .  F r o m (5-6),  1/2  r  2  2 2  M - 1  =  .4 - 1 + yfW^l  = o8t  + °—8t +  d-l  =  A - l - V ^ l  = -a8t /  1/2  0{8t ' ) 3 2  2 1  + ^-8t  2  +  0(8t ^ ). 3  Using the above and the expansion logo; — (x — 1) — (x — l ) / 2 -\  , we have  2  log u — log d  =  u-d  +  0(8t )  logw  =  a8t  +  0(8t )  logd  =  -a8t  1/2  2  3/2  3/2  +  1/2  0(8t ^ ). 3  2  Subsituting the above into (16) yields  ™ i +  oHt  =  n + 1  ( « - d ) ( l + 0(c5t))crc5i /2(i 1 + r«ft - (1 - aSt '  1 2  +  (r ~ (u-d)(l  (8t))  1  0  + %6t) +  k  2  )  ^  + 0(8t))  Q{8t^ ) 2  u —d e  r5t  -d  +  0(8t / ) 3 2  u —d  Similarly, it is straight forward to show that  = 1 ^ ( C ™ ?  =  1  +  0  ^  1 / 2  ))  0{8t ' ). 3 2  We conclude the chapter by stating the equivalence of the two algorithms i n the following theorem. T h e o r e m 2.1 In calculating the price of a Black Scholes European option model, the binomial  tree algorithm for the case d = 1/u is equivalent  applied to the corresponding  Black Scholes differential  to the forward  equation.  Euler  Scheme  Chapter 3  Willow Tree  3.1  Basic Setup  In setting u p a willow tree lattice for modelling option prices, we first need to set u p a discrete M a r k o v process that converges to a B r o w n i a n motion i n the l i m i t .  A more  general process of a security can then be modelled from the M a r k o v process under suitable mappings (see Chapter 4). M o r e specifically, let z\, z%, • • •, z be the representative n  normal variates w i t h corresponding probabilities qi, c^, • • •, q , i-e., n  <&)} is a discrete  approximation of the standard normal density function where Oj = P(Z = Zi). For example, C u r r a n suggests a choice (see Figure 3.1): ^  =  N-\(i-0.5)/n)  ft  =  1/n  (21)  where N(x) is the cumulative standard normal distribution function. Let Y  tk  be a discrete M a r k o v process w i t h time nodes tk = £ j = i hj, for some  w i t h each hj > 0. Y  tk  takes on the value y/hZi  hi,h,2,-"  when the embedded M a r k o v chain X is  i n state i, 1 < i < n. W e can view each realized sequence of Y  k  tk  as a p a t h traversed on a  tree lattice consisting of parallel layers of nodes. T h e nodes at a given layer correspond to the possible states {xk} at time tk. If Xk = i we assign transition probabilities p-j. that Xk+\ = j. A t the initial time t = 0, there is only one node corresponding to state 0 w i t h the transition probabilities being p§i = Qi-  8  9  Chapter 3. Willow Tree  Sample paths on a willow tree We wish to make Y  tk  converge to a B r o w n i a n motion B i n the limit n —> co and t  hk —>• 0. W e first impose the following conditions on p^:  IZP% =  1  V  j=i  f^Pij^k  j=i  *  (22)  + hkZj = yftkZi V i  £ p% (t + h )z] - t z\ = h j=i k  k  E?4 = ^ i=l  k  k  (23) Vi  V j  (24) (25)  P & > 0 V t , j .  (26)  T h e first condition (22) is just the statement that sum of the conditional probabilities at a node should be unity. T h e second condition (23) constrains the conditional mean E[Y  \Y }=Y  tk+hk  tk  \/t ,hk  tk  k  (27)  which corresponds to the first moment of dB being zero. Similarly, the t h i r d condition t  (24) constrains the conditional variance Var[Y  \Y ]=h  tk+hk  tk  k  Vt ,h k  k  (28)  10  Chapter 3. Willow Tree  which corresponds to the second moment of dB equal dt. W e impose the condition (25) t  so that the unconditional probability of ending at node i at time tk is q i.e., b y i n d u c t i o n iy  and (25)  jlJ2—jk-l jk-i Hence {q } is a stationary distribution, i.e. {X } t  is stationary.  k  In order to further narrow down the choice of the transition matrices ensure that the convergence is sufficiently fast, for each k, the  a n c  i to  are determined from  the following linear programming problem.  Subject to  ^EEpJ-lA + ^ i - vW EPij = W  (29) (30)  1  j=i  ^ P t f V*fc + h Zj = yftkZi Vz k  (31)  j=l f; P y (** + h )z] - t «? = fc V i j=i k  fc  E?iP6 = ^ y 7  fc  (32)  (33)  t=i  rfj>0Vx,j.  (34)  Essentially, we match the first two moments of dB and we require the t h i r d power of t  the distance between transitions to be as small as possible so that we get the proper convergence. We would like to recast the L P problem so that we can easily see that the choice of the distribution {zi,qi}  must have mean = 0 and variance = 1. F o r convenience, let us  drop the fc's and introduce the following notation:  Chapter  3.  Willow  Tree  • v is the transpose of a m a t r i x v 1  • P is the n x n transition m a t r i x w i t h entries Pij • F is the m a t r i x w i t h entries Fji = \ZJ - bzi\  3  a  =  h t  ,  1  o =  Vl+a  In terms of the above notation, the L P becomes nun trace  (PF)  Subject to : Pu  = u  Pz  = bz  p  = br  r  + (1 - b )  2  qP  =  l  p^ >  2  (f  0  A c c o r d i n g to constraints (37) and (39), qz t  = q Pz l  =  bq z. l  Since 6 ^ 0 , this implies that z has mean = 0, i.e.,  12  Chapter 3. Willow Tree  Similarly, from (36), (38), a n d (39) qr = b qr + t  2  t  (l-b ). 2  Since a ^ 0, this implies that z has variance = 1, i.e.  gV = 1. The  (42)  choice of q a n d z suggested i n (21) meets the mean = 0 requirement (41) b u t  fails the variance = 1 requirement (42). However, there are at least two modifications for allowing the suggested q a n d z to satisfy both requirements. T h e first one is to use a non-standard normal distribution AT (0,1 + e) w i t h mean = 0 a n d variance = 1 + e for £  some appropriate e so that Zi = A r ( ( z - 0.5)/n) satisfies (42). T h e second one is to -1  e  modify only the two end points z\ a n d z  n  as z\ — 8 a n d z + S so that (42) is true for an n  appropriate choice of S.  3.2  Rank of constraint matrix  Let us consider the L P i n the original setup but express the constraint i n terms of a m a t r i x equation. L e t us index the entries of P as a vector v = {vi,V2,V3, . . . . i v } where the first n entries of v correspond to the first column of P a n d the second n entries correspond to second column a n d so on. In terms of v, the L P can be stated as min V  fv  (43)  Subject to :  where / is a vector w i t h positive entries.  Mv = w  (44)  Vi > 0 V i  (45)  Chapter  3.  Willow  13  Tree  Let {zi, qi} be an approximation of the standard normal distribution w i t h mean = 0 and variance = 1 such that a = {u, z, r} as described i n previous section is a linearly independent set. We show that the rank of M is 4 n - 3 . We start by choosing a convenient basis 0 = {0i,02 - - • 0n} of l R where 0i = u, 02 = z, 03 = r. In selecting 0, we require n  that Si = span of {040s, 0e, • • • ,0n} is orthogonal to 52 = span of {0i,02,0s}-  Let T be  the m a t r i x that transforms 0 into the standard basis E = { e i , • • •, e „ } and S =  T~ PT. l  We w i l l show that S has n — (An — 3) degree of freedom i n choosing its entries and hence 2  the rank of M must be in — 3. £2 can be constructed explicitly i n the following way. Let a = {0i, • • • ,0 } m  be a  linear independent set and A =[0i  02 •••  (46)  0] m  be the m a t r i x consisting of the vectors i n a. F r o m a QR-decomposition, C  A = Q  (47)  0  where C is a m x m full ranked upper triangular matrix. Using the m a t r i x Q, we let  B  =  0  Q  (48)  In—m C"  0  1  0  where I n  m  (49)  Q-  In-  is a (n - m) x (n - m) identity matrix. We check that B and T have the  desired properties T [ A B ] = / „ and Si _L S2  T[AB]  C"  1  0  C Q-  1  0  In—rn  Q  0  Q  0  ln—m  Chapter 3. Willow Tree  14  0 = In0  In-m _  For the orthogonality property, we use the fact that Q is hermitian, i.e., Q  -  1  = Q*. L e t  cij € a a n d bi be the columns of B. T h e n  <L+iCj = 0 j <m  =  w h e r e Cj i s t h e i  t / l  c o l u m n vector of  C 0  We now show that S — TPT  1  has n - (An - 3) degrees of freedom. U s i n g the basis 2  (3, the L P (35-40) can be restated as the following problem: m i n trace (SG)  (50)  Se\ = e i  (51)  Sea = be2  (52)  Subject to  Se = b e + (1 2  3  3  b)  f  X  ei  (53) (54)  q'S = q (T- ST)..  2  >0 Vi,j  (55)  Chapter 3.  15  Willow Tree  where G = TFT"  1  and q =  (T )V _1  1 0  F r o m the above, S must be of the form  (1 - 6 )  *  * • •  *  * *  2  *  0  b  0  *  * • •  0  0  b  2  *  * • • *  *  0  0  0  *  * • • *  *  0  0  0  *  * • • *  *  * • • *  *  '•  0  0  0  *  * • • *  *  0  0  0  *  * • • *  *  (56)  where the entries of the first three columns are determined and remaining entries subject to the constrains (54) and (55). We determine q by computing its components. {u, z,r}.  We first suppose that q G Span of  F r o m the definition of q ft = e\q =  ftT-yq  = (T" *)^ = 1  fi . q  (57)  Hence, by our choice of /?, q* = ( a i , a , a , 0 , 0 , 0 , •••,()) 2  3  (58)  Chapter 3. Willow Tree  16  where for 1 < i < 3, Oj = (3\q. Thus S must be of the form 1  0  (1-6 )  0  6  0  S24  0  0  b  S34 535  0  0  0  0  0  0  2  2  5  1 4  Sis  Sl(n-l)  S25  S2(n-1) S^n  :  *  0  0  0  *  *  0  0  0  *  *  -Sin  53(n-l)  Sz  *  *  n  (59)  where for 4 < j < n , a\S\j + a^S2j + C23S3J = 0. This implies there are n? — (An — 3) degree of freedoms i n choosing the unknowns. Thus the rank of M must be An - 3. F o r the case q not i n the span of {u,z,r},  we may choose /?4 so that q is i n the span {u, z,r,p4}.  Then g* = ( 1 , 0 , 1 , ^ f t , 0 , 0 . - - - , 0 ) , and we have sij + S3j + q ^^^ 1  (60)  = 0 i f j > A and Su + «34 + <7*/?4S44 = <7*/?4 i f j = A. Result  follows. W e summarize our discussion on the rank of the m a t r i x M of the L P problem by the following proposition.  P r o p o s i t i o n 3.1 The rank of the matrix M in the LP problem specified by (43-45) is An - 3.  Note that i n the L P problem, there is a further nonnegative constraint (45) on v i n addition to the linear equation (44). T h u s a n immediate collorary to the proposition is that the solution of the L P problem is a "corner point" of the feasible region constrained by (44) a n d (45) w i t h only An - 3 non-trivial values. Thus at each node, on average,  Chapter  3.  17  Willow Tree  there are only 4 moves that have non-trivial probability. T h e low density of the transition matrices gives a very high efficiency i n calculating expectations w i t h respect to these transition probabilities.  3.3  Convergence of the willow tree  W e don't have a proof for the convergence of Y  tk  to a B r o w n i a n motion. Nevertheless, we  outline a plausible strategy for showing the convergence. We need the following Central L i m i t Theorem i n our strategy. T h e o r e m 3.1 Let X\,  Xi,  Central Limit  be independent variables = 0,var(Xi)  EXj and following  Theorem satisfying 2 T?\v2\ = a],E\X]\ < oo  : 1  M  Y,E\X?\->0  asM-+oo  where M  Then 1  M  5>j->Jv(o i) f  in distribution  where N(p, cr ) is the normal distribution 2  with mean // and variance cr  2  Chapter  Willow  3.  Tree  18  T h e criterion for a process being a B r o w n i a n motion is the following (page 176 of [6]):  1. It is (almost surely) continuous, 2. the increment Y  s+t  —Y  s  is distributed as a normal N(0, t) and is independent of T , B  the history up to s, s > 0. To show that Y  tk  converges to B r o w n i a n motion, we would like to show that i n the  l i m i t , Y satisfy the above two conditions. For the first condition, we require (Kolmogorov) E\Y +h s  — Y\ s  3  < Kh  1+e  for some K < oo and e > 0. A s for the second condition, we would  t r y to use the C e n t r a l L i m i t theorem to show that Y  s+t  - Y  s  is normal and independent  of Ts. Let us write Y  s+t  —Y  s  as a telescoping sum  Now let us compute the mean and variance for each of the (30-31) E\Y (j+i)&t s+  = 0,  —  Y jAt] s+  I^+Q+IJA*  —  Y j& s+  t  From  Chapter  3.  19  Willow Tree  F r o m (30-33) and the fact that the mean is zero,  var(Y i)& s+{j+  -  t  Ys+jAt)  E[(Ys+(j+i)&t -  E  <?iPij [Zj\/s  Ys+jAt) ] 2  + (J +  = zZQi{ i(s + jAt) i 2z  -  z^s+jAt  + At-2zUs  +  jAt))  = *E& A  i = At. T h i s implies that a(M)  =  t . 1/2  T h e last t h i n g we need to show is that E[\Y ( ) 3+  j+1  - Y jAt\ ] 3  At  s+  < K\At\  1+£  as M ->• oo  and n, the number of spatial nodes, -> oo. This suffices for condition 1 a n d it also implies M-l  1 CT(M)  3  (61)  E  i=0  E[\Y  Since (29) is just E[\Y ^ ^ 3+  +  At  possible values of E[\Y (j i)At 3+  - Y  s+u+1)At  +  \} 3  3+jAt  - Y  < Kt-^\At\  e  -+ 0.  \ ],  so the minimization produces the smallest  — Y j& \ ]-  Hence we expect the following conjecture to  3  s+jAt  3  3+  t  be true.  C o n j e c t u r e 3.1 Let {zi(n),qi(n)} mations of the normal distribution ofY (n,M) tk  be some "reasonable" choices of discrete  such that the corresponding transition matricespfj(n,  satisfy the LPs specified by (35-40).  the limit M —>• oo and n(M)  approxi-  —>• oo, Y  tk  Then there exists n(M)  converges to Brownian  motion.  M)  such that in  Chapter  3.  Willow  Tree  A cfscreta approximation to Die standard normal distribution Each point * has probability 0.1  Figure 3.1: A discrete approximation of the standard normal distribution  Chapter 4  Option  4.1  Pricing  European Option  A n equity following the Black Scholes continuous process defined i n (2), under a m a r t i n gale measure (see Chapter 3 of [1]), has the same spot price distributions as S(t)  = S(0)e -£ ° . {r  (62)  )tk+ Bt  Because we conjecture that the tree distribution Y  tk  constructed i n Chapter 3 converges  to the B r o w n i a n motion B , the distribution of equity prices t  should converge to the distribution of (62) i n the limit. A standard technique for calculating an European option on S(t)  given by (62) w i t h payoff F(S(T))  at terminal time  T uses the conditional expectation w i t h respect to the distribution (62). Let V be the f  value of the option at time t. T h e n V  1  = E[e- F(S(T))\S(t)]. rT  (64)  In a willow tree setup, as i n a binomial tree estimation, V° is estimated by iteratively taking conditional expectations w i t h respect to the transition probabilities. T h e terminal condition at expiry T is  = ns^21  (65)  Chapter 4.  Option Pricing  22  T h e subsequent V^ are calculated iteratively using the formula k  ytk  =  e  -r(t  M - t ) J2 P^V- ,  n > 1.  k+1  k + 1  f c  (66)  j=i  A t the home node, N  o  V  =  -n j2 1  e  q j  v^.  (67)  F r o m (39) V°  = =  - ^i r  e  t k + 1  -  t k  q'P P ---P F(S ) 1  2  M  T  e- q F(S ) rT  J  (68)  T  where q denotes the tranpose of q and F(S ) 1  T  denotes the vector  (F(ST), • • •  ,^(5^)).  Thus the price calculated from a multi-time step setup is equivalent to the price calculated from a one time step setup. T h i s is not so surprising since the distribution of the equity price is chosen v i a (62) and so it is not necessary to construct it v i a the tree.  4.2  C a l i b r a t i o n of  {zi,qi}  There are many ways of choosing {zi,qi} i n a willow tree setup. W e calibrate a choice by comparing (68) for a call w i t h its corresponding closed form solution for (64). Let us consider a n European call w i t h strike K.  T h e closed form solution for the price of the  call is  V? = ^-r= f f  ( V -1r * r  )rWT  l5  - K) e-^dz  (69)  where  s._hsS-(r-flr Csff  (70)  Chapter 4. Option  23  Pricing  For a given {zi, <&}, the willow tree solution (68) is then  K  =  e- J2Qi( ° ~^ rT  i=i* =  £_  s  e(r  -)  )T+<TVTzi K  ^  W  '  * ( 0 (r-^)TWT 5  e  2  i  _  K  \  e  - ^  d  z  ( 7 1  )  where i* is the m i n i m u m of the index i such that Z{ > z* a n d qt = —== /  e  2  dz.  C o m p a r i n g (69) a n d (71), it is easy to see the error V° - V° is f  where  E  =  o  Ei  f  eh*') e~$dz  =  (f  0 =  aVT.  Zi  - e^ ) e-^dz  (72)  z  Note that except for E , the other Ei have no dependence on the strike K. 0  We would like to pick the discrete approximation {zi,qi} between V ° a n d c  so the absolute difference  is small. L e t a > 0 be the a number so that (•-a+Az -a-t-/32  /  -oo  ,2  e? e~dz z  =  o(l/N ) 3  e?'e-*rdz = o(l/JV )  /  3  Ja-Az  and Az = 2a/N. W e set the ft i n the following manner. c-o+Az  -oo  ftv = / Ja—Az  R  2  e~~*dz e 2 dz.  Chapter 4. Option Pricing  24  For 2 < i < N—l, we partition [—a+Az, a—Az] into intervals A = [—a + iAz, — a + (i + l)Az] {  of equal length Az and let  be -a+(i+l)Az /  J2 e-^dz.  (73)  •a+iAz  Now for 2 < i < N — 1, the z% is just any point i n the interval A- For i = 1, iV we choose 2i so that A^(^i) = c?j/2 where N{x) is the standard normal distribution function. B y expanding e@ as Zi  eP*+ {3e (z -z)  + 0(e (Az) )  /3z  IBz  i  (74)  2  and b y (72), for i* < i < N - 1, we have \Ei\  = J (pe (z -z)  +  0z  A  <  i  O(p e (Az) ))e-^dz 2  (pAz + 0((1 (Az) )) 2  f  2  l3z  2  e? e-$dz. z  T h e same argument works for \E \. T h i s implies that 0  „-/3 /2c0  -oo  2  |J571 <  _ V27T  (pAz + 0(P (Az) )) 2  2  V  / ' Jz*  2  e? e-*dz z  + 0(l/iV ) 3  and |£|  =  cf  _  \E\  _  ^ J~ (so <r-4)rWfc _ ^  V  e  ^ff_  e  -$  d z  (PAz + Q ( / ? ( A * ) ) ) / ~ e ^ d s „C!/o .2 "I" 2  2  0 ( 1 / i V  3  )  Cf  Q(l/N ) 3  <  ((3Az + 0(p (Az) )) 2  2  +  Hence if IK/I > l / i V  3 / 2  (75)  Chapter 4. Option  25  Pricing  then (76) "cf  For example, N = 50, a = 5, 0 = .1, ^ fi v  ~ .01.  ]  Actually, we can get a tighter bound for the case where Zi{0) vary slowly for a range of 0 . F r o m (72), we can solve for a Zi(0) so that Ei = 0.  Zi{0) = ^ l o g  (77)  z2  (  1  S'(eP'e-4dz\  2TT  1  ± l cr 0  0  °  (ePPfJ _  \V2t  e  a  * »  d  f» Qi  £ + log ^ w - f l + N ( « { - f l j  B y choosing the  Zj(/?)  for a particular jf  0, it is easy to see that (72) can be written as  ( e ^ - e ^ ) e - ^ d z .  E x p a n d i n g the Zi(0) at 0,  Hence, i f \zi{0) - Zi(0) \ is small, we can get a tighter bound. For example, for .1 < 0 < 1 and N = 50, i n Figure 4.2 the plot shows that |ZJ(.1) - ^ ( 1 ) | ~ 1 0 . In fact, for the - 3  given range of parameters, \zi(0) — Zi(0)\ ~ 1 0 . T h i s implies that for \V^\ > .003, the - 3  error should be less than 1%. Note that the above analysis also shows that for pricing European options, the choice {Zi, qi) based on the equal partition of q i n (21) is only accurate when the corresponding  Chapter  4.  Option  Pricing  26  z's of the non-zero payoff values are concentrated near z — 0, while our choice based on equal p a r t i t i o n of a n interval of z w i l l be accurated for a much wider range of payoff functions.  4.3  N u m e r i c a l Results for E u r o p e a n Options  We compare the results of European and A m e r i c a n vanilla options computed from the willow tree and computed from the binomial tree. Here we use a 50 spatial nodes setup i n the willow tree method. We first compare the values V of European O p t i o n C a l l and P u t computed from the w  willow tree setup to the values V f obtained from the closed form solution. In Table 4.2C  4.3 we list the percentage error of several test cases relative from the closed form solution. In Table 4.2, for the cases where the errors are greater t h a n 1%, the corresponding closed form solution of the calls is unrealistically small w i t h value < 1 0 . For a l l the other - 5  values, the error is always w i t h i n 1%.  In Table 4.3, since the range of parameters used  Table 4.1: European C a l l : T = l , r=0.6, M = Moneyness(= 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1  0.0000 0.0000 0.0000 0.0006 0.0049 0.0202 0.0543 0.1099  0.3 0.0000 0.0001 0.0013 0.0065 0.0206 0.0478 0.0902 0.1472  0.4 0.0001 0.0014 0.0065 0.0193 0.0427 0.0783 0.1260 0.1847  0.5 0.0010 0.0053 0.0164 0.0369 0.0681 0.1099 0.1616 0.2221  0.6 0.0033 0.0123 0.0300 0.0575 0.0950 0.1418 0.1969 0.2592  cr = V o l a t i l i t y 0.7 0.0076 0.0220 0.0461 0.0798 0.1227 0.1736 0.2316 0.2957  0.8 0.0138 0.0339 0.0639 0.1032 0.1506 0.2051  0.9 0.0216 0.0474 0.0829 0.1269 0.1784 0.2362  0.2658 0.3317  0.2993 0.3670  1 0.0308 0.0619 0.1024 0.1509 0.2060 0.2667 0.3321 0.4015  for the puts are identical to the calls, the closed form values are never too small. Hence the relative errors are always very small.  Chapter  4.4  4.  Option  27  Pricing  Numerical Results for American Option  The formula for calculating a vanilla A m e r i c a n option is only a slight variation of its European counterpart, taking account of allowing early exercise of the option.  The  terminal condition at expiry T is (78)  V f = F(S?). The subsequent V£ are calculated iteratively using the formula k  yt  k  =  -r(t -t  e  k+1  k)  M  A  X  ^F(S<*), £  P%v} ^ k+1  ,  n > 1.  (79)  A t the home node,  y ° = e " ^ max ( F ( S ° ) , | j q ^ j .  (80)  We bench mark the results of the willow tree and binomial tree calculation against the 1000 time step binomial tree calculation. Here we use a 50 nodes setup and only consider A m e r i c a n put. In Table 4.4, we see that other t h a n the values corresponding to put w i t h unrealistic value 0.023, all the other 5 0 time steps and 20 time steps values are comparable to the 200 time steps binomial tree calculation. In Table 4.5, we list the average relative errors on the range of parameters : S p o t = 2 0 0 , r = 0 . 5 , a = 0 . 1 , 0 . 2 , • • • 0.5, K = 1 0 0 , 1 2 0 , • • •, 300, T = 1,2. We see that on average, the 5 0 time steps willow tree is more accurate t h a n the 200 time steps binomial tree. L a s t l y we compare the speed performance of two methods. In Table 4.6, by comparing 400 american put calculations from a 50 nodes 20 time steps willow tree setup a n d a 200 time steps binomial tree setup, we see that the willow tree is more than 10 times faster.  Chapter  4.  Option  Pricing  28  Figure 4.2: Small variation of Zi(J3): | ^ ( . l ) - 2,(1)1 ~ I O  - 3  \v°-v° Table 4.2: European C a l l : Percentage of  M/CT  0.2  0.3 0.4  100 3.9274  0.5 0.6 0.7 0.8 0.9 1  0.5701 0.0065 0.6478 0.4463 0.1314 0.1116  T=l, 0.3 1.5927 1.7901 0.0853 0.1393 0.0614 0.5237 0.3782 0.0332  r=0.6, M = Moneyness, 0.4 0.5 0.6 0.0696 0.2202 0.9789 0.0941 0.4644 0.3897 0.6927 0.6301 0.1908 0.3119 0.1243 0.0780 0.0096 0.1412 0.2847 0.2607 0.1997 0.1715 0.2327 0.0081 0.1465 0.0316 0.0636 0.1417  w  c } v 6  a = Volatility 0.7 0.8 0.7266 0.5118 0.4410 0.2592 0.0460 0.3746 0.3299 0.1823 0.2095 0.1839 0.1945 0.2017 0.1609 0.0017 0.0382 0.0948  0.9 0.4824 0.4446 0.1224 0.0798 0.2040 0.1355 0.3202 0.1314  1 0.2242 0.1702 0.1018 0.0748 0.2199 0.0434 0.0204 0.0698  Chapter 4. Option Pricing  29  Table 4.3: European P u t : Percentage of  M/cr 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0  0.2 6.E-09 2.E-08 2.E-07 2.E-06 3.E-05 9.E-05 7.E-05 l.E-04  T = l , r=0.6, M = Moneyness, 0.4 0.5 0.6 0.3 6.E-08 4.E-08 2.E-06 3.E-05 2.E-06 l . E - 0 6 2.E-05 5.E-05 l . E - 0 6 5.E-05 l . E - 0 4 6.E-05 9.E-06 6.E-05 5.E-05 5.E-05 l . E - 0 5 4.E-06 l . E - 0 4 3.E-04 3.E-04 2.E-04 2.E-04 2.E-04 3.E-04 3.E-04 l . E - 0 5 3.E-04 5.E-05 6.E-05 l . E - 0 4 4.E-04  \V°—V°  \  c a  '  a = Volatility 0.7 0.8 6.E-05 7.E-05 l . E - 0 4 9.E-05 2.E-05 2.E-04 3.E-04 2.E-04 3.E-04 3.E-04 3.E-04 4.E-04 4.E-04 5.E-06 l . E - 0 4 3.E-04  1 7.E-05 l.E-04 l.E-04 l.E-04 5.E-04 l.E-04 7.E-05 3.E-04  0.9 l.E-04 2.E-04 l.E-04 l.E-04 4.E-04 3.E-04 l.E-03 5.E-04  Table 4.4: A m e r i c a n P u t : Percentage of '^JfooQ ' 00  a 0.5 0.3 0.2 0.5 0.2 0.4 0.2 0.1 0.3 0.2  Spot=200, r=0.5, a = Volatility, K = Strike, T = M a t u r i t y i n years, Vw N = Value of P u t using W i l l o w Tree w i t h N time steps VB N = Value of P u t using B i n o m i a l Tree w i t h N time steps Ew N = % error relative to the 1000 steps binomial tree calculation EB N = % error relative to the 1000 steps binomial tree calculation K T V 1000 V 200 V 50 V 20 E 200 E 50 E 20 1 106.931 300 106.911 106.958 106.993 0.0256 0.0579 0.0188 1 260 61.787 61.779 61.783 61.772 0.0064 0.0252 0.0136 1 23.942 0.0462 220 23.931 23.936 23.926 0.0239 0.0681 1 24.632 180 24.560 24.623 24.669 0.2915 0.0383 0.1507 0.022 120 1 0.023 0.023 0.022 4.6582 4.6582 2.1329 2 89.852 280 89.848 89.843 89.850 0.0057 0.0049 0.0025 41.354 41.211 240 2 41.363 41.310 0.0216 0.1283 0.3677 200 2 5.755 5.760 5.720 5.665 0.0986 0.6105 1.5540 180 2 16.679 16.663 16.680 16.701 0.0939 0.0088 0.1346 140 2 1.089 1.086 0.2494 1.086 1.088 0.0867 0.2239 B  B  w  w  B  w  Table 4.5: A m e r i c a n P u t : Average Percentage of ^  V  w  ^°° ^ 0  v  Spot=200, r=0.5, a = 0.1,0.2, • • • 0.5, K = 100,120, • • •, 300, T = 1,2 average of E 200 average of Ew 50 average of E 20 0.37 0.46 0.51 B  w  Chapter  4.  Option  Pricing  30  Table 4.6: A m e r i c a n P u t : 50 nodes 20 time steps willow tree vs 200 time steps b i n o m i a l tree C P U time for 400 calculations cycle per sec 1000000 W i l l o w Tree C P U cycles start load time W T 0 load time end load time W T 140000 140000 start time W T 2550000 load time & calculations end time W T C P U cycles B i n o m i a l Tree start time B T end time B T  4330000 31880000  calculations  C P U time (sec) 0.1400 2.5500 C P U time (sec) 27.5500  Chapter 5  Extension  5.1  Extension to other models  T h e setup of willow tree for pricing vanilla options can be easily extended to models on equity w i t h dividend payments and some other type of options. We give a list of some of the modifications. • E q u i t y w i t h continuous dividend payments : Adjust the spot values at each node by the discount factor e~  qAt  where q is the  dividend rate. • E q u i t y w i t h discret dividend payments : Adjust the spot values by the dividend payments at the nodes correponding to the payment schedule. • Barrier Options : Use a n interpolation on the lower and upper boundaries expections. For example, consider a single down and out barrier w i t h barrier B. S*£.\ and S£j. < B < S £ j .  + 1  A t tk+i, let S^  +1  For z < ra*, we compute ra—1 J=l  TO i=i  We define Vl  k  by an interpolation between  31  and V^£ . p  < B <  Chapter  5.  32  Extension  • B u r m u d a n Options : In the willow tree setup, the set of discrete time nodes used must contain the a l lowable exercise dates as a subset. In the iterative procedure for calculating V f , fc  apply (79) on the allowable exercise dates and apply (66) on the non-allowable exercise dates. Note that between two time nodes which are adjacent to the allowable exercise dates and have no allowable exercise dates i n between, the iterative procedure is E u r o p e a n and only one time step calculation is needed. It is an interesting problem to determine the m i n i m u m number of non-uniform time steps needed for the calculation when using transition matrices calculated from uniform time steps w i t h A t = 1 day. • T w o factor models : In a two factor stochastic model, the B r o w n i a n motion is two dimensional. Let p be the instantaneous correlation between the components Bi(t)  a n d E>2(t). T h e  second component B<i(t) can be constructed from two independent one dimensional B r o w n i a n motions Bi(t)  and B$(t)  where  B {t)=pB (t)-Jl^fiB {t). 2  1  z  (81)  Thus to set up the corresponding W i l l o w Tree for the B r o w n i a n motion, one can use a three dimensional grid where at each time node tk, the two dimensional grid (y/Uz ,py/tkZ m  - \ / l - p' yftk~Zm) is a discretized version of a two dimensional 2  m  B r o w n i a n motion. Similar constructions can be used for higher dimensional willow tree setups. • Deterministic time dependent instantaneous volatility : Suppose the instantaneous volatility o(t) is deterministic and time dependent. T h e willow tree setup accommodates a(t) by replacing Yk = y/h z w i t h Yk = yJ~L{t) z  33  Chapter 5. Extension  where E(t) = f  a (s)ds. 2  Js=0  Stochastic volatility : A more challenging extension of the willow tree setup is to construct a discrete process that incorporates implied volatility smile. Using the idea introduced by K l a u s Said [7], we can consider the two factor model  S dY X (K,T)  =  rdt+  ^/x(S,t)YdB  1  = ct{Y - Y)dt +  (VYdB  2  2  E[Y (T)\S(T) = K) 2  K  dK ' 2  where CK,T is the current value of a call o n S w i t h strike K a n d m a t u r i t y T. In a willow tree setup, i f one is able to solve for X(S,t)  recursively on a grid, then a  tree distribution of S can be determined. A s a result, after appropriate calibration on the parameter £, option prices can be determined from the tree distribution of  S.  5.2  Conclusion  We have presented the setup of a willow tree algorithm for calculating prices of vanilla options. F o r better accuracy on a larger class of options, a good choice of the discrete approximation of the standard normal distribution used i n the setup is calibrated by using a n equal partition of on an interval of the variate z.  F r o m the results of the  numerical calculation, the speed performance of the willow tree is much superior to the binomial tree. T h e superority will even be more extensive for multi-factor models.  J  Chapter  5.  Extension  34  F u r t h e r extensions of the setup can be applied to other options. In particular, m o r e is r e q u i r e d if o n e w o u l d like t o c o n s i d e r a m o d e l t h a t i n c o r p o r a t e s s t o c h a s t i c a n d is c o n s i s t e n t w i t h t h e m a r k e t v o l a t i l i t y s m i l e .  work  volatility  Bibliography  [1] Baxter, M a r t i n and Rennie, A n d r e w , 1996, F i n a n c i a l calculus : an introduction to derivative pricing, Cambridge University Press, Cambridge ; New Y o r k , N Y . [2] Black, F . and M . Scholes, 1973, The pricing of options and corporate laiabilities, Journal of Political Economy 3, 637-654. [3] M i c h a e l C u r r a n , June 1, 1998, W i l l o w Power, Riskcare, L i m i t e d , L o n d o n , E n g l a n d . [4] C o x , John C . and Ross, Stephen A . and Rubinstein, M a r k , 1979, O p t i o n P r i c i n g : A simplified A p p r o a c h , Journal of F i n a n c i a l Economics 7, 229-263. [5] Dewynne, Jeff and Howison, S a m and W i l m o t t , P a u l , 1997, The Mathematics of F i n a n c i a l Derivatives, Cambridge University Press, Cambridge ; New Y o r k , N Y . [6] G r i m m e t t , G . R . and Stirzaker D . R . , 1995, P r o b a b i l i t y and R a n d o m Processes, Oxford University Press Inc. New York. [7] Said, K l a u s , N o v 1999, P r i c i n g exotics under the simile, Risk, 72-75.  35  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080017/manifest

Comment

Related Items