Double-Exponential Fast Gauss Transform Algorithms for Pricing Discrete Lookback Options Yusaku Yamamoto Nagoya University Thirty Years of the Double Exponential Transforms KRIMS, Kyoto September 3, 2004 Outline of the talk 1. Introduction 2. The DE-FGT algorithm for lookback options 3. Extension to lookback options under Mertons ju mp-diffusion model 4. Extension to American lookback options 5. Conclusion 1. Introduction What is a lookback option? A lookback put option is the right to sell an asset at the end of a tim

e period at the highest price the asset took during the period. A lookback call option is the right to buy at the lowest price. asset price St MT = max St 0 t T S0 option payoff = MT ST ST 0 t life of the option T (maturity)

Appealing to investors because the holder of a lookback option can never miss the best underlying asset price. Popular in OTC markets for currency hedging. Pricing of lookback options The option price Though lookback options give the buyer great flexibility, the seller (the counter party of the option contract) has to take on a lot of risk. To compensate for the risk, the buyer of the option has to pay the seller at the beginning of the contract. This is called the option price. The pricing principle The rational option price is given as the discounted expectation value (under the risk-neu tral probability) of the option payoff: Analytical formula V0(Sthe e E0[MT model ST]. dSt/St = r dt + dWt and the extreme valu

0) = When the asset follows Black-Scholes es are continuously monitored, analytical pricing formula is available . (Conze and Visw anathan, 1991) rT Pricing of discrete lookback options Discrete lookback options For the great majority of the traded lookback options, the maximu m or minimum is taken over a finite set of time points within the li fe of the option called monitoring dates. St Mn = max Si S0 0 i n S2

S1 option payoff = Mn Sn S3 t0 = 0 t1 t2 t3 Sn tn-1 tn=T t

monitoring dates In this case, there is no analytical pricing formula and one has to re sort to numerical methods. Existing numerical methods Monte Carlo method Binomial method Reiners convolution method (Reiner, 2000) DE-FGT algorithm (Broadie and Yamamoto, 2002) Among these, the DE-FGT algorithm has proven to be extremely f ast and accurate when pricing standard discrete lookback options u nder the Black-Scholes framework.

Objective of this study In this study, we generalize the DE-FGT algorithm in two directions. 1. Extension to lookback options under Mertons model 2. We extend our algorithm to deal with lookback options under Merton's jump-diffusion model, which takes into account the possibility of discontinuous movements of the asset price. Extension to American lookback options We propose a modified version of the algorithm to deal with

American lookback options, which offers the holder added flexibility of exercising the right before maturity. 2. The DE-FGT algorithm for lookback options Problem formulation Lets consider a discrete lookback put option with time period [0, T] a nd n+1 monitoring dates ti = it (i = 0, 1, , n, t = T/n). Assume also that the asset price follows the Black-Scholes model: dSt / St = (r q) dt + dWt (r: interest rate, q: dividend rate, : volatility, Wt : standard Brownian motion) and let Si = (asset price at ti) and Mi = max Sk. 0 k i Then the option price is given as the discounted expectation value of the option payoff: V0(S0) = erT E0[Mn Sn].

Computation of the expectation value Reduction to a 1-dimensional problem To evaluate the expectation value, we need the joint probability den sity function (pdf) of Sn and Mn. To reduce the dimensionality, we apply a change of measure (Babb s, 1992): and obtain a new expression: V0(S0) . By introducing log stock prices by si = log(Si /S0) and mi=log(Mi /S0), V0(S0) So we only need the probability density function of mn sn. Computing the pdf of mn sn The recurrence formula

To compute the pdf of mn sn, we use the following relation: If the asset follows a Levy process, mi1 si1 is independent of si1 si. The pdf of (mi1 si1) + (si1 si) can be computed as the convolution of the pdfs of mi1 si1 and si1 si. Finally, the pdf of mi si is obtained by collecting all the probability mass corresponding to mi si < 0 to the point mi si = 0 . As a result, the pdf of mi si has a -function component at mi si = 0. Computing the pdf of mn sn (contd) The recurrence formula (contd) By expressing the pdf of mi si as ci(x) + gi(x), we have the recurrence for mula: where c0 = 1, gi(x) = 0 and f (x) is the pdf of si1 si. Under the BS model, si1 si follows Gaussian distribution N((r q (1/2)2)t, 2). The recurrence formula reduces to convolution of a given function with Gaussian.

Use of the double-exponential formula Change of variables To compute the convolution, we use the double-exponential transfor mation y = exp(u eu). . Discretizaion By discretizing the integral using the trapezoidal rule, we have , where ak = exp(kh ekh) and wk = (1 + ekh) exp(kh ekh) h . Acceleration by the fast Gauss transform We need to compute the discrete convolution of the form: ,

