American option, which could be exercised optimally before the expiration date, enables the holders choose to buy or sell the option according to their judgement. It takes a large proportion of traded options around the world with the increase in the type of derivatives. In reality, the pricing of American option is an optimal stopping problem as consumers would choose the best stopping time to achieve the highest payoffs. In contrast, the European option which could only be exercised at the expiration time may be determined in closed-form in those cases.
The value of European option was derived from the classical Black-Scholes formula developed by Black and Scholes(1973) based on the assumption that price of asset changes continuously in a way that produces lognormal distribution for the price at a future time. But there are other alternative processes of asset's price that could be assumed.
While the valuation of American option has always been a challenging problem in financial mathematics, especially when it involves several underlying assets, yet various methods have been presented to solve the problem. And the value of American option could be derived by binomial trees, finite difference schemes, quadrature routines or Monte Carlo simulation , among which binomial trees is backward solving used to calculate the option value at each preceding node. However, with the rapid development of the options market, a variety of new financial products have been developed as the market demands and a number of exotic options are no longer confined to a single underlying asset. The payoff on the maturity date may possess the path-dependent features, thus it is not feasible to use the binomial model to evaluate the possible increase in payoff exponentially with the increase in time. But the Monte Carlo simulation is quite effective and flexible in dealing with a number of underlying assets and the issue of path dependence. Yet Monte Carlo simulation can only be the solution of the past time (forward solving). We can not calculate the expected payoffs derived from the continuation of holding the option and it can not be compared with the payoffs derived from the immediate exercise. Thus it is hard to decide whether to continue or exercise now. Based on this, Hull(1993) made Monte Carlo simulation that can only be used to evaluate the European derivative securities rather than American option several years ago.
The problem was partly solved by Tilley(1993), who proposed an algorithm model for pricing American option by a path simulation model that mimics the standard lattice method to calculate the value of the option from continuation equaling the present value of the expected option value for the next period .
Monte Carlo simulation has always been an active research area due to its advantages in pricing path-dependent option and in employing to solve high dimensional problems with multiple assets.
Longstaff and schwarz(2001) presented a simple least-square approach, which has the significant effect on pricing of American option. It has been applied as a standard solution to value the American option by simulation. However, it actually requires the selection of basis functions and the set of optimally exercisable dates. While its convergence depends on the number of each being infinite (cf. Clement et al. 2002), the practical number is restricted to be finite obviously. Tsitsiklis and Van Roy(2001) proposed a method, of which the same type of recursive algorithm is presented.
Afterwards, there are many literatures associated with least-square Monte-Carlo simulation. Broadie and Detemple (2004) engage in an investigation in pricing approach of recent trends of option valuation for basis function methods, and Lai and Wong (2004) review these approaches with the objective of understanding the basis on which to make the choice of basis function. The variance reduction techniques are discussed by Bolia and Junjeja (2005) and Moreni (2004) for the basis function methods. In addition, Stentoft (2004) and Glasserman and Bin (2004) present convergence analyses for the choice of basis function, including Monte-Carlo LSM , under different assumptions on the stochastic processes.
Additionally, there are other authors introducing some other advanced methods of valuation of American option on the basis of LSM algorithm. F or example, Glasserman et al (2004) argues that a weighted average quasi- Monte Carlo (WLSQM ) proposed by the weighted least-square regression is better than LSM method in that it can produce less disperse estimates of the option price. However, this proof of convergence of estimators assumes constant volatility and there is no finite-sample proof of convergence.
The paper wrote by Longstaff and Schwartz (2001) suggests us a convergence result in the simplest situation with only one variable and one early exercise time. Clement et al. (2002) proves that convergence of the LSM algorithm is an approximation, in the limit, to the true price of American option. The reason is that only a fixed and finite number of regressors are used in the relevant cross-sectional least squares regression.
The purpose of my paper is to introduce the principle and procedure of the method in the view of algorithm and to analyze the accuracy of the algorithm compared to finite differences by using matlab. The article is organized as follows. Chapter 2 presents background knowledge associated with the LSM technique. Chapter 3 describes the procedure of algorithm for LSM by simulation. Chapter 4 discusses the convergence results and the implementation issues related to the algorithm. Chapter 5 provides an example for results of American option value simulated by LSM and an comparison of values implied by both finite difference and Monte-Carlo LSM methods. Chapter 6 is the conclusion section.
Chapter 2 Background
2.1 Markov process
Definition: Let (,F,P) be a probability space, let T be a fixed positive number, and let F(t), 0tT, be a filtration of sub--algebras of F. Consider an adapted stochastic process X(t), 0tT. Assume that for all 0stT and for every nonnegative, Borel-measurable function f, there is another Borel-measurable function g such that
E[f(X(t)) ]=g(X(s))
Then we say that the X is a Markov process.
2.2 Wiener process
Brownian motion is described as Wiener process, which is a particular Markov stochastic process with a mean change of zero and variance rata of 1 per year. It has two properties as follows:
Property 1: The change â-³z during a small period time â-³t is:
, where has a standard normal distribution N(0,1).
Property 2: The values of â-³z for any two different short intervals of time, â-³t are independent.
The change in values of Z in the period time T are denoted as: Z(T)-Z(0) and T can be divided into N intervals . According to definition, E[Z(T)-Z(0)]=0,Var[Z(T)-Z(0)]=Nâ-³t=T.
2.3 Laguerre polynomials
The Laguerre polynomials, named after Edmond Laguerre, are the canonical solutions of Laguerre's equation:
xy"+(1-x)y'+ny=0
which is a second-order linear differential equation that has nonsingular solutions as long as n is a non-negative integer. The Laguerre polynomials are also applied in Gaussian quadrature to numerically compute integrals of the form
These polynomials, usually expressed as,,…, are a polynomial sequence that may be defined by the formula:
They are orthogonal mutually with regard to the inner product given by
2.4 Hilbert space
Definition. A Hilbert space is a vector space endowed with an inner product and associated norm and metric, such that every Cauchy sequence (a sequence whose elements become arbitrarily close to each other as the sequence progresses) in H has a limit in H.
An example of a Hilbert space is the space ：
The space is the collection of Borel measurable real or complex valued square integrable functions f on (a,b), i.e., ，endowed with inner product and associated norm and metric ， and
,
respectively, where the integrals involved are Lebesgue integrals.
2.5 process
Definition Let W(t),t0, be a Brownian motion, and let F(t), t0, be an associated filtration. An process is a stochastic process of form
Where X(0) is nonrandom and (u) and (u) are adapted stochastic processes.
It is supposed that the value of a variable x follows process,
dx=a(x,t)dt+b(x,t)dz, where dz is a Wiener process and x has a drift rate of a and a variance rate of . f is a function of x and t.
lemma shows that :
(1)
We define:
G=lnS
Since ,,
From (1) we obtain that the process followed by G is:
Since and are constants, the function reveals that G=lnS follows a general Wiener process with constant drift rate of and variance rate of . The change of lnS fits normal distribution with mean value of and variance of .
That is :
2.6 Black-Scholes model
We assume that stock price follows the stochastic process:
dS=µSdt+σSdz (2)
suppose that G is the price of put option of other derivative securities. G is the function of S and t.
from (1):
(3)
Discrete version of (2) and (3):
(4)
and (5) are tiny changes in G and S in a small time interval.
The holder of this portfolio will short one derivative and long an amount
of shares. The value V=-G+S (6)
The change in the value in is given by: V=-G+S (7)
Substitute (4) and (5) into (7) yields:
(8)
The arbitrageurs could make a profit by borrowing money to short it when it earned more than this return or sell it when it earned less.
(9)
So that (10), which is the Black-Scholes-Merton differential equation.
The Black-Scholes formula calculates the price of European put and call options. The value of a call option for a non-dividend paying underlying stock in terms of the Black-Scholes parameters is:
The price of a corresponding put option is:
Where T-t is the remaining time to maturity, K is the strike price, S is current price of option, r is riskless interest rate, is the volatility of stock return and N is normal distribution function.
2.8 Valuation of American option
Brennan and Swartz (1978) substituted the variable into (10) to obtain a PDE with the constant coefficients:
(11), where S0 is the initial price of the underlying asset and H is the value of option.
To simplify equation (11) further, according to Curtardon[1982], it is defined :
]
(12)
,
where t is the remaining time to maturity date.
Substitute some replacing variables, it is obtained as below:
(13)
Values of an option with barriers must accord to following equation ( 4)with the one or two following boundary constraints :
, (14)
where:
correspond to the upper and lower boundary.
The initial conditions for call options and put options are:
(15c)
(15p)
2.9 Finite difference methods
Finite difference methods price a stock by solving the differential equation that the stock satisfies. The equation is converted into difference equations that are solved iteratively. We use V to denote the value of option.
The option paying a dividend yield of q must satisfy the option:
Construct a coordinate axis with variable X denoting horizontal dimension and variable t denoting vertical dimension.
, i = 0,...,
j = 0,...,
where
,
With Xmax and Xmin denote the boundary conditions (14), Texp is the remaining time to expiration date, Nt and NX are a number of time and variable X partitions.
To obtain a finite difference approximation to equation (13), partial derivatives are replaced by finite differences:
(16)
(17)
is calculated in two different ways:
(18e)
or
(18i)
Approximation (18e) (18i) are used in the explicit and implicit finite difference method, respectively.
Substituting (16), (17) and (18e) into (13), we obtain the following explicit finite difference equation:
(19e)
Substituting (16), (17) and (18i) into (4), the following explicit finite difference equation is obtained:
(19i)
,
Then equations (19e) and (19i) are denoted as
(20e)
(20i)
The initial conditions (15c) and (15p) are expressed as:
(21)
2.10 Monte-Carlo methods
According to relevant option theory, it is supposed that the expiration date is T, and the exercise date is T*, T=T* for European option, as the European option could only be exercised at the expiration date. But for American option, it could be exercised any day before expiration date, T* [0, T]. The value of option at exercise date will not only be influenced by underlying asset price at time t, but also affected by the sample path from t=0 to maturity. Therefore, the option value at time T* is : , where is expectation value under risk-neutral measure, r is riskless discount rate and random samples of the underlying asset price path is generated by using the Monte Carlo simulation option pricing through the first step. Risk-neutral stock price process is assumed to follow the stochastic differential equation:
(22), where dS is sub-change in underlying asset price, is volatility of underlying asset price , z is standard Brownian motion and dz is Brownian increments, , is a random sample following a standard normal distribution.
Under the assumption of risk neutral, is replaced by r. According to Ito formula , the formula (22) can be rewritten as:
(23). In above two formulas, using lnS is more accurate than using S, because the simulation in (22) would have high order of error o(â-³t) for â-³t. If and only if â-³t→0, formula (23) is correct and accurate. But for (23), it is correct regardless of whether the value of â-³t is approximate zero or not.
In order to use Monte-Carlo method, the interval [0,T] should be divided into N subintervals with length of t=T/N. Thus (23) could be rewritten as:
(24), where i , ~(0,1).
From (24), given initial underlying asset price , at any time ,
(25), where sample paths of underlying asset prices are obtained.
The key advantage of Monte Carlo simulation is that it can be applied to the situation where the payoff depends on the path followed by the underlying variable S as well as where it depends only on the final value of S. Payoffs can occur at several exercisable times before the expiration time of option instead of all in the end.
2.11 Numerical example for LSM
In order to price American option, we have to decide whether to exercise or continue holding. It is optimal to exercise if immediate exercise is more valuable than the expected cash flow resulting from continuing holding. Many researchers including Longstaff and Schwartz have proposed many valuation methods based on Monte-Carlo simulation. The approach is done by using a least square to decide the best-fit relationship between expected cash flows from holding on a set of basis function and the values of relevant variables at each time an early exercise decision has to be made. It will be explained through the numerical example provided by original paper.
Consider a 3-year American put option on a share of non-divided-paying stock that could be exercised at time 1, 2 and 3 with initial price of 1.00, riskless rate of 6% and strike price of 1.10. The sample paths are generated as follows:
Sample paths for put option example:
path
t=0
t=1
t=2
t=3
1
1.00
1.09
1.08
1.34
2
1.00
1.16
1.26
1.54
3
1.00
1.22
1.07
1.03
4
1.00
0.93
0.97
0.92
5
1.00
1.11
1.56
1.52
6
1.00
0.76
0.77
0.90
7
1.00
0.92
0.84
1.01
8
1.00
0.88
1.22
1.34
table1
Assume that the option can be exercised until the final maturity date at time 3, the cash flows are identical to their intrinsic value.
Cash flow if exercise only at time 3:
path
t=1
t=2
t=3
1
0.00
0.00
0.00
2
0.00
0.00
0.00
3
0.00
0.00
0.07
4
0.00
0.00
0.18
5
0.00
0.00
0.00
6
0.00
0.00
0.20
7
0.00
0.00
0.09
8
0.00
0.00
0.00
Table2
If the put option is in the money at time 2, the option holder should decide whether to hold or not. Table 1 above illustrates that paths 1,3,4,6,7 are in the money. Thus we assume an approximate relationship:
where S is the share price at time 2 and V denotes the corresponding discounted cash flows. The share prices S and corresponding values V for path 1,3,4,6,7 are 1.08, 1.07,0.97.0.77,0.84 and 0.00, 0.07,0.18,0.20,0.09, respectively. By regressing these values to obtain the minimum value of following formula:
a=-1.070,b=2.983,c=-1.813
Therefore, the best-fit relationship is
With this function, we can calculate the expected value of option from continuation, 0.0369. 0.0461, 0.1176, 0.1520, 0.1565, respectively. From table 1, the value from immediate exercise is 0.02, 0.03, 0.13, 0.33 and 0.26, meaning that it is optimal to exercise at time 2 along the paths 4, 6 and 7.
path
t=1
t=2
t=3
1
0.00
0.00
0.00
2
0.00
0.00
0.00
3
0.00
0.00
0.07
4
0.00
0.13
0.00
5
0.00
0.00
0.00
6
0.00
0.33
0.00
7
0.00
0.26
0.00
8
0.00
0.00
0.00
The table 3 shows the cash flows received at time 2 or 3.
The in-the-money paths at time 1 are 1, 4, 6, 7 and 8. Values of share along these paths and corresponding continuations values discounted back to time 1 are 1.09, 0.93, 0.76, 0.92, 0.88 and 0.13 , 0.33 ,0.26 ,0.00 respectively. Thus the approximation function is:
Substituting value of S into the regression the estimated conditional expectation function for paths 1, 4, 6, 7, 8, the value can be obtained as 0.0139, 0.1092, 0.2866, 0.1175, 0.1533. From table 1, the value from exercising is 0.01, 0.17, 0.34, 0.18, 0.22, which means that it is optimal to exercise at time 1 for paths 4, 6, 7, 8.
path
t=1
t=2
t=3
1
0.00
0.00
0.00
2
0.00
0.00
0.00
3
0.00
0.00
0.07
4
0.17
0.13
0.00
5
0.00
0.00
0.00
6
0.34
0.33
0.00
7
0.18
0.26
0.00
8
0.22
0.00
0.00
The table 4 summarizes all cash flows. The value of option could be calculated by averaging all discounted cash flows from each path back to time zero at riskless rate.
Since the value is greater than 0.10, it is optimal to holding the options.
As shown by the numerical example, the LSM is nothing but regression involved in calculation.
Chapter 3: The valuation algorithm for Monte-Carlo LSM
3.1The valuation framework
We will consider an underlying probability space(,F,P) with a discrete time within the time horizon [0,T], where is the set of all possible states of stochastic result within the period and w represents a specific sample path. Let F be a field of distinguishable events at time T, and P is the probability of F. On top of this space, it is also assumed an equivalent martingale measure Q.
According to Benoussan(1984) and Karatzas(1988) the value of American option should equal the maximum discounted cash flows that is taken over all discrete stopping times given by the filtration F of the option, that is Snell envelope. The notation C(w,s;t,T) is introduced to represent cash flows generated from each path of option which has not been exercised before time t and holders follow the optimal stopping rule for s, t<s
The purpose of LSM is to provide an approximation for the optimal stopping rule in order to obtain maximized value of option from each path. w is the sample simulated path and let t to be the discrete time node in T, 0t1t2t3…t=T, at which the American option could be exercised and optimal stopping policy should be considered at each exercise date. To make the simulation possible, K is taken as sufficiently large in the LSM algorithm to approximate the value of these options.
At each exercise time node, the investors should compare whether the payoff P(S(w)) from immediate exercise is greater than expected value F(w; t) from holding in order to determine the exercise time. Payoffs are known while the expected holding values are unknown. From no-arbitrage valuation theory, the value of continuation is equivalent to expected value of discounted cash flows. Under the assumption of the risk-neutral pricing measure Q, the holding value F(w; t) can be denoted as:
∣] (Longstaff(2001)), where r(w,t) represents risk-free discount rate and denotes the cash flow generated at the sample path w, which should be satisfied that the option cannot be exercised until tk. As the option has only one chance to exercise, there is no more than one node tj to make ＞0.
3.2 The procedures and algorithm of LSM
Least square method is used to estimate conditional expectation function at each time node. As cash flows C(w,s;t,T) arising from each path of the option is worked recursively, C(w,s; t,T) could be different from C(w,s; t,T) when the option is optimally exercised at t, thus changing all subsequent cash flows along the sample path w. There is an assumption that the function of F(w; t) can be expressed as a linear combination of a finite number of basis function that could be justified when conditional expectation is an element of the L² space of square-integrable functions.
Since L² is Hilbert space, the theory on Hilbert spaces is that any function that belongs to the Hilbert space could be expressed as a linear function of basis vectors for the space (Royden 1988). Assume that variableX is the value of option and follows a Markov process.
the cross-sectional regressions by the LSM method could be used to determine the conditional expectation function:
, where is the j'th Laguerre polynomial evaluated at, α and are estimated coefficients of function. In LSM algorithm, we use and note that although = 1 corresponds to the constant coefficient, is the first weighted Laguerre polynomial.The set of weighted Laguerre polynomials are:
(17)
(18)
(19)
(20)
We write ∣] and can be also represented as :
, where is unknown and should be estimated when implementing the procedures. can be estimated by regressing the cash flows that are only along the in-the-money paths. According to Amemiya(1985), it is claimed that is the best linear unbiased estimator of and 0＜M＜∞. In addition, White(1984) indicated that when the number of paths is infinite, calculated by regression would converge to in probability and mean square.
Longstaff and Schwartz (2001) claimed that American style options are priced based on the first 3 weighted Laguerre polynomials and a constant term and 3 basis functions are sufficient to effectively converge to the algorithm of the regressions. However, different combination of K and M should be considered as it may have an influence on price estimates. There are two biases that may affect the price estimates as follows. The first bias is that as the conditional expectation is estimated, it may appear some residual errors that arise from approximation, which could be smaller with the increase in the number of regressors. In addition to this, use the same path to estimate the conditional expectation function and to calculate the estimated value of the option, resulting in a high level of bias which could also vanish with the increase of the number of simulated paths. Yet the actual bias will depend on both the number of simulated paths and basis functions.
The basic procedures for LSM are as follows. Given the fixed path obtained in using Monte-Carlo methods, in order to obtain the optimal exercise time and relevant payoffs, the calculation of LSM algorithm initiates cash flows with payoffs on the expiration date t for all paths and discount the value of cash flows back to time t. Then approximate F(w, t) by orthonormal basis and least square which is done by regressing C(w,s; t,T) using M basis functions along the in-the-money path. To estimate coefficients , minimum value of following equation needs to be yield:
Once the conditional expectation value function at time t is determined, then it can be compared with that of immediate exercise to determine the optimal stopping rule whether to hold or exercise. The value of cash flow at time t is known. We could repeat the procedure s in the previous section until optimal exercise times along each path have been identified. Once the optimal exercise time is determined, the optimal value of cash flow can then be approximated.
The final procedure is to average all the discounted optimal cash flows from each path resulting from LSM rule of exercising when immediate exercise value is greater or equal to.
, where C(wi) is the discounted cash flow along the path wi. The optimal time and payoffs from option could also be obtained. As optimal exercise time is distinguishable from each path, the riskless discounted factors applied to cash flows from each path are different too.
When the set of basis function involves variables X and Y, the function should include terms of X and Y as well as the interaction term of X and Y. It suggests that the number of basis function would exponentially increase with the dimensionality of the problem.
The detailed process of LSM is illustrated by the following diagram.
Create sample paths by Monte Carlo method
Initialize cash flow matrix with payoffs on expiration
Calculate underlying values along each path
Find in the money path(IMP) and its value
t(i)=t(i-1)
Make regression
Determine optimal stopping time and record corresponding expected value.
Update cash flow by optimal values
Discounting all values
Averaging values over all paths
t(i)=t(n)=T
t(i)=t(n-1)
If IMP>0
If IMP=0
If t(i)=0
If t(i)>0
3.3 Valuing American Put Option
We are intrigued in estimating value of American put option, where the risk-neutral stock price process is assumed to follow the stochastic differential equation
dS=rSdt+σsdZ, where Z is a standard Brownian motion, r and σ are constants and no-dividends paid. According to Longstaff and Schwartz (2001), it is also assumed that the put option could be exercised 50 times per year at a strke price of K prior to maturity date T. Since using more than three basis functions does not change the numerical results, three basis functions are enough to obtain the level of accuracy. By using the equations (17)~(19), on which we regress discounted realized cash flows, we could estimate the conditional expectation function.
Chapter 4. Assessing the LSM method
4.1 Convergence result
Although LSM provides a simple way to obtain the optimal value strategy for American option, it depends on the number of basis functions and paths. The convergence result of LSM is to imply that the estimated price from above LSM algorithm is actually convergent to the true price of the option when the conditional expectation approximation converges to the true expectation.
There are two propositions in original paper. The first proposition addresses the bias of the LSM algorithm.
Proposition 1. For any choice of M, K, and vector representing the coefficients for the M basis functions at each of the K-1 early exercise dates, let LSM(;M,K) denoted cash flow resulting from following the LSM rule of exercising when the immediate exercise value is positive and greater than or equal to as defined by . Then the following inequality holds,
Where LSM(;M,K) denotes the discounted cash flow estimated by using LSM when these cash flows are in the money.
The underlying implication is easy to understand. The pricing of American option is identified by using optimal stopping rule, which aims to maximize the value of American option. Therefore, it leads to values indicated by optimal stopping rule greater or equal to that implied by other stopping rules.
Proposition 2 claimed by Longstaff and schwarz(2001) is that the value of American option depends on the variable x which is defined in the range of (0, ) and follows Markov process. Assume further that the option can only be exercised at t1 or t2, and the conditional expectation function is absolutely continuous and satisfies that
,
, and for any ＞0, there is an M＜ to make that:
︳︳＞ =0
From the proposition, it is known that as long as N goes to infinity and M is large enough, then the difference between the estimated price resulting from LSM rule and actual price would be less than, and is arbitrary positive. The result of convergence is great in that the is uniformly convergent to the conditional function. While this proposition is valid to one-dimensional settings, it is deemed to be valid for higher-dimensional settings. Therefore, value of option identified by LSM actually represents the true price.
However, the dependence caused by the cross-sectional regressions at preceding steps limits the use of the proposition 1, since this does not hold due to the estimated coefficients. The discounted cash flows arising from the LSM stopping rule when the value of conditional expectation approximation is equal or less than payoffs from immediate exercise are dependent across paths when the coefficients are estimated and common across paths(Stenfort,2004).
4.2 Implementation issues
When it comes to actually implementing the method, at least three questions may emerge.
First of all, it is necessary to check the results of applying more numbers of regressors and paths than that is suggested in original paper. As mentioned above, in order to approximate the conditional expectation arbitrarily well, both the number of K and the number of M should tend to infinity, and we conjecture it to be the same requirement for convergence of the price estimate. But this is not certain from Longstaff and Schwartz(2001)'s statement that 'the LSM algorithm converges to any desired degree of accuracy'(p.125). This is questionable because the choice of M largely depends on the degree of accuracy,.
Secondly, the choice of Laguerre polynomials that is dimensions of x is somewhat subjective and arbitrary, so alternative specifications of the cross-sectional regression model need to be checked. In particularly, some choices of basis functions are highly correlated with each other, leading to the problem of estimation for regression coefficients due to the multicolinearity problem. Some general cases, such as using the LSM method to price options in models with interest rates, stochastic volatility and dividends or options with path-dependent payoff function have not been considered in the proposition 2, which can only be applied in the simple Black-Scholes model. Another important limitation that caused problems in this work was the transformation between the x and y state variables to the real world financial variables of short interest rate and the volatility thereof. The model that was implemented here could only handle positive x and y which lead to a limited range of results in the financial variables. Black model was used for determination of the boundary conditions on the transformed area, which is a simplified approach. In this paper these problems are not thoroughly investigated, merely pointed out.
The third problem is that the interest rates of derivatives are normally rather volatile and complex in real life, thus requiring a full set of discount rates to be applied in the LSM model.
Last but not least, from a practitioner's point of view, when considering the number of basis functions and paths, the optimal choice of trade-off between efficiency measured by computational time and precision should be made due to the limited computational time. Because too many M involved in calculation may substantially decrease the computational speed while subtly improve the precision. However, considering the limiting computationally time, only a subset of the options using LSM will be considered. We will focus on the options within 10 days to expiration, and set the number of exercisable time to ten in the following example, though this number apparently should be increased to approximate the value of American option.
Chapter 5: Simulation of LSM by using matlab
Next, we use the computer software Matlab to simulate the result of pricing for American put option, for which it is assumed that the initial price of the underlying asset is S0=100, exercise price of option is E=130, riskless interest rate is r=0.03, the expiration date is T=10, volatility rate sigma=0.2, the number of interval for discrete time is N=10 and the number of sample path is M=8. The results of simulation are as follows.
Table 5 simulated sample paths
N1
2
3
4
5
6
7
8
9
10
M1
134.16
143.65
150.94
209.44
180.11
209.11
249.61
240.12
253.23
202.58
2
80.28
82.81
96.64
163.64
144.71
151.74
150.76
103.45
95.71
67.52
3
119.49
101.05
104.13
94.33
101.24
90.68
101.03
118.30
168.28
163.50
4
65.86
56.24
74.48
60.71
74.31
76.94
103.59
70.68
68.63
54.44
5
180.69
215.25
286.46
234.15
215.35
205.98
259.16
247.61
287.77
192.83
6
94.10
80.61
59.40
66.41
70.97
72.17
55.83
70.65
76.54
72.82
7
101.47
97.26
69.22
66.03
56.48
46.90
37.59
34.13
23.09
28.29
8
112.08
112.75
113.09
97.38
120.58
118.59
103.83
137.42
137.70
119.14
Table 6 simulated results
Sample paths j
Optimal exercising time
Expected payoffs
Discounting factor
Discounted value
1
10
0
0.6065
0.0000
2
10
62.4844
0.6065
46.2896
3
4
35.6745
0.8869
31.6404
4
10
75.5588
0.6065
55.9753
5
10
0
0.6065
0.0000
6
7
74.1749
0.8106
60.1250
7
9
106.9067
0.7634
81.6104
8
4
32.6230
0.8869
28.9340
Expected payoffs over all paths
304.5734
Averaging result of simulated values
38.0718
The effectiveness of LSM includes the efficiency and convergence of algorithm, both of which would depend on the number of intervals of discrete time N, the number of sample path M and the approach to simulate the results. The algorithm characterizes its excellent efficiency of calculation, particularly in generating values for multiple underlying assets of American option. In the implementation of the algorithm, by using function 'randn' automatically generated by matlab, we guarantee the geometrical distribution and independence of these random numbers.
To illustrate the accuracy of LSM techniques, table 7 compares the values indicated by finite difference and LSM approaches. These two methods are both estimated on the basis of M=100000, N=50 and other conditions.
S
FD
European
LSM
22
18.000
16.141
17.955
24
16.001
14.442
15.967
26
14.057
12.852
14.077
28
12.329
11.379
12.326
30
10.775
10.029
10.765
32
9.391
8.803
9.383
34
8.162
7.699
8.149
36
7.076
6.711
7.089
38
6.122
5.834
6.123
40
5.286
5.060
5.342
42
4.558
4.379
4.574
44
3.924
3.783
3.953
46
3.375
3.263
3.415
48
2.901
2.812
2.922
50
2.491
2.420
2.528
52
2.139
2.081
2.167
54
1.836
1.789
1.859
56
1.576
1.537
1.595
58
1.352
1.320
1.344
60
1.161
1.134
1.171
Table 7: S is the initial price of option. In the comparison, the strike price is 40 and he interest rate is 0.06, is 0.4. Furthermore, the American option can be exercised at 50 points for one year and simulation is achieved on 100,000 paths. The European put option value is obtained by Black-Scholes formula with the same conditions of stock volatility, expiration date, interest rate, number of paths and dividends.
Table 8
As shown, these two models are in fairly good agreement, meaning the differences of value indicated by both techniques are sufficiently small. The Monte-Carlo method seems to provide values less than 5% larger or smaller than those predicted by finite difference. The results of some other tests, which were made with the same conditions as above except for initial share price, were similar to the results shown on the graph. The LSM proves to be very reliable in pricing American option when finite difference method is regarded as the benchmark. However, LSM appears to be more efficient than finite difference since it took less computational time for me to generate the results by using matlab.
Chapter 6. Conclusion
In trading options, we always confront with the problems of valuing American option with flexible expiration time. Since traditional binomial tress and finite difference techniques are not capable of dealing with very complex multiple underlying assets and the problem of path-dependence, the Monte-Carlo LSM technique is of theoretical and realistic significance to compute the pricing of American option. The article introduced the procedures for implementation of LSM to price American option and gave sample results of the algorithm as well as of the comparison between finite difference and least square, thus providing a concrete and applicable solution to valuation of American option. Since the principal purpose of my paper is to present the procedure of implementation of simulation method and to explain more clearly, only the simple situation of single underlying asset is considered, while it is more complicated to simulate the situation, where it involves multiple underlying assets and path-dependent American option. And it will be the direction of future research.
Appendix:
Matlab code for implementation of LSM:
function [Price,CF,S,t] = AmericanOptLSM(S0,K,r,T,sigma,N,M,type)
%AmericanOptLSM - Price an american option via Longstaff-Schwartz Method
%
% Returns the price of an American option computed using finite
% difference method applied to the BlackScoles PDE.
%
% Inputs:
%
% S0 Initial asset price
% K Strike Price
% r Interest rate
% T Time to maturity of option
% sigma Volatility of underlying asset
% N Number of points in time grid to use (minimum is 3, default is 50)
% M Number of points in asset price grid to use (minimum is 3, default is 50)
% type True (default) for a put, false for a call
S0=100;
K=130;
r=0.03;
T=10;
sigma=0.2 ;
M=8 ;
N=10;
type=true;
if nargin < 6 || isempty(N), N = 50; elseif N < 3, error('N has to be at least 3'); end
if nargin < 7 || isempty(M), M = 50; elseif M < 3, error('M has to be at least 3'); end
if nargin < 8, type = true; end
dt = T/N;
t = 0:dt:T;
t = repmat(t',1,M);
R = exp((r-sigma^2/2)*dt+sigma*sqrt(dt)*randn(N,M));
S = cumprod([S0*ones(1,M); R]);
ExTime = (M+1)*ones(N,1);
% Now for the algorithm
CF = zeros(size(S)); % Cash flow matrix
CF(end,:) = max(K-S(end,:),0); % Option only pays off if it is in the money
for ii = size(S)-1:-1:2
if type
Idx = find(S(ii,:) < K); % Find paths that are in the money at time ii
else
Idx = find(S(ii,:) > K); % Find paths that are in the money at time ii
end
X = S(ii,Idx)'; X1 = X/S0;
Y = CF(ii+1,Idx)'*exp(-r*dt); % Discounted cashflow
R = [ ones(size(X1)) (1-X1) 1/2*(2-4*X1-X1.^2)];
a = R\Y; % Linear regression step
C = R*a; % Cash flows as predicted by the model
if type
Jdx = max(K-X,0) > C; % Immediate exercise better than predicted cashflow
else
Jdx = max(X-K,0) > C; % Immediate exercise better than predicted cashflow
end
nIdx = setdiff((1:M),Idx(Jdx));
CF(ii,Idx(Jdx)) = max(K-X(Jdx),0);
ExTime(Idx(Jdx)) = ii;
CF(ii,nIdx) = exp(-r*dt)*CF(ii+1,nIdx);
end
Price = mean(CF(2,:))*exp(-r*dt);
end
>> S0=100;
K=130;
r=0.03;
T=10;
sigma=0.2 ;
M=8 ;
N=10;
type=true;
>> [Price,CF,S,t] = AmericanOptLSM(S0,K,r,T,sigma,N,M,type)
Price =
42.2091
CF =
0 0 0 0 0 0 0 0
73.0769 5.8540 75.6275 12.4812 32.2472 44.2858 38.0505 66.3334
75.3024 6.0323 77.9307 12.8613 33.2293 45.6345 39.2093 68.3535
77.5957 6.2160 80.3040 8.2317 34.2412 47.0243 40.4035 70.4352
79.9588 6.4053 82.7497 1.2156 35.2840 48.4564 41.6339 72.5803
82.3939 0 85.2698 0 33.0420 38.5357 42.9019 74.7907
84.9032 0 87.8666 0 34.0483 39.7093 44.2084 77.0684
87.4889 0 90.5426 0 35.0852 0 45.5548 79.4155
90.1856 0 93.3000 0 36.1537 0 46.9421 81.8340
89.6677 0 90.7874 0 37.2547 0 48.3717 78.8010
95.9436 0 71.4486 0 38.3893 0 49.8449 59.7873
S =
100.0000 100.0000 100.0000 100.0000 100.0000 100.0000 100.0000 100.0000
77.6139 108.3772 90.4298 105.1363 94.6057 113.6696 79.9368 87.5369
74.1646 106.3561 67.7661 117.1387 110.8457 99.8091 104.2082 98.2902
64.9325 101.9682 74.5809 121.7683 91.5604 96.0647 87.1888 99.9862
62.7709 123.5947 65.4647 128.7844 94.7160 81.5436 63.9554 72.4179
60.6048 197.9955 71.5399 208.7703 99.5809 85.4096 121.6851 66.2977
52.9158 236.9320 61.2000 180.3647 137.7914 90.2907 130.9964 64.9840
42.5111 272.1385 48.1087 176.4792 155.0064 129.2798 115.8832 66.7135
39.8144 275.1332 36.7000 155.7826 157.6029 187.8330 117.2335 48.1660
40.3323 285.2062 39.2126 181.5027 121.7208 234.5996 120.0574 51.1990
34.0564 323.5968 58.5514 192.9264 91.6107 294.3228 80.1551 70.2127
t =
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9
10 10 10 10 10 10 10 10
Matlab code for finite difference:
function [P_FD,P,s,t] = AmericanOptFD(S0,K,r,T,sigma,N,M,type)
%AmericanOptFD - Price an american option via finite differences
%
% Returns the price of an American option computed using finite
% difference method applied to the BlackScoles PDE.
%
% Inputs:
%
% S0 Initial asset price
% K Strike Price
% r Interest rate
% T Time to maturity of option
% sigma Volatility of underlying asset
% N Number of points in time grid to use (minimum is 3, default is 50)
% M Number of points in asset price grid to use (minimum is 3, default is 50)
% type True (default) for a put, false for a call
S0=36 ;
K=40;
r=0.06;
T=1;
sigma=0.4 ;
M= 100000 ;
N= 50 ;
type=true;
if nargin < 6 || isempty(N), N = 50; elseif N < 3, error('N has to be at least 3'); end
if nargin < 7 || isempty(M), M = 50; elseif M < 3, error('M has to be at least 3'); end
if nargin < 8, type = true; end
% create time grid
t = linspace(0,T,N+1);
dt = T/N; % Time step
% Share price grid
Smax = 2*max(S0,K)*exp(r*T); % Maximum price considered
dS = Smax/(M);
s = 0:dS:Smax;
% Now find points either side of the initial price so that we can calculate
% the price of the option via interploation
idx = find(s < S0); idx = idx(end); a = S0-s(idx); b = s(idx+1)-S0;
Z = 1/(a+b)*[a b]; % Interpolation vector
% Set up a pricing matrix to hold the values we compute
P = NaN*ones(N+1,M+1); % Pricing Matrix (t,S)
% Boundary condition
if type
P(end,:) = max(K-(0:M)*dS,0); % Value of option at maturity - Put
else
P(end,:) = max((0:M)*dS-K,0); % Value of option at maturity - Call
end
P(:,1) = K; % Value of option when stock price is 0)
P(:,end) = 0; % Value of option when S = Smax
% Create matrix for finite difference calculations
J = (1:M-1)';
a = r/2*J*dt-1/2*sigma^2*J.^2*dt;
b = 1+sigma^2*J.^2*dt+r*dt;
c = -r/2*J*dt-1/2*sigma^2*J.^2*dt;
D = spdiags([[a(2:end);0] b [0;c(1:end-1)]],[-1 0 1],M-1,M-1);
% Finite difference solver
for ii = N:-1:1
y = P(ii+1,2:end-1)'+[-a(1)*K; zeros(M-3,1); -c(end)*0];
x = D\y; % Value of the option
if type
P(ii,2:end-1) = max(x,K-s(2:end-1)'); % Put
else
P(ii,2:end-1) = max(x,s(2:end-1)'-K); % Call
end
end
% Extract the final price
P_FD = Z*P(1,idx:idx+1)';
End
Matlab code for Black-Scholes formula:
[call, put]=blsprice(36,40,0,06,1,0.4)
