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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Willow tree
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Willow tree Ho, Andy C.T. 2000
pdf
Page Metadata
Item Metadata
Title | Willow tree |
Creator |
Ho, Andy C.T. |
Date Issued | 2000 |
Description | 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. |
Extent | 1494640 bytes |
Subject |
Options (Finance) -- Prices -- Mathematical models Derivative securities -- Mathematical models |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-07-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080017 |
URI | http://hdl.handle.net/2429/10625 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2000-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
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
Cite
Citation Scheme:
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>
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