inner barrier is the true
harricroarricr,
2! The procedure we describe here is similar to that in E. Derman, 1. Kani, D. Ergener, and [ Bardhan, “EnhancedNumerical Methods for Options with Barriers,’ Working Paper, Goldman Sachs, May 1995.More on Models and Numerical Procedures 471
2. Calculate the value of the derivative on the assumption that the outer barrier is the truebarrier.
3. Interpolate between the two prices. ”
The method can be generalized to situations where there is more than one barrier and to situationswhere the barriers are nonhorizontal.
The Adaptive Mesh Model
The methods we have presented so far work reasonably well when the initial asset price is not closeto a barrier. When the initial asset price is close to a barrier, the adaptive mesh model, which weintroduced in Section 18.5, can be used.?* The idea behind the model is that computationalefficiency can be improved by grafting a fine tree on to a coarse tree to achieve a more detailedmodeling of the asset price in the regions of the tree where it is needed most.
To value a barrier option, it is useful to have a fine tree close to the barriers. Figure 20.7illustrates the design of the tree. The geometry of the tree is arranged so that nodes lie on thebarriers. The probabilities on branches are chosen, as usual, to match the first two moments of theprocess followed by the underlying asset.
The heavy lines in Figure 20.7 are the branches of the coarse tree. The light solid lines are the
 
 
Figure 20.7 The adaptive mesh model used to value barrier options
® See S. Figlewski and B. Gao, “The Adaptive Mesh Model: A New Approach to Efficient Option Pricing,” Journalof Financial Economics, 53 (1999), 313-51.472 CHAPTER 20
fine tree. We first roll back through the coarse tree in the usual way. We then calculate the value atadditional nodes using the branches indicated by the dotted lines. Finally we roll back through thefine tree.
20.8 OPTIONS ON TWO CORRELATED ASSETS
 
Another tricky numerical problem is that of valuing options dependent on two assets whoseprices are correlated. (These are sometimes referred to as rainbow options.) A number ofalternative approaches have been suggested. Three of these approaches are presented in thissection.
Transforming Variables
It is relatively easy to construct a Wee in three dimensions lo represent the movements of twouncorrelated variables. The procedure is as follows. First, we construct a two-dimensional tree foreach variable. We then combine these trees into a single three-dimensional tree. The probabilitieson the branches of the three-dimensional tree are the product of the corresponding probabilities onthe two-dimensional trees. Suppose, for example, that the variables are stock prices S, and 5.Each can be represented in two dimensions by a Cox, Ross, and Rubinstein binomial tree. Assumethat S, has a probability p; of moving up by a proportional amount u, and a probability | — p; of
maving down 6 ; 1 td, Qa ncn Comber that © hasa aeahahihty 5. af movingMoving aown GY a Proporidhal aMOouNt aq. Suppose (UTIET idl 47 NaS a Prooaonity p>. oF Moving
up by a proportional amount uz and a probability 1 — p) of moving down by a proportionalamount dy». In the three-dimensional tree there are four branches emanating from each node. Theprobabilities are:
Pipy: §) increases; 3) iucreases.
pil — pr): S| increases; S, decreases.
(i — p)p2: S; decreases; S increases.
(1 = p;) — px): +S, decreases; S, decreases.
Consider next the situation where S, and S, are correlated. We suppose that the risk-neutralprocesses are:
dS, = (r — q1)S, dt + 0S, dz), Sy = (r — qo) 82 dt + 0S, dz2and the instantaneous correlation between the Wiener processes dz, and dz, is p. This means thatdin S; =(r-—q, — 07/2) dt +0) dz, din Sy = (r — q) — 03/2) dt + oy dyWe define two new uncorrelated variables:x; =o0,InS, +o, In $3, . x2 =o,InS,—o,InS,
3 ‘This idea was suggested by J. Hull and A. White, “Valuing Derivative Securities Using the Explicit FiniteDifference Method,” Journal of Financial and Quantitative Analysis, 25 (1990), 87-100.More on Models and Numerical Procedures 473
These variables follow the processes
dx, = [ar — gy — of /2) + o1(r— gy — 03 /2)] dt + 0099/20 + p) dzydry = [ox(r — gy — 01/2) — 017 — qn — 03/2) dt + 710/20 = p) deg
where dz, and dz, are uncorrelated Wiener processes.
The variables x, and x. can be modeled using two separate binomial trees. In time ét, x; has aprobability p; of increasing by 4; and a probability 1 — p; of decreasing by h;. The variables h;and p; are chosen so that the tree gives correct values for the first two moments of the distributionof x; and x.. Because they are uncorrelated, the two trees can he combined into a single three-dimensional tree, as already described.
At each node of the tree, S, and S; can be calculated from x, and x) using the inverse
relationships_ x, + X2 _ xX 7 X2s,= exp (SR ) and S)= exp( 5 )
2 o|
 