where f(x) is a Gaussian function given by . This can be done efficiently with the fast Gauss transform (Greengard and Strain, 1991), which is a variant of the fast multipole method. The computational work is O(N) when the number of sample points at each monitoring date is N. Main idea of the fast Gauss transform Convolution to be computed Suppose that we want to compute the discrete convolution: i i Expansion of Gaussian by Hermite functions To compute the sums efficiently, we use the following expansion o f the Gaussian probability density function: This can be shown easily using the expansion

( hn(x): Hermite function ) and the definition of the Hermite function. Algorithm A three step algorithm Truncating this expansion, we have i i This suggests a three step approach to calculate the sums of Gaussian s (Greengard & Strain, 1991): (1) Compute (2) Multiply the result by (3) Multiply the result by . (O(N) work)

and sum over n. (O(1) work) and sum over m. (O(N) work) Thus we can compute G(xi) (i=1, , N) in O(N) work. Main idea of the fast Gauss transform xi yj x0 y0 t t +1 Acceleration by the fast Gauss transform

We need to compute the discrete convolution of the form: , where f(x) is a Gaussian function given by . This can be done efficiently with the fast Gauss transform (Greengard and Strain, 1991), which is a variant of the fast multipole method. The computational work is O(N) when the number of sample points at each monitoring date is N. 3. Extension to lookback options under Mertons jump-diffusion model Limitations of the Black-Scholes model It is widely known that the BS model fails to reproduce some of th e important features of the asset price dynamics such as jumps in the asset price heavy tails of the pdf of si1 si. St S0

0 empirical pdf jump Gaussian T t si1 si Ignoring these features might cause mispricing, so a more realistic model which can reproduce these features has been sought. Mertons jump-diffusion model The model

Mertons jump-diffusion model (Merton, 1976) is the simplest mode l that can reproduce these features. It adds random jumps driven by a Poisson process to the BS model. The size of jumps is also random and is log-normally distributed. SDE for the asset price where N(t) : Poisson process with intensity . Vl: i.i.d. random variables such that log(Vl) follows N (, 2). Mertons jump-diffusion model (contd) Mertons model in integral form By solving the SDE, we have the following relationship between a sset prices at ti1 and ti: where zl (l=0, 1, ) : i.i.d random variables that follow N(0,1). = e 1.

The pdf of si1 si From the above expression, it can easily be seen that the pdf of si1 si has the following form, that is, sum of Gaussians: Computing the lookback option price Reduction to a 1-dimensional problem To compute the lookback option price, we first apply the change of measure to reduce the dimensionality of the problem: Then we can write the option value (as in the BS case) as follows: Under the new measure Q, the asset price can be shown to follow a new jump-diffusion p V0(Sparameters: rocess with modified 0) The functional form of f(x) does not change. r =using

r + Girsanovs , = theorem + for , jump-diffusion = e This can be proved processes. An elementar y proof can also be given. 2 2 The DE-FGT algorithm for Mertons model Reduction to a series of convolutions By applying the same procedure as we used for the BS model, the computation of the option price can be reduced to a series of discre te convolutions: ,

where f(x) is sum of Gaussians. Acceleration by the fast Gauss transform The above convolution can be computed efficiently by a repeated use of the fast gauss transform. Further reduction in computational work is possible because these transforms have many operations in common. Numerical experiments Target problem Discrete lookback put options under Mertons jump-diffusion model Numerical methods Monte Carlo method Reiners convolution method (compute the convolution by FFT) Our method (DE formula + FGT) Computational environment Pentium 4 PC (2.0GHz) with Red-Hat Linux

gnu++ compiler Parameters S0 = 100, r = 0.1, q = 0, = 0.3, = 2.0, = 0.3, = 0, T = 0.2. Numerical results Computation time (sec) 1.E+01 1.E+00 0.1 1 10 100 1.E-01 Option price = 12.09911864

Absolute error 1.E-02 1.E-03 1.E-04 1.E-05 1.E-06 1.E-07 1.E-08 1.E-09 Results for an option with 25 monitoring dates 1000 (extremum monitored every two days) Reiner Monte Carlo DE-FGT

The DE-FGT method outperforms Reine rs convolution method and the Monte C arlo method in this case. It can compute the price of the lookback option price within 0.4 seconds up to the accuracy of 10-9. Numerical results (contd) Computation time (sec) 1.E+01 1.E+00 1.E-01 0.1 1 10

100 Option price = 12.57499665 Absolute error 1.E-02 1.E-03 1.E-04 1.E-05 1.E-06 1.E-07 1.E-08 1.E-09 1.E-10 1000 Results for an option with 50 monitoring dates (daily monitoring).

