W I L L O W T R E E B y A n d y C . T . Ho B . Sc. (Mathematics) Simon Fraser University M . Sc. (Mathematics) University of Br i t i sh Columbia P h . D . (Mathematics) University of Br i t i sh Columbia A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S M A T H E M A T I C S We accept this thesis as conforming to the required standard 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 M a y 2000 © A n d y C . T. Ho, 2000 UBC Special Collections - Thesis Authorisation Form Page 1 of 1 I n 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 o f t h e r e q u i r e m e n t s f o r an advanced degree 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 agree 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 agree 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 by t h e head 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 c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n 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 olumbia Vancouver, 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. i i Table of Contents Abstract ii List of Figures v List of Tables v i Acknowledgment vi i 1 Introduction 1 2 Binomial Tree 3 3 Wil low Tree 8 3.1 Basic Setup 8 3.2 Rank of constraint matrix 12 3.3 Convergence of the willow tree 17 4 Option Pric ing 21 4.1 European Opt ion 21 4.2 Cal ibrat ion of 22 4.3 Numerical Results for European Options 26 4.4 Numerical Results for American Option 27 i i i ( 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 20 4.2 Small variation of \Zi(.l) - zj(l)| ~ 10" 3 28 v List of Tables 4.1 European C a l l ; s ^ g • 26 \V°-V°A 4.2 European C a l l : Percentage of 1 " y U c / l 28 \v°-v° I 4.3 European Put : Percentage of 1 \ ^ 29 4.4 American Put : Percentage of ^ " J f ^ 0 0 ! 29 4.5 American Pu t : Average Percentage of ^ " J ^ 0 " 1 29 4.6 American Put : 50 nodes 20 time steps willow tree vs 200 time steps binomial tree 30 vi Acknowledgment I would like to acknowledge Professor Ulr ich Haussmann for his advice and support through out my Mathematical Finance Program in U B C . I would also like to thank my parents for their support and encouragement. vii Chapter 1 Introduction Since the celebrated option pricing model introduced by Black and Scholes [2] in 1973, Mathematical Opt ion pricing theory has undergone tremendous revolutionary develop-ment. The basis of many of these pricing models stems from incorporating random diffusion processes generated from Brownian motion to describe the stochastic dynamics of various quantities in 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 wi th respect to a random process. For most situations, because of the un-availability of closed form solutions, option prices can only be determined numerically. Among the many numerical approaches for option pricing models, a popular one is the binomial re-combining tree algorithms. This algorithm was first developed by Cox, Ross, and Rubinstein [4] in 1979. The binomial tree generates branches of paths of prices by bifurcating the prices recursively from one time step to the next. The 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 in 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 Curran [3] in 1998. The setup 1 Chapter 1. Introduction 2 of the willow tree is based on estimating the standard Brownian motion by a discrete Markov process. The transition probabilities are determined by solving a sequence of linear programming problems. These transition probabilities only need to be computed once and then they can be stored for future useage. From the Markov process, other more general processes can be constructed from suitable mappings. One distinct feature of the willow tree is that the number of nodes at each time step is constant. This is i n contrast to the binomial tree where the number of nodes grows as 0(M2) where M is the number of time steps. This feature of the willow tree allows the computation process to be very efficient even wi th a large number of time steps and this becomes especially advantageous for multi-factor models. The layout of this paper is as follows. Chapter 2 describes briefly the binomial tree algorithm. We show that under the setup for computing European Options, i t is equivalent to an 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 European and American vanilla options. Here, we wi l l only concentrate our study on vanil la options, but the result can easily be extended to many other types of options. We 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 than 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 Binomial Tree We would like to show that the binomial tree algorithm for computing European 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 European option price. Please see Chapter 10 of [5] for more details. Let denote the binomial tree discrete process where m is the time index and n is the node index. Starting wi th an in i t ia l stock price SQ, allow each stock price S™ to change into two possible prices cm+l „. cm qm+1 rlQm °n+l — U O n ) °n ~ 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. Continuing this process, we obtain a tree lattice of the price distribution. Because this a recombining tree, S™ = S°Qundm-n. (1) 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 , it is possible to show that the tree process converges to the Black Scholes (geometric Brownian motion) continuous process dS = S (rdt + adBt), (2) where r and a are the (risk-neutral) drift and instantaneous volati l i ty respectively, and Bt is the standard Brownian 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 = erSt (3) pu2 + (l-p)d2 = e(2r+°2)5t. (4) Because there are only two equations here, there is st i l l 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 erdt - d d = A-y/T^T, u = A+y/A^l, (5) where A = \ (e~r5t + e{r+°2)5t) . (6) Let F(S, T) be the contingent payoff function at expiry time T for an European option and V n m be values of the option on the nodes of a binomial tree wi th parameters p, u, d. A t time T = M6t, VnM = F(S?). (7) Chapter 2. Binomial Tree 5 The subsequent V™ are computed by iterating the formula fStyrn = pV™? + (1 - P)V™+1 e "i/m+l , " _^ T/m+1 *n+l ' ~ V " u — d 0r6t u — d u — d 0r5t i ^ n u — d (8) This setup of the binomial tree is actually equivalent to an explicit finite difference method. More explictly, let us consider the Black Scholes P D E of a European option wi th variables t, x = In S SV St T , 1 2S2V ( 1 2 \ SV . (9) where t is the time and S is the spot price of the underlying stock. B y wri t ing SV T / rt6e-HV rV — e St St ' (9) becomes ,Se~rtV 1 2S2V ( 1 . St sv Sx (10) We convert (10) into a finite difference equation by approximating the derivatives wi th finite differences (See Chapter 10 of [5]). The corresponding finite difference equation for (9) is •,-rU 1+1K m+1 _ grtmym 1 2 xn+\ t ym+1 _ ym+1 T/m+1 _ ym+ vn+l vn yn vn—l (11) m+1 2-n+l X r Xn — \ + ( r - - c r 2 ) 7 1 + 1 _ n 1 = 0, Z / 3^ n+l %n—\ where * m = mft, atf tf = logfiEff, C + 1 = l o g ^ + 1 > <-x = log S T (12) Chapter 2. Binomial Tree We would like to express the x's in terms of u, d. F rom (12) and (12), x n + 1 - x n = loguS™ - l o g 5 ^ = l o g u Xn-Xn-! = log S™ - log dS™ = - log d xn+x-xn-x = log u/d tm+1 tin = &t and <ft l ogw/d \ logw l o g d Further rearrangment gives where cm+i = °2&t {r - jo3) 6t n 1 l o g w / d l o g d \ogu/d \ogu/d \\ogu log ay 7 1 + 1 l o g u / d l o g d logw/d From comparing (13) wi th (8), we wish to show that p r < K — d Chapter 2. Binomial Tree 7 Let us expand A, u - 1, d - 1 in terms of 8t1/2. From (5-6), r 2 2 2 M - 1 = .4 - 1 + yfW^l = o8t1/2 + °—8t + 0{8t3'2) 2 d - l = A - l - V ^ l = -a8t1/2 + ^-8t + 0(8t3^2). Using the above and the expansion logo; — (x — 1) — (x — l ) 2 / 2 -\ , we have log u — log d = u-d + 0(8t3/2) logw = a8t1/2 + 0(8t3/2) l o g d = -a8t1/2 + 0(8t3^2). Subsituting the above into (16) yields ™ + i = oHt (r ~ k 2 ) ^ n + 1 (« - d ) ( l + 0(c5t))crc5i1/2(i + 0(8t)) (u-d)(l + 0(8t)) 1 + r«ft - (1 - aSt1'2 + %6t) + Q{8t^2) u — d er5t -d + 0(8t3/2) u — d Similarly, it is straight forward to show that = 1 ^ ( 1 + 0 ^ 1 / 2 ) ) C ™ ? = 0{8t3'2). We conclude the chapter by stating the equivalence of the two algorithms in the following theorem. Theorem 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 to the forward Euler Scheme applied to the corresponding Black Scholes differential equation. Chapter 3 Willow Tree 3.1 Basic Setup In setting up a willow tree lattice for modelling option prices, we first need to set up a discrete Markov process that converges to a Brownian motion in the l imi t . A more general process of a security can then be modelled from the Markov process under suit-able mappings (see Chapter 4). More specifically, let z\, z%, • • •, zn be the representative normal variates wi th corresponding probabilities qi, c^, • • •, qn, i-e., <&)} is a discrete approximation of the standard normal density function where Oj = P(Z = Zi). For example, Curran suggests a choice (see Figure 3.1): ^ = N-\(i-0.5)/n) (21) ft = 1/n where N(x) is the cumulative standard normal distribution function. Let Ytk be a discrete Markov process wi th time nodes tk = £ j = i hj, for some hi,h,2,-" with each hj > 0. Ytk takes on the value y/hZi when the embedded Markov chain Xk is in state i, 1 < i < n. We can view each realized sequence of Ytk as a path traversed on a tree lattice consisting of parallel layers of nodes. The 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 ini t ia l time t = 0, there is only one node corresponding to state 0 wi th the transition probabilities being p§i = Qi-8 Chapter 3. Willow Tree 9 Sample paths on a willow tree We wish to make Ytk converge to a Brownian motion Bt in the l imit n —> co and hk —>• 0. We first impose the following conditions on p^: IZP% = 1 V * (22) j=i f^Pij^k + hkZj = yftkZi V i (23) j=i £ p% (tk + hk)z] - tkz\ = hk V i (24) j=i E?4 = ^ V j (25) i=l P & > 0 V t , j . (26) The first condition (22) is just the statement that sum of the conditional probabilities at a node should be unity. The second condition (23) constrains the conditional mean E[Ytk+hk\Ytk}=Ytk \/tk,hk (27) which corresponds to the first moment of dBt being zero. Similarly, the th i rd condition (24) constrains the conditional variance Var[Ytk+hk\Ytk]=hk Vtk,hk (28) Chapter 3. Willow Tree 10 which corresponds to the second moment of dBt equal dt. We impose the condition (25) so that the unconditional probability of ending at node i at time tk is qiy i.e., by induction and (25) jlJ2—jk-l jk-i Hence {qt} is a stationary distribution, i.e. {Xk} is stationary. In order to further narrow down the choice of the transition matrices a n c i to ensure that the convergence is sufficiently fast, for each k, the are determined from the following linear programming problem. E^EpJ-lA + ^ i - vW (29) Subject to EPij = 1 W (30) j=i ^ P t f V*fc + hkZj = yftkZi Vz (31) j=l f; Py (** + hk)z] - t f c «? = fcfc V i (32) j=i E?iP6 = ^ y 7 (33) t=i rfj>0Vx,j. (34) Essentially, we match the first two moments of dBt and we require the th i rd power of 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 distr ibution {zi,qi} must have mean = 0 and variance = 1. For convenience, let us drop the fc's and introduce the following notation: Chapter 3. Willow Tree • v1 is the transpose of a matrix v • P is the n x n transition matrix wi th entries Pij • F is the matrix wi th entries Fji = \ZJ - bzi\3 h , 1 a = - o = t Vl+a In terms of the above notation, the L P becomes nun trace (PF) Subject to : Pu = u Pz = bz p r = b2r + (1 - b2) q lP = (f p^ > 0 According to constraints (37) and (39), q tz = q lPz = bq lz. Since 6 ^ 0 , this implies that z has mean = 0, i.e., Chapter 3. Willow Tree 12 Similarly, from (36), (38), and (39) qtr = b2qtr + (l-b2). Since a ^ 0, this implies that z has variance = 1, i.e. gV = 1. (42) The choice of q and z suggested i n (21) meets the mean = 0 requirement (41) but fails the variance = 1 requirement (42). However, there are at least two modifications for allowing the suggested q and z to satisfy both requirements. The first one is to use a non-standard normal distribution AT £ (0 ,1 + e) wi th mean = 0 and variance = 1 + e for some appropriate e so that Zi = Ar e - 1 ( ( z - 0.5)/n) satisfies (42). The second one is to modify only the two end points z\ and zn as z\ — 8 and zn + S so that (42) is true for an 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 in terms of a matr ix equation. Let 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 and the second n entries correspond to second column and so on. In terms of v, the L P can be stated as min fv V (43) Subject to : Mv = w (44) Vi > 0 V i (45) where / is a vector wi th positive entries. Chapter 3. Willow Tree 13 Let {zi, qi} be an approximation of the standard normal distribution wi th mean = 0 and variance = 1 such that a = {u, z, r} as described in 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 n where 0i = u, 02 = z, 03 = r. In selecting 0, we require that Si = span of {040s, 0e, • • • ,0n} is orthogonal to 52 = span of {0i,02,0s}- Let T be the matrix that transforms 0 into the standard basis E = {ei , • • • , e„} and S = T~lPT. We wi l l show that S has n 2 — (An — 3) degree of freedom i n choosing its entries and hence the rank of M must be in — 3. £2 can be constructed explicitly in the following way. Let a = {0i, • • • ,0m} be a linear independent set and A =[0i 02 ••• 0m] be the matr ix consisting of the vectors in a. From a QR-decomposition, A = Q (46) C 0 (47) where C is a m x m full ranked upper triangular matrix. Using the matr ix Q, we let B = Q 0 In—m C " 1 0 0 In-Q-(48) (49) where In-m 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 Q-1 C 0 Q Q 0 In—rn 0 ln—m Chapter 3. Willow Tree 14 0 = In-0 In-m _ For the orthogonality property, we use the fact that Q is hermitian, i.e., Q - 1 = Q*. Let cij € a and bi be the columns of B. Then = <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 v e c t o r o f C 0 We now show that S — TPT 1 has n2 - (An - 3) degrees of freedom. Using the basis (3, the L P (35-40) can be restated as the following problem: Subject to min trace (SG) Se\ = e i Sea = be2 Se3 = b2e3 + (1 - b2)ei q'S = qf (T-XST).. > 0 V i , j (50) (51) (52) (53) (54) (55) Chapter 3. Willow Tree 15 where G = TFT"1 and q = ( T _ 1 ) V From the above, S must be of the form 1 0 (1 - 6 2) * * • • * * 0 b 0 * * • • * * 0 0 b2 * * • • * * 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. We first suppose that q G Span of {u, z,r}. From the definition of q ft = e\q = ftT-yq = ( T " 1 * ) ^ = fiq. (57) Hence, by our choice of /?, q* = ( a i , a 2 , a 3 , 0 , 0 , 0 , •••,()) (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 2 ) 5 1 4 Sis 0 6 0 S24 S25 0 0 0 0 0 0 0 0 0 0 b2 0 0 0 0 S34 535 : * * * * * Sl(n-l) -Sin S2(n-1) S^n 53(n-l) Szn * * (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. For the case q not in the span of {u,z,r}, we may choose /?4 so that q is in the span {u, z,r,p4}. Then g* = (1 ,0,1, ^ f t , 0 ,0 . - - - , 0 ) , (60) and we have sij + S3j + q1^^^ = 0 i f j > A and Su + «34 + <7*/?4S44 = <7*/?4 i f j = A. Result follows. We summarize our discussion on the rank of the matr ix 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 in the L P problem, there is a further nonnegative constraint (45) on v in addition to the linear equation (44). Thus an 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) and (45) wi th only An - 3 non-trivial values. Thus at each node, on average, Chapter 3. Willow Tree 17 there are only 4 moves that have non-trivial probability. The low density of the transition matrices gives a very high efficiency in calculating expectations wi th respect to these transition probabilities. 3.3 Convergence of the willow tree We don't have a proof for the convergence of Ytk to a Brownian 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. Theorem 3.1 Central Limit Theorem Let X\, Xi, be independent variables satisfying 2 T?\v2\ and following : EXj = 0,var(Xi) = a],E\X]\ < oo 1 M Y,E\X?\->0 asM-+oo where Then M 1 M 5>j->Jv(ofi) in distribution where N(p, cr2) is the normal distribution with mean // and variance cr2 Chapter 3. Willow Tree 18 The criterion for a process being a Brownian motion is the following (page 176 of [6]): 1. I t is (almost surely) continuous, 2. the increment Ys+t — Ys is distributed as a normal N(0, t) and is independent of TB, the history up to s, s > 0. To show that Ytk converges to Brownian motion, we would like to show that i n the l imit , Y satisfy the above two conditions. For the first condition, we require (Kolmogorov) E\Ys+h — Ys\3 < Kh1+e for some K < oo and e > 0. As for the second condition, we would t ry to use the Central L i m i t theorem to show that Ys+t - Ys is normal and independent Now let us compute the mean and variance for each of the I^+Q+IJA* — Ys+j&t- F rom of Ts. Let us write Ys+t — Ys as a telescoping sum (30-31) E\Ys+(j+i)&t — Ys+jAt] = 0, Chapter 3. Willow Tree 19 From (30-33) and the fact that the mean is zero, var(Ys+{j+i)&t - Ys+jAt) E[(Ys+(j+i)&t - Ys+jAt)2] E <?iPij [Zj\/s + (J + - z^s+jAt = zZQi{2zi(s + jAt) + At-2zUs + jAt)) i = A*E& i = At. This implies that a(M) = t1/2. The last thing we need to show is that E[\Y3+(j+1)At - Ys+jAt\3] < K\At\1+£ as M ->• oo and n, the number of spatial nodes, -> oo. This suffices for condition 1 and it also implies Since (29) is just E[\Y3+^+^At - Ys+jAt\3], so the minimization produces the smallest possible values of E[\Y3+(j+i)At — Y3+j&t\3]- Hence we expect the following conjecture to be true. C o n j e c t u r e 3.1 Let {zi(n),qi(n)} be some "reasonable" choices of discrete approxi-mations of the normal distribution such that the corresponding transition matricespfj(n, M) ofYtk(n,M) satisfy the LPs specified by (35-40). Then there exists n(M) such that in the limit M —>• oo and n(M) —>• oo, Ytk converges to Brownian motion. 1 M - l C T ( M ) 3 E E[\Ys+u+1)At - Y3+jAt\3} < Kt-^\At\e -+ 0. (61) i=0 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 distr ibution Chapter 4 Option Pricing 4.1 European Option A n equity following the Black Scholes continuous process defined i n (2), under a mart in-gale measure (see Chapter 3 of [1]), has the same spot price distributions as S(t) = S(0)e {r-£ )tk+°Bt. (62) Because we conjecture that the tree distribution Ytk constructed i n Chapter 3 converges to the Brownian motion Bt, the distribution of equity prices should converge to the distribution of (62) in the l imit . A standard technique for calcu-lating an European option on S(t) given by (62) wi th payoff F(S(T)) at terminal time T uses the conditional expectation wi th respect to the distribution (62). Let V f be the value of the option at time t. Then V1 = E[e- rTF(S(T))\S(t)]. (64) In a willow tree setup, as in a binomial tree estimation, V° is estimated by iteratively taking conditional expectations with respect to the transition probabilities. The terminal condition at expiry T is = ns^- (65) 21 Chapter 4. Option Pricing 22 The subsequent V^k are calculated iteratively using the formula M ytk = e - r ( t k + 1 - t f c ) J2 P^V-k+1, n > 1. (66) j=i A t the home node, N Vo = e - n 1 j 2 q j v ^ . (67) From (39) V° = e - r ^ i t k + 1 - t k q ' P 1 P 2 - - - P M F ( S T ) = e-rTqJF(ST) (68) where q1 denotes the tranpose of q and F(ST) 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. This 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 Calibration of {zi,qi} There are many ways of choosing {zi,qi} in a willow tree setup. We calibrate a choice by comparing (68) for a call wi th its corresponding closed form solution for (64). Let us consider an European call wi th strike K. The closed form solution for the price of the call is V?f = ^ -r= f (l5Vr-1r)rWT* - K) e-^dz (69) where s ._hsS-(r - f l r ( 7 0 ) Csff Chapter 4. Option Pricing 23 For a given {zi, <&}, the willow tree solution (68) is then K = e-rTJ2Qi(s°e(r~^)T+<TVTzi-K) i=i* ^ ' = £ _ W * ( 5 0 e ( r - ^ ) T W T 2 i _ K \ e - ^ d z ( 7 1 ) where i* is the minimum of the index i such that Z{ > z* and qt = —== / e 2 dz. Comparing (69) and (71), it is easy to see the error V° - V°f is where E o = f eh*') e~$dz Ei = (fZi - e^z) e-^dz (72) 0 = aVT. Note that except for E0, the other Ei have no dependence on the strike K. We would like to pick the discrete approximation {zi,qi} so the absolute difference between Vc° and is small. Let a > 0 be the a number so that (•-a+Az /- a - t - / 3 2 ,2 e?ze~dz = o(l/N3) -oo / e?'e-*rdz = o(l/JV 3) Ja-Az and Az = 2a/N. We set the ft in the following manner. c-o+Az R 2 e~~*dz -oo ftv = / e 2 dz. Ja—Az Chapter 4. Option Pricing 24 For 2 < i < N—l, we parti t ion [—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 in 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@Zi as eP*+ {3e/3z(zi-z) + 0(eIBz(Az)2) (74) and by (72), for i* < i < N - 1, we have \Ei\ = JA(pe0z(zi-z) + O(p2el3z(Az)2))e-^dz < (pAz + 0((12(Az)2)) f e?ze-$dz. The same argument works for \E0\. This implies that „-/3 2 /2c0 -oo 2 |J571 < _ (pAz + 0(P2(Az)2)) / e?ze-*dz + 0 ( l / i V 3 ) V27T V ' Jz* and |£| = _ _ \E\ Vcf ^ J~ (so e<r-4)rWfc _ ^ e - $ d z ^ff- (PAz + Q ( / ? 2 (A*) 2 ) ) / ~ e ^ d s 0 ( 1 / i V 3 ) _ „C!/o .2 "I" Cf < ((3Az + 0(p2(Az)2)) + Q(l/N3) Hence if IK / I > l / i V 3 / 2 (75) Chapter 4. Option Pricing 25 then "cf (76) For example, N = 50, a = 5, 0 = .1, ^vfi ] ~ .01. Actual ly, we can get a tighter bound for the case where Zi{0) vary slowly for a range of 0 . F rom (72), we can solve for a Zi(0) so that Ei = 0. Zi{0) = ^ l o g z2 ( 1 S'(eP'e-4dz\ (77) 2TT 1 (ePPfJ e a d* » ± l0cr _ f» 0 ° \V2t Qi £ + log ^w- f l+N(«{ - f l j B y choosing the Zj(/?) for a particular 0, it is easy to see that (72) can be writ ten as jf ( e ^ - e ^ ) e - ^ d z . Expanding the Zi(0) at 0, Hence, if \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 - 3 . In fact, for the given range of parameters, \zi(0) — Zi(0)\ ~ 1 0 - 3 . This implies that for \V^\ > .003, the 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 parti t ion of q in (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 part i t ion of an interval of z w i l l be accurated for a much wider range of payoff functions. 4.3 Numerical Results for European Options We compare the results of European and American 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 Vw of European Opt ion C a l l and Pu t computed from the willow tree setup to the values VCf obtained from the closed form solution. In Table 4.2-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 than 1%, the corresponding closed form solution of the calls is unrealistically small wi th value < 1 0 - 5 . For a l l the other values, the error is always wi th in 1%. In Table 4.3, since the range of parameters used Table 4.1: European Ca l l : T = l , r=0.6, M = Moneyness(= cr = Volat i l i ty 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.3 0.0000 0.0000 0.0001 0.0010 0.0033 0.0076 0.0138 0.0216 0.0308 0.4 0.0000 0.0001 0.0014 0.0053 0.0123 0.0220 0.0339 0.0474 0.0619 0.5 0.0000 0.0013 0.0065 0.0164 0.0300 0.0461 0.0639 0.0829 0.1024 0.6 0.0006 0.0065 0.0193 0.0369 0.0575 0.0798 0.1032 0.1269 0.1509 0.7 0.0049 0.0206 0.0427 0.0681 0.0950 0.1227 0.1506 0.1784 0.2060 0.8 0.0202 0.0478 0.0783 0.1099 0.1418 0.1736 0.2051 0.2362 0.2667 0.9 0.0543 0.0902 0.1260 0.1616 0.1969 0.2316 0.2658 0.2993 0.3321 1 0.1099 0.1472 0.1847 0.2221 0.2592 0.2957 0.3317 0.3670 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. Option Pricing 27 4.4 Numerical Results for American Option The formula for calculating a vanilla American 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 V f = F(S?). (78) The subsequent V£k are calculated iteratively using the formula ytk = e-r(tk+1-tk) 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 American put. In Table 4.4, we see that other than the values corresponding to put wi th unrealistic value 0.023, all the other 50 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 : Spot=200, r=0.5, a = 0.1,0.2, • • • 0.5, K = 100,120, • • •, 300, T = 1,2. We see that on average, the 50 time steps willow tree is more accurate than the 200 time steps binomial tree. Las t ly 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 and 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 Ca l l : Percentage of w v 6 c } T = l , r=0.6, M = Moneyness, a = Volat i l i ty M / C T 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.3 100 1.5927 0.0696 0.2202 0.9789 0.7266 0.5118 0.4824 0.2242 0.4 3.9274 1.7901 0.0941 0.4644 0.3897 0.4410 0.2592 0.4446 0.1702 0.5 0.5701 0.0853 0.6927 0.6301 0.1908 0.0460 0.3746 0.1224 0.1018 0.6 0.0065 0.1393 0.3119 0.1243 0.0780 0.3299 0.1823 0.0798 0.0748 0.7 0.6478 0.0614 0.0096 0.1412 0.2847 0.2095 0.1839 0.2040 0.2199 0.8 0.4463 0.5237 0.2607 0.1997 0.1715 0.1945 0.2017 0.1355 0.0434 0.9 0.1314 0.3782 0.2327 0.0081 0.1465 0.1609 0.0017 0.3202 0.0204 1 0.1116 0.0332 0.0316 0.0636 0.1417 0.0382 0.0948 0.1314 0.0698 Chapter 4. Option Pricing 29 \V°—V° Table 4.3: European P u t : Percentage of \ a c ' T = l , r=0.6, M = Moneyness, a = Volat i l i ty M / c r 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.3 6.E-09 6.E-08 4.E-08 2.E-06 3.E-05 6.E-05 7.E-05 l .E-04 7.E-05 0.4 2.E-08 2.E-06 l .E-06 2.E-05 5.E-05 l .E-04 9.E-05 2.E-04 l .E-04 0.5 2.E-07 l .E-06 5.E-05 l .E-04 6.E-05 2.E-05 2.E-04 l .E-04 l .E-04 0.6 2.E-06 9.E-06 6.E-05 5.E-05 5.E-05 3.E-04 2.E-04 l .E-04 l .E-04 0.7 3.E-05 l .E-05 4.E-06 l .E-04 3.E-04 3.E-04 3.E-04 4.E-04 5.E-04 0.8 9.E-05 3.E-04 2.E-04 2.E-04 2.E-04 3.E-04 4.E-04 3.E-04 l .E-04 0.9 7.E-05 3.E-04 3.E-04 l .E-05 3.E-04 4.E-04 5.E-06 l .E-03 7.E-05 1.0 l .E-04 5.E-05 6.E-05 l .E-04 4.E-04 l .E-04 3.E-04 5.E-04 3.E-04 Table 4.4: American Put : Percentage of '^JfooQ 0 0 ' Spot=200, r=0.5, a = Volati l i ty, K = Strike, T = Matur i ty i n years, Vw N = Value of Put using Wi l low Tree wi th N time steps VB N = Value of Put using Binomial Tree wi th 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 a K T VB 1000 VB 200 Vw 50 Vw 20 EB 200 Ew 50 Ew 20 0.5 300 1 106.931 106.911 106.958 106.993 0.0188 0.0256 0.0579 0.3 260 1 61.787 61.779 61.783 61.772 0.0136 0.0064 0.0252 0.2 220 1 23.942 23.931 23.936 23.926 0.0462 0.0239 0.0681 0.5 180 1 24.632 24.560 24.623 24.669 0.2915 0.0383 0.1507 0.2 120 1 0.023 0.023 0.022 0.022 2.1329 4.6582 4.6582 0.4 280 2 89.848 89.843 89.852 89.850 0.0057 0.0049 0.0025 0.2 240 2 41.363 41.354 41.310 41.211 0.0216 0.1283 0.3677 0.1 200 2 5.755 5.760 5.720 5.665 0.0986 0.6105 1.5540 0.3 180 2 16.679 16.663 16.680 16.701 0.0939 0.0088 0.1346 0.2 140 2 1.089 1.086 1.086 1.088 0.2494 0.2239 0.0867 Table 4.5: American Pu t : Average Percentage of ^ V v ^ ° ° 0 ^ Spot=200, r=0.5, a = 0.1,0.2, • • • 0.5, K = 100,120, • • •, 300, T = 1,2 average of EB 200 average of Ew 50 average of Ew 20 0.46 0.37 0.51 Chapter 4. Option Pricing 30 Table 4.6: Amer ican P u t : 50 nodes 20 time steps willow tree vs 200 time steps binomial tree C P U time for 400 calculations cycle per sec 1000000 W i l l o w Tree C P U cycles C P U time (sec) start load t ime W T 0 end load time W T 140000 load time 0.1400 start time W T 140000 end time W T 2550000 load time & calculations 2.5500 Binomia l Tree C P U cycles C P U time (sec) start t ime B T 4330000 end time B T 31880000 calculations 27.5500 Chapter 5 Extension 5.1 Extension to other models The setup of willow tree for pricing vanilla options can be easily extended to models on equity wi th dividend payments and some other type of options. We give a list of some of the modifications. • Equi ty wi th continuous dividend payments : Adjust the spot values at each node by the discount factor e~qAt where q is the dividend rate. • Equi ty wi th discret dividend payments : Adjust the spot values by the dividend payments at the nodes correponding to the payment schedule. • Barrier Options : Use an interpolation on the lower and upper boundaries expections. For example, consider a single down and out barrier with barrier B. A t tk+i, let S^+1 < B < S*£.\ and S£j. < B < S £ j . + 1 For z < ra*, we compute ra—1 J=l TO i=i We define Vlk by an interpolation between and V^£ p. 31 Chapter 5. Extension 32 • Burmudan Options : In the willow tree setup, the set of discrete time nodes used must contain the al-lowable exercise dates as a subset. In the iterative procedure for calculating Vf f c , apply (79) on the allowable exercise dates and apply (66) on the non-allowable ex-ercise dates. Note that between two time nodes which are adjacent to the allowable exercise dates and have no allowable exercise dates in between, the iterative proce-dure is European and only one time step calculation is needed. It is an interesting problem to determine the minimum number of non-uniform time steps needed for the calculation when using transition matrices calculated from uniform time steps wi th A t = 1 day. • Two factor models : In a two factor stochastic model, the Brownian motion is two dimensional. Let p be the instantaneous correlation between the components Bi(t) and E>2(t). The second component B<i(t) can be constructed from two independent one dimensional Brownian motions Bi(t) and B$(t) where B2{t)=pB1(t)-Jl^fiBz{t). (81) Thus to set up the corresponding Wi l low Tree for the Brownian motion, one can use a three dimensional grid where at each time node tk, the two dimensional grid (y/Uzm,py/tkZm - \ / l - p'2yftk~Zm) is a discretized version of a two dimensional Brownian motion. Similar constructions can be used for higher dimensional willow tree setups. • Deterministic time dependent instantaneous volatili ty : Suppose the instantaneous volatili ty o(t) is deterministic and time dependent. The willow tree setup accommodates a(t) by replacing Yk = y/h z w i th Yk = yJ~L{t) z Chapter 5. Extension 33 where E(t) = f a2(s)ds. Js=0 Stochastic volatil i ty : A more challenging extension of the willow tree setup is to construct a discrete process that incorporates implied volatili ty smile. Using the idea introduced by Klaus Said [7], we can consider the two factor model = rdt+ ^/x(S,t)YdB1 X2(K,T) S dY = ct{Y - Y)dt + (VYdB2 E[Y2(T)\S(T) = K) K dK2' where CK,T is the current value of a call on S wi th strike K and maturi ty T. In a willow tree setup, if one is able to solve for X(S,t) recursively on a grid, then a tree distribution of S can be determined. As a result, after appropriate calibration on the parameter £, option prices can be determined from the tree distribution of S. 5.2 C o n c l u s i o n We have presented the setup of a willow tree algorithm for calculating prices of vanilla options. For better accuracy on a larger class of options, a good choice of the discrete approximation of the standard normal distribution used in the setup is calibrated by using an equal parti t ion of on an interval of the variate z. From the results of the numerical calculation, the speed performance of the willow tree is much superior to the binomial tree. The superority wil l even be more extensive for multi-factor models. J Chapter 5. Extension 34 F u r t h e r e x t e n s i o n s o f t h e s e t u p c a n b e a p p l i e d t o o t h e r o p t i o n s . I n p a r t i c u l a r , m o r e w o r k i s r e q u i r e d i f o n e w o u l d l i k e 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 v o l a t i l i t y a n d i s 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 . Bibliography [1] Baxter, M a r t i n and Rennie, Andrew, 1996, Financial calculus : an introduction to derivative pricing, Cambridge University Press, Cambridge ; New York , N Y . [2] Black, F . and M . Scholes, 1973, The pricing of options and corporate laiabilities, Journal of Pol i t ical Economy 3, 637-654. [3] Michael Curran, June 1, 1998, Wi l low Power, Riskcare, L imi ted , London, England. [4] Cox, John C . and Ross, Stephen A . and Rubinstein, Mark , 1979, Opt ion Pr ic ing: A simplified Approach, Journal of Financial Economics 7, 229-263. [5] Dewynne, Jeff and Howison, Sam and Wi lmot t , Paul , 1997, The Mathematics of Financial Derivatives, Cambridge University Press, Cambridge ; New York, N Y . [6] Grimmett , G . R. and Stirzaker D . R. , 1995, Probabil i ty and Random Processes, Oxford University Press Inc. New York. [7] Said, Klaus , Nov 1999, Pr ic ing 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 |
FileFormat | 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 |
GraduationDate | 2000-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | 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