The procedure for rolling back through a three-dimensional tree to value a derivative is analogousto that for a two-dimensional tree.Using a Nonrectangular Tree
Rubinstein has suggested a way of building a three-dimensional tree for two correlated stock pricesby using a nonsreciangular arrangement of the nodes.’* From a node (5}, Sy) where the first stockprice is S; and the second stock price is S,, we have a 0.25 chance of moving to each of thefollowing:(Sjuj, SA), (Syui, SB), (Sid,, S.C), (Spd;, S,D)whereuy = expl(r — qi — 97/2) dt +0, V8]
dy = expl(r — q) — 0/2) 8t — 0) V8t]
A = expl(r — qo — 03/2) 8t + a,V8t(0 + V1 — p*)]B = expl(r — 2 — 03/2) 8t + o7Vt(p — V1 — p*)IC = expl(r — g2 — 03/2) 5t — oV8t(p - V1 PID =expl(r — q — 03/2) 8t — 0,V8t(p + V1 — p*)]
When the correlation is zero, this method is equivalent to constructing separate trees for 5S, and Syusing the alternative binomial tree construction method in Section 18.5.
 
 
Adjusting the ProbabilitiesA third approach to building a three-dimensional tree for S$, and S) involves first assuming no
correlation and then adjusting the probabilities at each node to reflect the correlation.”> We use the
4 See M. Rubinstein, “Return to Oz,” RISK, November 1994, pp. 67-70.
3 This approach was suggested in the context of interest rate trees by J. Hull and A. White, “Numerical Proceduresfor Implementing Term Structure Models HW: Two-Factor Models,” Journal of Derivatives, Winter 1994, 37-48.
 474 CHAPTER 20
 
alternative binomial tree construction method for each of S, and S, in Section 18.5. This m ethod
has the pronerty that all probabilities are 0.5. When the two binomial trees are combin onnas ine property tnat au proodonities are vo. Wnen tne two oimomia: trees are combined on the
assumption that there is no correlation, the probabilities are as follows:
S)-moveS5-move Down UpUp 0.25 0.25Down 0.25 0.25
When we adjust these probabilities to reflect the correlation, they become:
S|-moveSy-move Down UpUp 0.251 — p) 0.251 + p)
Down 0.25(1 + p) 0.25 — p)
20.9 MONTE CARLO SIMULATION AND AMERICAN OPTIONS
 
