# The Valuation Of American Option Using Monte Carlo Least Square Method Accounting Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The 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. I n contrast, the European option that 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 in Black and Scholes(1973) based on the assumption that asset's price changes continuously in a way that produces lognormal distribution for the price at a future time. B ut 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. T he payoff on the maturity date may possess the path-dependent features, thus it is not feasible to us e the binomial model to evaluate the possible increase in payoff exponentially with the increase in time. B ut t he Monte Carlo simulation is quite effective and flexible in dealing with a number of underlying assets and the issue of path dependence. Y et 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 could 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.

T he problem was partly solved by Tilley(1993), who proposed a n 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 significan effect. 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) did an investigation in pricing approach of recent trends of option valuation for basis function methods, and Lai and Wong (2004) review ed these approaches with the objective of understanding the basis on which to make the choice of basis function. T he 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.

T he 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. 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 comparison of values implied by both finite difference and Monte-Carlo LSM methods. Chapter 6 is the conclusion section.

## Markov process

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.

## 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 could be denoted as: Z(T)-Z(0) and T could be divided into N intervals . According to definition, E[Z(T)-Z(0)]=0,Var[Z(T)-Z(0)]=Nâ-³t=T.

## 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 denoted L0, L1, ..., are a polynomial sequence that may be defined by the the formula:

They are orthogonal mutually with regard to the inner product given by

## 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 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 associated norm and metric

## ,

respectively, where the integrals involved are Lebesgue integrals.

## 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 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 :

## Black-Merton 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 must 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 is 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 shorting 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.

## Black-Scholes formula

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.

## 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 a put options are:

(15c)

(15p)

## Finite difference methods

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 implicite 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) can be denoted as

(20e)

(20i)

The initial conditions (15c) and (15p) can be expressed as:

(21)

## 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-nuetral 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 ot 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.

## Numerical example for LSM

In order to pricing an 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 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 could 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.

## 3.1 the 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â€¦tk=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;tk) 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;tk) 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;tk,T) could be different from C(w,s;tk+1,T) when the option is optimally exercised at tk+1, thus changing all subsequent cash flows along the sample path w. There is an assumption that the function of F(w;tk-1) 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, there 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.

## Least square method

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 tk for all paths and discount the value of cash flows back to time tk-1. Then approximate F(w,tk-1) by orthonormal basis and least square which is done by regressing C(w,s;tk-1,T) using M basis functions along the in-the-money path. To estimate coefficients aj, minimum value of following equation needs to be yield:

Once the conditional expectation value function at time tk-1 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 tk-1 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 and their 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

## 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.

## 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.

The proposition 1. For any chioice of M,K, and vecor representing the coefficients for the M basis functions at each of the K-1 early exercise dates. The following inequality holds,

Where LSM(wi;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.

The 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 functionis 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 is actually represent 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). Additionally, the fact that the convergence of the conditional expectation approximation should be achieved by making both N and M tending to infinity has been neglected. Thus, we can not say that the convergence result of LSM has been fully proved by Longstaff and Schwartz.

## 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.

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: 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.

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 result

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

## 38.0718

The effectiveness of LSM includes the efficiency and convergence of algorithm, both of which would depend on the number of interval for 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 simulation of 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.

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: S0 is the initial price of option. I n the comparison, the strike price is 40, the interest rate is 0.06, is 0.4. Furthermore, the American option could be exercised at 50 points for one year and simulation is achieved on 100,000 paths. T he European put option value is obtained by Black-Scholes formula with the same stock volatility, maturity 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 tiny. The Monte-Carlo method seems to provide values above those predicted by finite difference somewhat. 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. The LSM proves to be very reliable in pricing American option if 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 obtain the results by using matlab.

## Chapter 6. Conclusion

In the application of practical options, we always confront with the problems of valuing American option with flexible expiration time. As 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 paper 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. Since the principal purpose of my paper is to present the procedure of implementation of simulation method. 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

% 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

S0=3 6 ;

K=40;

r=0.06;

T=1;

sigma=0. 2 ;

M= 8 ;

N= 1 0;

type=true;

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

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

% create time grid

S0=3 6 ;

K=40;

r=0.06;

T=1;

sigma=0. 4 ;

M= 100000 ;

N= 50 ;

type=true;

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)