On the efficient application of the repeated Richardson
Department of Applied Mathematics, University of Venice WORKING PAPER SERIES
Luca Barzanti, Corrado Corradi
and Martina Nardon
On the efficient application of the repeated Richardson extrapolation technique to
option pricing
Working Paper n. 147/2006
November 2006
ISSN: 1828-6887
This Working Paper is published under the auspices of the Department of Applied Mathematics of the Ca’ Foscari University of Venice. Opinions expressed herein are those of the authors and not those of the Department. The Working Paper series is designed to divulge preliminary or incomplete work, circulated to favour discussion and comments. Citation of this paper should consider its provisional nature.
On the e?cient application of the repeated Richardson extrapolation technique to option pricing
Luca Barzanti Corrado Corradi
University of Bologna University of Bologna
Martina Nardon
University Ca’Foscari Venice
(November,2006)
Abstract.Richardson extrapolation(RE)is a commonly used technique in?nancial ap-plications for accelerating the convergence of numerical methods.Particularly in option pricing,it is possible to re?ne the results of several approaches by applying RE,in order to avoid the di?culties of employing slowly converging schemes.But the e?ectiveness of such a technique is fully achieved when its repeated version(RRE)is applied.Nevertheless,its application in?nancial literature is pretty rare.This is probably due to the necessity to pay special attention to the numerical aspects of its implementation,such as the choice of both the sequence of the stepsizes and the order of the method.In this contribution,we consider several numerical schemes for the valuation of American options and investigate the possibility of an appropriate application of RRE.As a result,we?nd that,in the ana-lyzed approaches in which the convergence is monotonic,RRE can be used as an e?ective tool for improving signi?cantly the accuracy.
Keywords:Richardson extrapolation,repeated Richardson extrapolation,American op-tions,randomization technique,?exible binomial method.
JEL Classi?cation Numbers:C15,C63,G13.
MathSci Classi?cation Numbers:65B05.
Correspondence to:
Martina Nardon Department of Applied Mathematics
University Ca’Foscari Venice
Dorsoduro3825/E
30123Venice,Italy
Phone:[++39]0412346924
Fax:[++39]0415221756
E-mail:mnardon@unive.it
1Introduction
In?nance one has frequently to deal with approximate results that are obtained by iterative methods or computational procedures depending on some parameter(e.g.the time-step). Often the convergence of numerical schemes is slow and this may be a serious problem in many practical situations.For this reason,convergence acceleration techniques,such as Richardson extrapolation,have been studied and applied in the literature.
In this contribution,we focus on repeated Richardson extrapolation(hereafter RRE), which has not been well exploited in?nancial applications,probably due to numerical techniques required.In fact,one has to pay special attention to the numerical aspects of its implementation,such as the choice of both the sequence of the stepsizes and the order of the method.
Although the RRE technique is generally applicable,in order to illustrate how it works, we will focus on valuing a standard American put option.We consider several numerical schemes for the valuation problem and investigate the possibility of an appropriate appli-cation of RRE.As a result,when the convergence of the method is monotonic,RRE can be used as an e?ective tool for improving signi?cantly the accuracy.
In particular,we apply RRE to the randomization approach proposed by Carr(1998), the binomial approach of Cox et al.(1979),the Black-Scholes-binomial method(BBS)of Broadie and Detemple(1996),and the?exible binomial method proposed by Tian(1999). The accuracy of the randomization method is improved when RRE is applied by choosing a particular sequence of stepsizes.As well known,it is not convenient to use Richardson extrapolation(RE)in the binomial model:this is due to the non-uniform convergence of the method1.Numerical results highlight that RE and RRE are not useful in the classical binomial approach.RE has been successfully applied by Broadie and Detemple(1996)in their hybrid binomial-Black-Scholes model,but in our numerical experiments carried out RRE cannot be e?ciently applied to the BBS method.When implemented within the ?exible binomial setting introduced by Tian(1999),RRE based on Romberg sequence of stepsizes gives very accurate and fairly robust results,because of the smoother nature of the convergence of the method.
An outline of the paper is the following.In section2we brie?y review the?nancial literature on the Richardson extrapolation technique applied to option pricing problems. Subsection2.1explains the RE and RRE techniques and introduces the choice of di?erent stepsize sequences.A wide experimental analysis is carried out in order to test the method; the main results are presented and discussed in section3.We will provide some insights on how RRE can e?ectively be used in practice.Section4presents some concluding remarks.
1We refer to Heston and Zhou(2000)for a discussion on the rate of convergence of lattice methods.Here non-uniform convergence is understood in the sense that the solution in the binomial setting has not the same rate of convergence at all nodes of the tree.
2
2Richardson extrapolation and its applications in?nance Richardson extrapolation has been applied to accelerate valuation schemes for American options and exotic options.Geske and Johnson(1984)?rst applied Richardson extrapolation in a?nancial context to speed up and simplify their compound option valuation model.They obtain a more accurate computational formula for the price of an American put option using the values of Bermuda options.Geske and Johnson approach was subsequently developed and improved by Bunch and Johnson(1992),and Ho et al.(1997).More recently,Chang et al.(2002)proposed a modi?ed Geske-Johnson formula based on the repeated Richardson extrapolation.
Richardson extrapolation techniques were also employed to enhance e?ciency of lattice methods(Breen,1991).It is common opinion that it is not convenient to extrapolate on the number of time steps in the binomial model due to the oscillatory nature of the convergence (Omberg,1987).Broadie and Detemple(1996)successfully use Richardson extrapolation to accelerate a hybrid of the binomial and the Black-Scholes models.Tian(1999)and Heston and Zhou(2000)also apply Richardson extrapolation to binomial and multinomial approaches.
Carr(1998)proposes a randomization approach for the valuation of the American put option and uses Richardson extrapolation to obtain accurate estimates of both the price and the exercise boundary of an American put option.Leisen(1999)shows that randomizing the length of the time steps in the binomial model allows the successful use of extrapolation. Huang et al.(1996)and Ju(1998)use extrapolation methods to accelerate the integral representation of the early exercise premium.
2.1Richardson extrapolation techniques
The very natural idea of extrapolation can be summarized as follows(see Deu?hard,1983). Consider the problem of calculating a quantity of interest for which an analytical formula is not provided.In the following,we restrict our attention to the problem of valuing an American put option.Instead of the unknown solution P0,take a discrete approximation P(h)depending on the stepsize2h>0,P(h)being a calculable function yielded by some numerical scheme,such that
P(h)=P(0)=P0.(1)
lim
h→0
All extrapolation schemes are based on the existence of an asymptotic expansion.Under the assumption that P(h)is a su?ciently smooth function,we write
P(h)=α0+α1h p1+α2h p2+···+αk h p k+O(h p k+1),(2) with0
2h may be the period of time between two exercise dates of the American option.Hence P(0)is the limit of the value of a Bermudan option as h goes to zero.
3
Compute the function P(h)over a certain basic step H>0a number of times with successively smaller stepsize h i,with
h1>h2> 0
In such a way,we obtain a sequence of approximations
P(h1),P(h2),...
for a given sequence of stepsizes.
We can construct extrapolation schemes of arbitrary order k by considering the following procedure3:
1.de?ne T i,1=P(h i),for i=1,2,...;
2.for i≥2and j=2,3,...,i,compute
T i,j=T i,j?1+T i,j?1?T i?1,j?1
h i?j+1
h i?1
.(3)
Recursion(3)is based on polynomial interpolation and an asymptotic h-expansion.We can establish the following extrapolation tableau(stopped at k-th order):
T1,
T2,T2,
T3,T3,T3,3
.. ...
.
..
....
T k,1T k,2T k,3...T k,k
The sequence{P(h i)}is taken as a?rst column in the extrapolation tableau.Each quan-tity T i,j is computed in terms of two successive approximations.The two point Richardson extrapolation technique can be repeated,giving rise to a numerical scheme which is ex-tremely fast and can dramatically improve accuracy4.The e?ciency of the method relies on the fact that the amount of computation required essentially corresponds to the number of function evaluations.
3Such a procedure is also known as Aitken-Neville algorithm and it is one of the extrapolation schemes which are commonly used.
4Each entry of the tableau is an approximation for P0;obviously,more precision is achieved on the diagonal.
4
The idea behind(3)is to provide two mechanisms for enhancing the accuracy:by increasing i one obtains a reduction in the stepsize parameter,while taking j large implies more accurate approximations.Both mechanisms work simultaneously,which indicates that the quantities T k,k are those of most interest.This provides us with the possibility of order control.
The accuracy and e?ciency of the method is strictly connected with the choice of the sequence of stepsizes.De?ne h i in terms of the basic stepsize H,such that h i=H/n i (i=1,2,...).Any stepsize sequence is characterized by the associated sequence of integers {n i}.In numerical experiments,we considered several sequences of the stepsize:?harmonic sequence:{1,2,3,4,5,6,7,8,...,n,...};
?double harmonic(Deu?hard)sequence:{2,4,6,8,10,12,14,16,...,2n,...};?Burlisch sequence5:{2,4,6,8,12,16,24,32,...,2n k?2,...};
?Romberg sequence:{2,4,8,16,32,64,128,...,2n k?1,...}.
All these sequences allow for convergence of the method;this is not always the case (see Burlisch,1964).The?rst and the fourth sequence are of common use in the?nancial literature related to extrapolation combined with option pricing models6;though the other sequences are well known in numerical analysis,it seems their use has not been investigated in?nance.
3E?cient implementation of RRE to option pricing: analysis of some numerical experiments
Richardson extrapolation is a well understood technique,which is often applied in?nance to enhance precision of results provided by discrete models.Nevertheless,repeated Richardson extrapolation has received little attention in the?nancial literature.In this section,we investigate how to implement e?ciently the RRE to option pricing.In order to explain how such a technique applies,we focus on the problem of valuating an American put option.
In particular,we apply the method to valuation models based on di?erent approaches: the randomization technique,the classical lattice method and some extensions of such an approach.The following subsections report the main results of the numerical experiments carried out and provide some insights about the convenient choice of the stepsize sequence when applying RRE within the di?erent valuation frameworks taken into consideration. 3.1Carr’s randomization approach
The model proposed by Carr(1998)for the valuation of American put options is based on a particular technique,called randomization.This technique,also known as Canadization,
5See Burlisch(1964).Note that some authors report the following sequence:{2,3,4,6,8,12,...}.
6Usually two or three point Richardson extrapolation is applied.
5
has been recently applied and generalized by Kyprianou and Pistorius(2003)and Bouchard et al.(2005).
According to Carr’s de?nition,randomization is a three-step procedure for solving a valuation problem,which can be summarized as follows:let the value of one of the model parameters be“randomized”by assuming a plausible probability distribution for it;calcu-late the expected value of the dependent variable(which is unknown in the?xed parameter model)in this random parameter setting;let the variance of the distribution governing the parameter approach zero,holding the mean of the distribution constant at the?xed para-meter value.For example,if we consider standard options,we could randomize the initial stock price,the strike price,the initial time,or the maturity date.Carr randomizes the maturity date of an American put option and determines the solution for its value and the optimal exercise boundary.
Let the maturity of the randomized American put de determined by the waiting time to a certain number of jumps of a standard Poisson process,which is assumed to be independent of the underlying stock price process and uncorrelated with any market factor.The value of the random maturity American option approximates the value of its?xed maturity version.
When the randomized American option is supposed to mature at the?rst arrival of a Poisson process with intensityλ=1/T,the maturity?T is exponentially distributed with expectation T.
Due to the memoryless property of the exponential distribution,it turns out that the early exercise boundary is independent of time and the option value su?ers no time decay. As a result,the search for a time-dependent boundary is reduced to the search for a single critical stock price.The fair value of a randomized American put with an exponential distributed maturity is the solution of the following problem
P0=sup
H
E S[e?rt H(X?S t H)+],(4)
for S>H?,where H?is the unknown optimal exercise boundary,and t H is the?rst passage time through H.The expectation in equation(4)can be evaluated in closed form,and the result can be maximized over constant barriers.
The assumption of an exponentially distributed maturity leads to simple approxima-tions,which entail too much errors to be used for practical purposes.To obtain more accurate approximations,let assume that the time to maturity is subdivided into n inde-pendent exponential subperiods.Therefore the randomized American option matures at the n-th jump of a standard Poisson process(with intensityλ=n/T).As a result,the maturity?T is gamma distributed,with expectation T and variance T2/n.
In Carr’s n-step setting the randomized American put value and the initial critical stock price are determined by a dynamic programming algorithm.The resulting expression for the randomized option value is a triple sum,which does not require the evaluation of special functions.As the number of subperiods becomes large,the variance of the random maturity approaches zero.So increasing the number of periods improves the accuracy of the solution (of course at the expense of a greater computational cost).
Richardson extrapolation can be used to improve the method.Let P(n)
0denote the
randomized option price at time t=0determined assuming n random subperiods.The
6
N-point Richardson extrapolation7is the following weighted average of N approximate values
?P N 0=
N
n=1(?1)N?n n N
n!(N?n)!
P(n)
.(5)
By using Richardson extrapolation,accurate option values can be obtained just with
a few random time steps.The method proved robust and quite accurate,moreover the
convergence of the results is monotonic,allowing us to consider extrapolations of higher
order.
Carr applies extrapolation as de?ned by(5),which is based on the harmonic sequence.
We compared numerical results obtained with di?erent sequences of the steps,and assessed
the method on a large set of option valuation problems,considering di?erent values of
moneyness,maturity,volatility and risk-free interest rate.
In order to test the goodness of the employment of the RRE within Carr’s randomization
framework,we make a comparison between the price obtained for an American put option in
the25000-steps binomial model and the extrapolated prices in the random maturity model.
The simulation analysis takes into consideration3500randomly generated option valuation
problems.The parameter ranges are:r∈[0.01,0.12],σ∈[0.1,0.5],X/S0∈[0.7,1.3](r,σand X/S0are sampled from a uniform distribution on a given interval),with S0=100and
T=1.More in details,the moneyness interval has been partitioned into seven subsets:
X∈[70,80],[80,90],[90,100],{100},[100,110],[110,120],[120,130],and we have randomly
generated500instances from each subset.
We have considered di?erent sequences of the stepsize h i when applying repeated Richard-
son extrapolation.The results of the simulation experiments carried out for the option price
can be summarized by computing the mean absolute error(MAE)and the root mean square
error(RMSE)8of the simulation results with respect to the binomial price as moneyness
varies.
The outcomes of the simulation experiments are synthesized in tables from1to4;we
discuss only the out-of-the-money cases,being the results for in-the-money instances almost
the same.Both the MAE and the RMSE have been computed,but only the RMSE’s
are reported here in detail(as they give the same information of MAE’s).In the second,
fourth and sixth column of tables1,2and3we show the pricing errors on the diagonal of 7When we consider the harmonic sequence and recurrence(3),we can directly compute the quantities T k,k using the formula
T k,k=
k
i=1(?1)k?i i k
(k?i)!i!
P(h i),
which corresponds to a k-point Richardson extrapolation.
8The MAE and the RMSE are computed as follows:
MAE=1
N
N
n=1
|e n|,RMSE=
1
N
N
n=1
e2n,
where e n=?P n?P n
P n are the relative errors,being P n and?P n the“true”and the estimated option values,
respectively.We do not considers option prices lower than0.05when calculating errors.
7
the extrapolation tableau,which have been computed considering the harmonic,Deu?hard,
Burlisch and Romberg sequences,respectively.
Of course,one has not to compare the errors line by line in the tables.Such errors are
obtained by applying RRE based on di?erent sequences of the number of random steps.
Each sequence is characterized in the implementation by a speci?c computational amount
(see Burlisch,1964).
The harmonic sequence has been stopped at n=10(in practice we can apply RRE
based on the harmonic sequence up to step15,and in some cases also up to step20).We
stopped Romberg sequence at n=64(in same cases at n=128),because for higher values
of the number of steps,the method does not achieve higher accuracy or round-o?errors
arise(or,simply,the method is to slow).Hence,one has to make comparisons in terms of
accuracy the same remaining the computational e?ort required.
For example,in tables1–3we can compare RRE based on Deu?hard sequence with
n=16and n=18with RRE based on Burlisch sequence with n=24and n=32.The
resulting errors are of the same order,and it appears that one method does not overperform
the other one,but both are preferable to the extrapolation based on the harmonic sequence.
Moreover,with Burlisch sequence we can achieve higher accuracy if RE is repeated once
or twice more.Note also that RMSE’s of order10?4or lower are not obtainable with the other sequences(we are still considering the case X∈[70,80]).
In order to compare the errors relative to Burlisch sequence with those yielded by apply-
ing Romberg sequence,we have to consider the case n=48for the?rst one and n=64for
the latter.Burlisch sequence seems preferable in terms of accuracy and speed with respect
to the other sequences,and this?nding is supported by the results obtained for every level
of moneyness(not only,but the method perform better the higher the moneyness).For
instance,in the case X∈[120,130](which is not reported in tables),the RMSE is of
order1.6·10?5for the Burlisch sequence with n=48,while it is2.5·10?5for the Romberg sequence with n=64.
It is also interesting to analyze the error reduction on the diagonal of the extrapolation
tableau9.Table4shows the percent variations of the MAE for all the four sequences.As
we expected,the advantage in repeating RE is more evident when we apply Romberg and
Burlisch sequences.
3.2Richardson extrapolation applied in a binomial framework
As an interesting exercise,we investigate the possibility of applying RRE both to the CRR
binomial and the BBS approaches.It is well known that the oscillatory nature of the
convergence in the CRR model makes infeasible RE,a fortiori RRE should not be used.
We will see that,the technique is useful only in the at-the-money case.
We have carried out a wide simulation analysis,which takes into consideration3500ran-
domly generated option valuation problems,comparing the price obtained for an American
put option in the25000-steps binomial model and the extrapolated prices.The parameter 9Based on the error reduction along the diagonal,a stopping rule for the RRE may be de?ned,hence allowing for order control.
8
ranges are:r∈[0.01,0.12],δ∈[0.0,0.12](whereδis the continuous dividend yield),volatil-ityσ∈[0.1,0.5],X/S0∈[0.7,1.3],with S0=100and T=1.The moneyness interval has been partitioned into7subsets:X∈[70,80],[80,90],[90,100],{100},[100,110],[110,120], [120,130],and we have randomly generated500instances from each subset.We have con-sidered di?erent sequences of the stepsize h i and the basic step:in particular,H=T/100 and H=T/200.
As already observed,RE and RRE work only for at-the-money options,hence we discuss this special issue.Nevertheless,also in this case,the choice of the stepsize sequence is crucial. In table5,we show the pricing errors relative to at-the-money American put options:each entry in the second,fourth,sixth and eight column of table5is the MAE of the price estimates obtained by applying repeatedly RE.Only the errors along the diagonal of the extrapolation tableau are reported.The results refer to a basic step T/200;we applied the harmonic,Deu?hard,Burlisch and Romberg sequence.Observe that only RRE based on Romberg sequence yields very accurate and fairly robust results(the method continues to gain precision along the diagonal),while with all other sequences just two-point RE can be applied.
It is interesting to investigate what happens when we consider out-of-the-money Amer-ican put options.It turns out the RE and RRE no longer work,even when consider-ing Romberg stepsize sequence.Table6shows the extrapolation tableau for the case H=T/200.Note that the pricing errors of the extrapolation are higher than those of the non-extrapolated values(compare the?rst column of the tableau with the errors re-ported on the diagonal).It is clear from this discussion that RE should not be applied within the CRR model,except in just one case which is of limited interest.
We brie?y discuss also the feasibility of RRE within the hybrid binomial-Black-Scholes model proposed by Broadie and Detemple(1996).The convergence of the BBS method is smoother compared to the binomial method,so that one may wonder if RRE could be used. Two-point RE has been applied successfully to the BBS method,but still RRE does not perform well.In our numerical experiments,we?nd that the extrapolated values along the diagonal of the tableau entail higher errors than the approximate values below the diagonal and even with respect to the non-extrapolated values.Hence,RRE should not be applied within the BBS model.Our results are in accordance with the?ndings of Chang et al. (2002).
3.3Tian’s?exible binomial model
Tian(1999)introduces in the CRR binomial model a so called“tilt factor”λ,with the e?ect of modifying the shape and span of the binomial lattice.In this?exible binomial (FB)model,the up-and down-factors are de?ned as follows:
u=eσ√?t+λσ2?t
d=e?σ
√?t+λσ2?t
,(6)
whereλis an arbitrary constant that can be positive,zero,or negative.The parameter σ>0is the volatility,?t=T/n(with n number of steps)is the timestep,and T is the option maturity.
9
λ=0λ>0λ<0
Figure1:The?exible binomial lattice for di?erent values of the tilt parameterλ.
Of course,whenλ=0one recovers the CRR model with u0=eσ
√?t
and d0=u?10.Tian shows that for every choice of the tilt parameter(provided thatλis?nite and bounded) the?exible binomial model converges to the continuous-time counterpart.
Figure1shows the?exible binomial lattice forλ=0,λ>0andλ<0.A positive tilt parameter causes an upward transformation of the tree,while the e?ect of a negativeλis a downward shift.
The introduction of the tilt parameter in the binomial model allows for convenient adjustment to the tree in order to position nodes relative to the strike price(or the barrier) of the option.For the particular choice
λ=
2(η?j0)
√?t
σT
,(7) where
j0= log(X/S0)?n log(d0)
log(u0/d0) ,(8) u0=eσ
√?t
,d0=u?10,and[·]denotes the closest integer to its argument,the strike is always located on node(n,j0)at the option maturity.As a result,convergence of the FB model is smoother than in the CRR model,thus allowing the use of Richardson extrapolation.
Tian applies a two-point RE which considers prices obtained with a FB model with n/2 and n steps.We will see that RRE can be successfully applied.To this aim,it is worth noting that,not all the stepsize sequences perform well in the same manner,but Romberg sequence yielded very accurate and robust results.
In the numerical experiments,we compare the American put prices obtained in the n-steps FB model when RRE based on Romberg sequence is applied,and those in the 50000-steps FB model.We randomly generated3500option valuation problems.The
10
parameter ranges are:r∈[0.01,0.12],δ∈[0.0,0.12](whereδis the continuous dividend yield10),σ∈[0.1,0.5],X/S0∈[0.7,1.3],with S0=100and T=1.As in the previous trials,the moneyness interval has been partitioned into7subsets:X∈[70,80],[80,90], [90,100],{100},[100,110],[110,120],[120,130],and we have generated500instances from each subset.We have considered di?erent sequences of the stepsize h i,and basic step H=T/100,but we reported only the results for the Romberg sequence(which in the numerical trials overperformed all the other sequences).
The results of the simulation experiments carried out are synthesized in tables7and8. Both the MAE and the RMSE have been computed but are not reported here in detail. Only the errors along the diagonal of the extrapolation tableau are shown(in the second, fourth and sixth column),while in columns three,?ve and seven the percent variations of the MAE are shown.The results refer to a basic step T/100.Di?erently than in the CRR model,RRE performs well for all option moneyness,and not only in the at-the-money case.The pricing errors decrease monotonically as we consider a larger number of steps and higher order of extrapolation.
4Concluding remarks
Richardson extrapolation and repeated RE are useful techniques in order to enhance ac-curacy of approximate solutions yielded by numerical schemes in problems that arise in ?nance.Nevertheless,such techniques should no longer be applied when convergence is non-uniform.Provided smooth convergence,RRE can improve accuracy and e?ciency of the results.We have also found that the choices of the basic step and the stepsize sequence are critical.
In particular,we implemented the RRE within Carr’s randomization approach with a di?erent choice of the stepsizes sequence,obtaining more accurate results with the same computational amount.Numerical experiments carried out have shown that it is not conve-nient to apply RRE to the CRR and the BBS methods,due to the non-monotonic behavior of the pricing errors,while in the?exible binomial approach,where a simple two-point RE has been used sofar,we employed successfully the RRE.
Finally,it seems interesting to investigate the possibility of applying repeated Richardson extrapolation to other models,and in particular to Monte Carlo simulation methods for valuing American options.It is worth noting that one should be careful when employing extrapolation techniques combined with these latter approaches,because of the di?culty of determining the accuracy of the approximations,which sometimes are also biased.To this regard,ad hoc smoothing procedures and discrete monitoring corrections may be required. This interesting task is left for future research.
10Note that Tian consider only the caseδ=0.
11
References
[1]Bouchard,B.,El Karoui,N.,Touzi,N.(2005),Maturity randomization for stochastic
control problems.Annals of Applied Probability,15(4),2575–2605.
[2]Breen,R.(1991),The accelerated binomial option pricing model.Journal of Financial
and Quantitative Analysis,26,153–164.
[3]Broadie,M.,Detemple,J.(1996),American option valuation:new bounds,approxima-
tions,and a comparison of existing methods.Review of Financial Studies,9,1211–1250.
[4]Bunch,D.S.,Johnson,H.(1992),A simple and numerically e?cient valuation method
for American puts using a modi?ed Geske-Johnson approach.Journal of Finance,47, 809–816.
[5]Burlisch,R.(1964),Bemerkungen zur Romberg-Integration.Numerische Mathematik,
6,6–16.
[6]Carr,P.(1998),Randomization and the American put.Review of Financial Studies,
11,597–626.
[7]Chang,C.C.,Chung,S.L.,Stapleton,R.C.(2002),Richardson extrapolation techniques
for the pricing of American-style options.Working paper,Management School,National Central University,Taiwan.
[8]Cox,J.,Ross,S.,Rubinstein,M.(1979),Option pricing:A simpli?ed approach.Jour-
nal of Financial Economics,7,229–263.
[9]Deu?hard,P.(1983),Order and stepsize control in extrapolation methods.Numerische
Mathematik,41,399–422.
[10]Geske,R.,Johnson,H.(1984),The American put option valued analytically.Journal
of Finance,39,1511–1524.
[11]Heston,S.,Zhou,G.(2000),On the rate of convergence of discrete-time contingent
claims.Mathematical Finance,10(1),53–75.
[12]Ho,T.S.,Stapleton,R.C.,Subrahmanyam,M.G.(1997),The valutation of American
options with stochastic interest rates:a generalization of the Geske-Johnson techinque.
Journal of Finance,57,827–839.
[13]Huang,J.,Subrahmanyam,M.,Yu,G.(1996),Pricing and hedging American options:
a recursive integration method.Review of Financial Studies,9,277–300.
[14]Ju,N.(1998),Pricing an American option by approximating its early exercise boundary
as a multipiece exponential function.Review of Financial Studies,11,627–646. [15]Kyprianou,A.E.,Pistorius,M.R.(2003),Perpetual options and canadization through
?uctuation theory.Annals of Applied Probability,13(3),1077–1098.
12
[16]Leisen,D.P.J.(1999),The random-time binomial model.Journal of Economic Dynam-
ics and Control,23,1355–1386.
[17]Omberg,E.(1987),A note on the convergence of the binomial pricing and compound
option models.Journal of Finance,42,463–469.
[18]Tian,Y.S.(1999),A?exible binomial option pricing model.Journal of Futures Markets,
19(7),817–843.
13
Table1:RMS relative errors of randomized American put option prices when Richardson ex-trapolation is applied repeatedly in Carr’s randomization approach(S=100,X∈[70,80], r∈[0.01,0.12],σ∈[0.1,0.5],T=1).
n i RMSE n i RMSE n i RMSE n i RMSE
10.1422057620.0897662520.0897662520.08976625
20.0376297340.0177381440.0177381440.01773814
30.0139109260.0054912760.0054912780.00466951
40.0059046080.0022215580.00222155160.00147634
50.00285097100.00121348120.00114269320.00060459
60.00170553120.00078884160.00069349640.00026906
70.00118567140.00055291240.00043189
80.00087775160.00040649320.00028092
90.00067173180.00031016480.00018259
100.00052799200.00024374640.00012264
Table2:RMS relative errors of randomized American put option prices when Richardson ex-trapolation is applied repeatedly in Carr’s randomization approach(S=100,X∈[80,90], r∈[0.01,0.12],σ∈[0.1,0.5],T=1).
n i RMSE n i RMSE n i RMSE n i RMSE
10.1782857720.1083311720.1083311720.10833117
20.0391164340.0164472040.0164472040.01644720
30.010*******.0039457560.0039457580.00335649
40.0039570280.0016013280.00160132160.00108761
50.00200959100.00091801120.00086479320.00045836
60.00129208120.00059881160.00052616640.00020470
70.00090593140.00041895240.00032749
80.00066608160.00030823320.00021353
90.00050842180.00023556480.00013943
100.00039982200.00018548640.00009427
14
Table3:RMS relative errors of randomized American put option prices when Richardson ex-trapolation is applied repeatedly in Carr’s randomization approach(S=100,X∈[90,100], r∈[0.01,0.12],σ∈[0.1,0.5],T=1).
n i RMSE n i RMSE n i RMSE n i RMSE
10.1770763020.1011257120.1011257120.10112571
20.0260186640.0097953740.0097953740.00979537
30.0052555960.0021737460.0021737480.00188378
40.0022323980.0010196280.00101962160.00069572
50.00130805100.00059122120.00055669320.00029425
60.00083735120.00038419160.00033753640.00013142
70.00058107140.00026869240.00021001
80.00042712160.00019764320.00013698
90.00032618180.00015104480.00008966
100.00025645200.00011900640.00006093
Table4:Percent variation of mean absolute relative errors along the diagonal of the extrap-olation tableau in Carr’s randomization approach(S=100,X∈[90,100],r∈[0.01,0.12],σ∈[0.1,0.5],T=1).
n i?%MAE n i?%MAE n i?%MAE n i?%MAE
1222
2-86.144-90.924-90.924-90.92
3-80.846-77.516-77.518-80.44
4-54.728-51.948-51.9416-62.24
5-40.3610-41.8812-45.2832-57.71
6-35.9212-35.0416-39.4164-55.49
7-30.5714-30.1424-37.89
8-26.4916-26.5532-34.92
9-23.6918-23.6948-34.75
10-21.4520-21.3364-32.34
15
Table5:Mean absolute relative errors of put option prices in the CCR framework when Richardson extrapolation is applied repeatedly(S=100,X=100,r∈[0.01,0.12],δ∈[0.01,0.12],σ∈[0.1,0.5],T=1).The results refer to a basic step T/200and the harmonic (second column),Deu?hard(fourth column),Burlisch(sixth column)and Romberg(eighth column)sequences.
n i MAE n i MAE n i MAE n i MAE
2000.000851324000.000422924000.000422924000.00042292
4000.000025168000.000013878000.000013878000.00001387
6000.0000267812000.0000147712000.0000147716000.00000984
8000.0000408416000.0000208716000.0000208732000.00000769
24000.0000200064000.00000691 Table6:Mean absolute relative errors of put option prices in the CCR framework when Richardson extrapolation is applied repeatedly(S=100,X∈[90,100],r∈[0.01,0.12],δ∈[0.01,0.12],σ∈[0.1,0.5],T=1).Extrapolation tableau with Romberg stepsize sequence and basic number of steps200.
n i T i1T i2T i3T i4T i5
4000.00044412
8000.000222410.00045825
16000.000111210.000225380.00041994
32000.000055400.000115100.000213500.00029184
64000.000024930.000053760.000101150.000140210.00016512
16
Table7:Mean absolute relative errors of put option prices in the?exible binomial model when Richardson extrapolation is applied repeatedly(S=100,X∈[70,100], r∈[0.01,0.12],δ∈[0.01,0.12],σ∈[0.1,0.5],T=1).?%MAE is the percentage of variation of the mean absolute errors along the diagonal of the extrapolation tableau. Extrapolation is based on Romberg stepsize sequence and basic step T/100.
n i X∈[70,80]?%MAE X∈[80,90]?%MAE X∈[90,100]?%MAE 2000.003921740.002562740.00126017
4000.00019418-95.050.00010093-96.060.00003225-97.44
8000.00012275-36.790.00006944-31.200.00001982-38.53 16000.00006096-50.340.00003443-50.410.00001027-48.19 32000.00002719-55.400.00001634-52.540.00000587-42.83 64000.00001640-39.680.00001080-33.920.00000508-13.50 Table8:Mean absolute relative errors of put option prices in the?exible binomial model when Richardson extrapolation is applied repeatedly(S=100,X∈[100,130], r∈[0.01,0.12],δ∈[0.01,0.12],σ∈[0.1,0.5],T=1).?%MAE is the percentage of variation of the mean absolute errors along the diagonal of the extrapolation tableau. Extrapolation is based on Romberg stepsize sequence and basic step T/100.
n i X∈[100,110]?%MAE X∈[110,120]?%MAE X∈[120,130]?%MAE 2000.000701330.000430710.00027674
4000.00001673-97.610.00001241-97.120.00001194-95.68 8000.00000930-44.420.00000799-35.580.00000784-34.33 16000.00000554-40.420.00000500-37.430.00000410-47.76 32000.00000391-29.450.00000294-41.300.00000192-53.05 64000.00000345-11.680.00000221-24.770.00000137-28.59
17