Monte Carlo simulation is well suited to valuing path-dependent options and options where thereare many stochastic variables. Trees and finite difference methods are well suited to valuingAmerican-style options. What happens if an option is both path dependent and American? Whathappens if an American option depends on several stochastic variables? In Section 20.5 weexplained a way in which the binomial tree approach can be modified to value path-dependentoptions in some situations. A number of researchers have adopted a different approach bysearching for a way in which Monte Carlo simulation can be used to value American-styleoptions.”® Here we explain two alternative approaches ways of proceeding.
In order to value an American-style option, it is necessary to choose between exercising andconlinuing at each early exercise point. The value of exercising is normally easy to determine.A number of researchers including Longstaff and Schwartz provide a way of determining thevalue of continuing when Monte Carlo simulation is used.2” Their approach involves using aleast-squares analysis to determine the best-fit relationship between the value of continuing andthe values of relevant variables at each time an early exercise decision has to be made. Theapproach is best illustrated with a numerical example. We use the one in the Longstaff—Schwartzpaper.
Consider a threc-ycar Amcrican put option on a non-dividcnd-paying stock that can be exercised
°6 Tilley was the first researcher to publish a solution to the problem. See J. A. Tilley, “Valuing American Options ina Path Simulation Model,” Transactions of the Society of Actuaries, 45 (1993), 83-104.
7 See F. A. Longstaff and E. S, Schwartz, “Valuing American Options by Simulation: A Simple Least-SquaresApproach,” Review of Financial Studies, 14, no. 1 (Spring 2001), 113-47,More on Models and Numerical Procedures 475
Table 20.1 Sample paths for put option example
 