Reiner Monte Carlo DE-FGT The behavior of the three numerical methods are almost the same as for the n=25 case. The DE-FGT algorithm can compute the price of the lookback option price within 1.0 seconds up to the accuracy of 10-9. 4. Extension to American lookback options What is an American lookback option? Its a variant of the lookback option which offers the holder added flexibility of exercising the right before maturity. The option payoff when exercised at time t is Mt St. St Mt = max Su

0 u t S0 option payoff = Mt St St exercise 0 t T life of the option It is usually more valuable than the standard lookback options bec ause there are cases where early exercise produces greater payoff. In the following, we consider a variant for which early exercise is

possible only on the monitoring dates. Pricing of the American lookback options Pricing principle It is known that the rational price of the American lookback option is given by the following expression (cf. Duffie, 1996): V0(S0) = sup E0[ert (M S)] Here, denotes Markov stopping time. That is, we consider expectation values under all possible stopping times (i.e. exercise strategies) and take the supremum. Pricing by dynamic programming To compute this expectation value, we use dynamic programming and use t he backward recursion: Vi(Si, Mi) = max (Mi Si, ert Ei[Vi+1] ) where

immediate exercise value continuation value Vi is the option value at time ti and is a function of Mi and Si in general. Ei is the expectation value operator given information up to ti. For i = n, we have Vn = Mn Sn. This backward recursion reflects the strategy of exercising the right when th e immediate exercise value is greater than the discounted expected value of the option at the next monitoring date, and holding the right otherwise. Reduction to a 1-dimensional problem Change of measure To reduce the dimensionality of the problem, we introduce a new v ariable Vi = Vi/Si and rewrite the backward recursion formula: Vi(Si, Mi) = max (Mi Si, ert Ei[Vi+1] ) Vi (Si, Mi) = max (Mi / Si 1, ert Ei[Vi+1] / Si ). B further introducing a change of measure similar to the one used f or standard lookback options, we have

ert Ei[Vi+1] = Si eqt Ei [Vi+1/Si+1] Inserting this into the above formula, we have a new recursion: Vi (Si, Mi) = max (Mi / Si 1, eqt Ei [Vi+1]). Furthermore, it can be shown that Vi (Si, Mi) is a function of Mi / Si only. Thus we have reached a 1-diemnsional problem. Application of the DE-FGT method The main task in computing the recursion Vi (Si, Mi) = max (Mi / Si 1, eqt Ei [Vi+1]). is the evaluation of the expectation value Ei [Vi+1] for each value of i / Si. M By introducing the log stock prices by si = log(Si /S0) and mi=log(Mi /S0) (a s in the case of standard lookback options), this can be rewritten as a c onvolution of a function with Gaussian.

Then our DE-FGT method can be applied. Difficulty in computing the convolution Difficulty As can be seen from the recurrence formula for Vi+1, Vi+1 is defined using the max operator and therefore has a discontinuity in its first derivative. Direct application of the DE formula will not give good results. Remedy We first locate the discontinuous point by the bisection method. Then we divide the integration interval into two intervals and apply the DE formula to each interval. Numerical experiments Target problem Discrete American lookback put options under Black-Scholes model Numerical methods Binomial method

Reiners convolution method Our method (DE formula + FGT) Computational environment Same as the previous numerical experiments Parameters S0 = 100, r = 0.1, q = 0, = 0.3, T = 0.2. Numerical results Computation time (sec) 1.E+00 0.01 1.E-01 0.1 1 10

Absolute error 1.E-02 Results for an option with 5 monitoring /exercise dates (bi-weekly monitoring/exercise) Option price = 7.05538954 1.E-03 1.E-04 100 Reiner Binomial DE-FGT 1.E-05

1.E-06 1.E-07 1.E-08 1.E-09 The convergence of Reiners method is r ather irregular. This seems to be because of the discontinuity in the first derivative of the integrand function. Numerical results (contd) Computation time (sec) 1.E+00 0.01 1.E-01 0.1 1

10 Absolute error 1.E-02 1.E-05 1.E-06 1.E-07 Results for an option with 10 monitoring /exercise dates (weekly monitoring/exercise) Option price = 7.92740313 1.E-03 1.E-04 100

Reiner Binomial DE-FGT Reiners method is the fastest when the r equired accuracy is relatively low. Still, our method is competitive when hi gher accuracy is needed. 1.E-08 1.E-09 Also, the convergence of our method is much more smooth than that of Reiners method. 5. Conclusion We proposed a pricing algorithm based on the DE formula and the fast Gauss transform for lookback options under Mertons model and American lookback options.

For lookback options under Mertons model, our method outpe rforms conventional methods such as Reiners convolution met hod and can compute the option price within 1 second up to ac curacy of 109. For American lookback options, reiners method is the fastest when the required accuracy is relatively low. But our method is competitive when high accuracy is required. Future work Extension to more general jump-diffusion asset price models variance gamma models stochastic volatility models Extensions to other types of exotic options options on two or more assets various path-dependent options