|
Article Excerpt
1. Introduction
The numerical valuation of the standard American put option, and other more complex American-style securities, is still the concern of many research studies. The lack so far in the literature of analytical solutions and the fact that most traded options are American style, allowing them to be exercised before maturity, implies that "efficient" algorithms in terms of accuracy and speed to price these options are valuable.
There are many different algorithms that price the American put option. Cox et al. (1979) introduce binomial trees. Brennan and Schwartz (1977) introduce the finite difference approach. (1) MacMillan (1986), Barone-Adesi and Whaley (1987), Bunch and Johnson (1992), and Ju and Zhong (1999) among others consider quasi-analytical solutions. Other recent approaches are as follows: Broadie and Detemple (1996) introduce two approximations based on lower and upper bounds. Huang et al. (1996) introduce a recursive method based upon the decomposition of the American option. Carr (1998) uses randomization. Ju (1998) approximates the optimal exercise frontier, and Chiarella et al. (1999) and Sullivan (2000) approximate the value function of the equivalent dynamic programming problem.
This paper presents a detailed analysis of the numerical implementation of one method, the decomposition of the standard American put option into an equivalent European option plus an early exercise premium. It then gives a new algorithm based upon this decomposition and Richardson's extrapolation. The novelty of this algorithm is based upon (a) the derivation of the correct order for the error term when applying Richardson extrapolation, which is used to control the error of the extrapolated prices, (b) an innovative adjustment of Kim's (1990) discrete-time early exercise premium, so that these premiums monotonically converge and, therefore, it is appropriate to use them in extrapolation, and (c) the optimal exercise frontier can be quickly computed through Newton's method, permitting the efficient implementation of the decomposition formula in practice. Numerical experiments show that this new algorithm is accurate, efficient, easy to implement, and competitive in comparison with other methods.
Richardson's extrapolation was introduced by Geske and Johnson (1984) to accelerate the computation of American option prices. The extrapolation method works so well that most American option pricing methods employ the extrapolation idea. American-style securities are priced by numerical algorithms, which yield a price P([DELTA]t) that approximates the true American price [P.sup.A]. Then, to gain in efficiency (speed and accuracy), extrapolation can be used to derive a price [P.sup.E] from a series of prices P([DELTA][t.sub.1]), P([DELTA][t.sub.2]),... , P([DELTA][t.sub.J]), where [DELTA][t.sub.1] > [DELTA][t.sub.2] > ... > [DELTA][t.sub.J] > depend on the option maturity T, P(0) should be equal to [P.sup.A], and in practice the number of prices J [greater than or equal to] 2 is small. A general misunderstanding of this literature is that the error of the extrapolated price [P.sup.A] - [P.sup.E] is the order [alpha]O([([DELTA]t]).sup.J]), where [alpha] is a constant and [DELTA]t is not specified in general. However, we show in Lemma 1 that this error depends, indeed, on every price used for extrapolation and is equal to [alpha]O([DELTA][t.sub.1][DELTA][t.sub.2] ... [DELTA][t.sub.J]).
This implies that (a) the error depends on the option maturity T and, indeed, it is much greater for long-term options; (b) the first prices of the series P([DELTA][t.sub.1]), P([DELTA][t.sub.2]),..., which are easier to compute, introduce the greater portion of the error and, hence, it could be inefficient to use them for extrapolation; and (c) it is possible to make the error of the extrapolated price, [P.sup.A] - [P.sup.E], consistent with the needed "accuracy." We can use the error order [alpha]O([DELTA][t.sub.1][DELTA][t.sub.2] ... [DELTA][t.sub.J]) to choose the numbers [DELTA][t.sub.1], [DELTA][t.sub.2],..., [DELTA][t.sub.J], which depend on the option maturity T, such that this error is systematically less, for instance, than one cent. This last point is our concept of "robustness." On the other hand, a measures whether the prices P([DELTA]t) smoothly converge to the true price [P.sup.A]. For instance, if P([DELTA]t) is approximately linear on [DELTA]t, then [alpha] [approximately equal to] and the extrapolated prices will be accurate. On the contrary, if, for example, P([DELTA]t) is not monotonic in [DELTA]t, then [alpha] [not equal to] and the extrapolated prices will be less accurate. Therefore, extrapolation combined with an appropriate and convergent algorithm can produce an efficient and robust method. (2)
In a series of papers, Kim (1990), Jacka (1991), and Carr et al. (1992) develop the decomposition formula. The early exercise premium is a function itself of the American option optimal exercise frontier, which is also unknown. The simultaneous determination of the frontier and the early exercise premium makes the application of this decomposition difficult. Huang et al. (1996) and Broadie and Detemple (1996) have used this method. Huang et al. (1996) use the Kim (1990) discrete-time decomposition and Broadie and Detemple (1996) work out briefly the continuous-time decomposition to recursively compute the optimal exercise frontier. However, both note that this procedure is time consuming. Huang et al. (1996) note that to compute more than three or four points is expensive and, therefore, use Richardson extrapolation. Broadie and Detemple (1996) do not work out this method in detail, because they show that computing four points from the nonlinear integrals produces a nonmonotonic frontier, which is theoretically inaccurate. In summary, the critical issue in implementing this decomposition is to efficiently compute the points of the optimal exercise frontier.
In a recent paper on pricing American options by simulation, Ibanez and Zapatero (2003) show that any point along the optimal exercise frontier, for the American put or for more complex American options, can be computed as the fixed point of a simple algorithm. Here, we apply and develop this observation. Option prices are smooth and convex functions of the underlying price. Therefore, the fixed point can be quickly computed by the Newton method in a few iterations and with no convergence issues. The Newton method also requires us to compute a derivative, but this derivative is just the option delta, which is also known from this decomposition. Therefore, it is possible to give a Newton-type algorithm, where all inputs are analytically computed, which solves the critical issue in implementing the American put option decomposition. Afterwards, we modify Kim's (1990) discrete-time early exercise premium so that convergence to the true American early exercise premium can be monotonic. The numerical experiments show that the extrapolated price errors produced from this monotonic series are then much lower. Besides, we price Bermudan options with 2,000 or more exercise periods and show that these prices have similar accuracy to binomial prices with equal number of periods and, therefore, could also be used as benchmark prices.
Ju (1998) approximates the optimal exercise frontier by exponential functions and then produces an efficient algorithm. However, Ju's (1998) method has possible limitations. First, it depends on a flat or exponential approximation for the frontier shape, which may not be appropriate for short-term options. Second, the algorithm initial points must be carefully chosen to avoid convergence issues (see AitSahlia and Lai 2000). Third, it could be difficult to apply this method to other exotic options. For instance, Hansen and Jorgensen (2000) show that the optimal exercise frontier for American-Asian-style options is a nonmonotonic function and, therefore, the Ju (1998) approach could not be used straight away.
Broadie and Detemple (1997), Hansen and Jorgensen (2000), and Gao et al. (2000) have also decomposed more complex American-style options into an equivalent European option plus an early exercise premium for exotic, Asian, and barrier options, respectively. Therefore, these extensions show that the decomposition technique is a general technique that could be applied to most American-style options, and that its numerical implementation is an alternative numerical method to finite difference or trees methods. For instance, in pricing and hedging barrier options close to the barrier, one must be careful when implementing trees methods, but Gao et al. (2000) show that the decomposition technique is robust and does not present these shortcomings. In the interest of brevity, and given that the American put option is well established in the literature, the application of our algorithm to these more complex securities is best left for future research.
The rest of this paper is organized as follows: [section] 2 presents a simple, brief background of the American put option decomposition. Section 3 presents numerical properties of this decomposition. Section 4 analyzes Richardson extrapolation. Section 5 presents the new algorithm. Section 6 presents numerical results and [section] 7 concludes this paper.
2. A Review of the American Put Option Decomposition
We assume a standard continuous time and frictionless market model. The stock price [S.sub.t] follows a lognormal process
(1) d[S.sub.t] = (r - q)[S.sub.t]dt + [sigma][S.sub.t]d[z.sub.t]
under the risk-neutral measure, Q. The interest rate r, the dividend or convenience yield q, and the volatility [sigma] are constants. For simplicity, let us assume that q=0.
Black and Scholes (1973) show that the nonarbitrage price of a European put option, [p.sub.t]([S.sub.t]), with strike price K and maturity at T, is given by
(2) [p.sub.t]([S.sub.t]) = [E.sub.Q][[e.sup.-r[tau]] [{K-[S.sub.T]}.sup.+]|[S.sub.t]] = [Ke.sup.-r[tau]]N(-[d.sub.2] ([S.sub.t], K, [tau]))-[S.sub.t]N(-[d.sub.1]([S.sub.t], K, [tau])),
where [tau] = T - t, N() is the standard normal distribution, and...
|