Path t=0 ~t=l t=2 t=31 1.00 1.09 1.08 1.342 1.00 1.16 1.26 1.543 1.00 1.22 1.07 1.034 1.00 0.93 0.97 0.925 1.00 1.11 1.56 1.526 1.00 0.76 0.77 0.907 1.00 — 0.92 0.84 1.018 1.00 0.88 1,22 1.34
at the end of year 1, the end of year 2, and the end of year 3. The risk-free rate is 6% per annum(continuously compounded). The current stock price is 1.00 and the strike price is 1.10. Assumethat we sample the eight paths for the stock price shown in Table 20.1. (This example is forillustration only; in practice many more paths would be sampled.) If the option can be exercisedonly at the three-year point, it provides a cash flow equal to its intrinsic value at that point. This isshown in the last column of Table 20.2.
If the put option is in the money at the two-year point, the option holder must decide whether toexercise. From Table 20.1 we see that the option is in the money at the two-year point for paths 1,3, 4, 6, and 7. For these paths we assume the approximate relationship
V=atbS+cS?
where S is the stock price at the two-year point and V is the value of continuing, discounted backto the two-year point. Our five observations on S are: 1.08, 1.07, 0.97, 0.77 and 0.84, From Table20.2 the corresponding values for V are: 0.00e7°°%*!, 9.07670! 9.182799! 9.20e7-*! and0.09e~°"*_ We use this data to calculate the values of a, b, and ¢ that minimize
i
5(V; —a— bS,; —cS?¥=I
Table 20.2 Cash flows if exercise only at the three-year point
Path t=1 t=2 t=3
 
1 0.00 0.00 0.002 0.00 0.00 0.003 0.00 0.00 0.074 0.00 0.00 0.185 0.00 0.00 0.006 0.00 0.00 0.207 0.00 0.00 0.098 0.00 0.00 0.00476 CHAPTER 20
Table 20.3 Cash flows if exercise only possible at two- andthree-year point
Path t=1 t=2 t=3
 
1 0.00 0.00 0.002 0.00 0.00 0.003 0.00 0.00 0.074 0.00 0.13 0.005 0.00 0.00 0.006 0.00 0.33 0.007 0.00- 0.26 0.008 0.00 0.00 0.00
where S; and V, are the ith observation on S and V, respectively. It turns out that a = —1.070,b = 2,983, and c = —1.813, so that the best-fit relationship is
V = —1.070 + 2.9835 — 1.8138?
This gives the value at the two-year point of continuing for paths 1, 3, 4, 6, and 7 of 0.0369, 0.0461,0.1176, 0.1520, and 0.1565, respectively. From Table 20.1 the value of exercising is 0.02, 0.03, 0.13,0.33, and 0.26. This means that we should exercise at the two-year point for paths 4, 6, and 7.Table 20.3 summarizes the cash flow for the eight paths assuming exercise at either the two-yearpoint or the three-year point.
We next consider the paths that are in the money at the one-year point. These are paths 1, 4, 6, 7,and 8 From Table 20.1 the values of S for the paths are 1.09, 0.93, 0.76, 0.92, and 0.88,respectively. From Table 20.3 the corresponding values of V are 0.00e7%%*!, 9.132700!0.33e7%! 9.2620! and 0.002%! | respectively. The least-squares relationship is
V = 2.038 — 3.3358 + 1.35657This gives the value of continuing at the one-year point for paths 1, 4, 6, 7, and 8 as 0.0139, 0.1092,
0.2866, 0.1175, and 0.1533, respectively. From Table 20.1 the value of exercising is 0.01, 0.17, 0.34,0.18, and 0.22. This means that we should exercise at the one-year point for paths 4, 6, 7, and 8.
Table 20.4 Cash flows from option
 
Path t=1 t=2 t=3I 0.00 0.00 0.002 0.00 0.00 0.003 0.00 0.00 0.074 0.17 : 0.00 0.005 0.00 . 0.00 0.006 0.34 0.00 0.007 0.18 0.00 0.008 0.22 0.00 0.00More on Models and Numerical Procedures 477
Table 20.4 summarizes the cash flows assuming that early exercise is possible at all three times. Thevalue of the option is determined by discounting each cash flow back to time zero at the risk-freerate and calculating the mean of the results: Tt is
40.072? 40,1720! 4. 0,34e70F*! 4 0.18%! 49,220 FX) = 0.1144
Because this is greater than 0.10, it is not optimal to exercise the option immediately.
This method can be extended in a number of ways. If the option can be exercised at any time, wecan approximate its value by considering a large number of exercise points (just as a binomial treedoes}. The relationship between V and S can be assumed to be more complicated. For example, wecould assume that V is a cubic rather than a quadratic function of S. When the early exercisedecision depends on several state variables, we proceed as we did in the example just considered.A functional form for the relationship between V and the variables is assumed and the parametersare estimated using the least-squares approach.
The Exercise Boundary Parametrization Approach
A number of researchers, such as Andersen, have proposed an alternative approach in which theearly exercise boundary is parametrized and the optimal values of the parameters are determinediteratively by starting at the end of the life of the option and working backward.”® To illustrate theapproach, we continue with the put option example and assume that the eight paths shown inTable 20.1 have been sampled. In this case the early exercise boundary at time ¢ can be
saramctrized by 4 critical valu S*iHN\ of Ss. Tf the acsct srice at time tis below 74. won avarciseparamctrizea oY & Critica: Vaiue, o (fj, Of o. ai Ine assct price at time 7 is Oc1OW Ss {i}, We Cxercise
at time ft; if is above $*(t), we do not exercise at time t. The value of $*(3) is 1.10. If the stock priceis above 1.10 when t = 3 (the end of the option’s life), we do not exercise; if it is below 1.10, weexercise. We now consider the determination of S*(2).
Suppose that we choose a value of S*(2) less than 0.77. The option is not exercised at the two-year point for any of the paths. The vaiue of the option at the two-year point for the eight paths isthen 0.00, 0.00, 0.07e °°! 0.18 °°! 9.00, 0.20 °°! 0.09 °°5*!, and 0.00, respectively.The average of these is 0.0636. Suppose next that $*(2) = 0.77. The value of the option at the two-year point for the eight paths is then 0.00, 0.00, 0.07e°°*!, 0.18¢-°*!, 0.00, 0.33, 0.09e 2%),and 0.00, respectively. The average of these is 0.0813. Similarly when S*(2) equals 0.84, 0.97, 1.07,and 1.08, the average value of the option at the two-year point is 0.1032, 0.0982, 0.0938, and0.0963, respectively. This analysis shows that the optimal value of 5*(2) (i.e., the one thatmaximizes the average value of the option) is 0.84. (More precisely, it is optimal to choose0.84 < $*(2) < 0.97.) When we choose this optimal value for $*(2), the value of the option atthe two-year point for the eight paths is 0.00, 0.00, 0.0659, 0.1695, 0.00, 0.33, 0.26, and 0.00,respectively. The average value is 0.1032.
We now move on to calculate $*(1). If S*(1) < 0.76, the option is not exercised at the one-yearpoint for any of the paths and the value at the option at the one-year point is0.1032e7°*! — 0.0972, If $*(1) = 0.76, the value of the option for each of the eight paths atthe one-year point is 0.00, 0.00, 0.0659e°™! 9.1695e~*!. 9.0, 0.34, 0.2629! and 0.00,respectively. The average value of the option is 0.1008. Similarly, when S*(1) equals 0.88, 0.92,0.93, and 1.09, the average value of the option is 0.1283, 0.1202, 0.1215, and 0.1228, respectively.The analysis therefore shows that the optimal value of $*(1) is 0.88. (More precisely, it is optimal
8 See L. Andersen, “A Simple Approach to the Pricing of Bermudan Swaptions in the Multifactor LIBOR MarketModel,” Journal af Computational Finance, 3, no. 2 (Winter 2000), 1-32.478 CHAPTER 20
 
to choose 0.88 < S*(1) < 0.92.) The value of the option at time zero with no early exercise is0.1283e-°°*! — 0,1208. This is greater than the value of 0.10 obtained by exercising at time zero.
In practice tens of thousands of simulations are carried out to determine the early exerciseboundary in the way we have described. Once we have obtained the early exercise boundary, wediscard the paths for the variables and carry out a new Monte Carlo simulation using the earlyexercise boundary to value the option.
Our American put option example is simple in that we know the early exercise boundary at atime can be defined entirely in terms of the value of the stock price at that time. In morecomplicated situations it is necessary to make assumptions aboul how the early exercise boundaryshould be parametrized.
Upper Bounds
The two approaches we have outlined tend to underprice American-style options because theyassume a suboptimal early exercise boundary. This has led Andersen and Broadie to propose aprocedure that provides an upper bound to the price.”® This procedure can be used in conjunctionwith any algorithm that generates a lower bound and pinpoints the true value of an American-styleoption more precisely than the algorithm taken on its own.
SUMMARY
 
 
A number of models have been developed to fit the volatility smiles that are observed in practice.The constant elasticity of variance model leads to a volatility smile similar to that observed forequity options. The jump diffusion model leads to a volatility smile similar to that observed forcurrency options. Stochastic volatility models are more flexible in that they can lead to either thetype of volatility smile observed for equity options or the type of volatility smile observed forcurrency options. The implied volatility function model provides even more flexibility that this. It isdesigned to provide an exact fit to any pattern of European option prices observed in the market.
The natural technique to use for valuing path-dcependcnt options is Monte Carlo simulation.This has the disadvantage that it is fairly slow and unable to handle American-style derivativeseasily. Luckily, trees can be used to value many types of path-dependent derivatives. The approachis to choose representative values for the underlying path function at each node of the tree andcalculate the value of the derivative for each alternative value of the path function as we roll backthrough the tree. There is a trick for valuing lookback options using trees. Instead of valuing theoption in dollars, we use the asset price as our unit of measurement.
Trees can be used to value many types of barrier options, but the convergence of th
value to the correct value as the number of time steps is increased tends to be slow. One approachfor improving convergence is to arrange the geometry of the tree so that nodes always lie on thebarriers. Another is to use an interpolation scheme to adjust for the fact that the barrier beingassumed by the tree is different from the true barrier. A third is to design the tree so that it providesa finer representation of movements in the underlying asset price near the barrier.
One way of valuing options dependent on the prices of two correlated assets is to apply atransformation to the asset price to create two new uncorrelated variables. These two variables are
he option
? See L. Andersen and M. Broadie, “A Primal-Dual Simulation Algorithm for Pricing Multi-DimensionalAmerican Options,” Working Paper, Columbia University, 2001.More on Models and Numerical Procedures 479
each modeled with trees and the trees are then combined to form a single three-dimensional tree.At each node of the tree, the inverse of the transformation gives the asset prices. A secondapproach is to arrange the positions of nodes on the three-dimensional tree to reflect thecorrelation. A third approach is to start with a tree that assumes no correlation between thevariables and then adjust the probabilities on the tree to reflect the correlation.
Monte Carlo simulation is not naturally suited to valuing American-style options, but there aretwo ways it can be adapted to handle them. The first involves using a least-squares analysis to relatethe value of continuing (i.e., not exercising) to the values of relevant variables. The second involvesparameirizing the early exercise boundary and determining it iteratively by working back from theend of the life of the option to the beginning.
SUGGESTIONS FOR FURTHER READING
 
 
Andersen, L., “A simple Approach to the Pricing of Bermudan Swaptions in the Multifactor LIBORMarket Model,” Journal of Computational Finance, 3, no. 2 (Winter 2000), 1-32.
Andersen, L. B. G., and R. Brotherton-Raicliffe, “The Equity Option Volatility Smile: An ImplicitFinite Difference Approach,” Journal of Computational Finance, 1, no. 2 (Winter 1997/98), 3-37.
Black, F., “How to Use the Holes in Black-Scholes,” RISK, March 1988.
Boyle, P. P., J. Evnine, and S. Gibbs, ‘““Numerical Evaluation of Multivariate Contingent Claims,”Review of Financial Studies, 2, no. 2 (1989), 241-50.
Boyle, P. P., and S. H. Lau, “Bumping Up Against the Barrier with the Binomial Method,” Journal ofDerivatives, |, no. 4 (Summer 1994), 6-14.
Conze, A., and R. Viswanathan, “Path Dependent Options: The Case of Lookback Options,” Journalof Finance, 46 (1991), 1893-1907.
Cox, J. C., and 8. A. Ross, “The Valuation of Options for Alternative Stochastic Processes,” Journal ofFinancial Economics, 3 (March 1976), 145-66.
Derman, E., and I. Kani, “Riding on a Smile,” RISK, February 1994, pp. 32-39.Duan, J.-C., “The GARCH Option Pricing Model,” Mathematical Finance, 5 (1995), 13~32.Duan, J.-C. “Cracking the Smile,” RISK, December 1996, pp. 55-59.
Heston, 8. L., “A Closed Form Solution for Options with Stochastic Volatility with Applications toBonds and Currency Options,” Review of Financial Studies, 6, no. 2 (1993), 327-43.
Dupire, B., “Pricing with a Smile,” RISK, February 1994, pp. 18-20.
Figlewski, S., and B. Gao, ““The Adaptive Mesh Model: A New Approach to Efficient Option Pricing,”Journal of Financial Economics, 53 (1999), 313-51.
Hull, J., and A. White, “Efficient Procedures for Valuing European and American Path-DependentOptions,” Journal of Derivatives, 1, no. 1 (Fall 1993), 21-31.
Hull, J. C., and A. White, “Finding the Keys,” RZSK, September 1993, 109-112.
Hull J. C., and A. White, “The Pricing of Options on Assets with Stochastic Volatilities,” Journal ofFinance, 42 (June 1987), 281-300.
Hull, J. C, and A. White, ‘An Analysis of the Bias in Option Pricing Caused by a StochasticVolatility,” Advances in Futures and Options Research, 3 (1988), 27-61.480 CHAPTER 20
 
Hull, J. C., and W. Suo, “A Methodology for the Assessment of Model Risk and its Application tothe Implied Volatility Function Model,” Journal of Financial and Quantitative Analysis, 37, no. 2(June 2002).
Longstaff, F. A., and E. S. Schwartz, “Valuing American Options by Simulation: A Simple Least-Squares Approach,” Review of Financial Studies, 14, no. 1 (Spring 2001), 113-47.
Merton, R. C., “Option Pricing When Underlying Stock Returns Are Discontinuous,” Journal ofFinancial Economics, 3 (March 1976), 125-44.
Ritchken, P., and R. Trevor, “Pricing Options Under Generalized GARCH and Stochastic VolatilityProcesses,”’ Journal of Finance, 54, no. 1 (February 1999), 377-402.
Rubinstein, M., ‘Implied Binomial Trees,” Journal of Finance, 49, no. 3 (July 1994), 