This page has summaries of papers that cover numerical methods applied to finance
Authors: Boyle, Broadie, and Glasserman
Published: Journal of Economic Dynamics and Control (1997)
Keywords: Monte Carlo, Optimal stopping policy, American Options, control variates, variance reduction, low discrepency sequences, Sobol sequences
Summary: This is a survey of monte carlo methods for estimating derivative prices and hedge parameters efficiently, including some stuff on American options. Since I am not deeply interested in numerical methods, I thought this was a great paper since it provides a conceptual overview without an overwhelming amount of details (there are over 70 references if a reader needs details)
For pricing derivative decurities, we can reduce this to learning a function f(x) over some probability distribution on a hypercude (e.g. a single 250-day price path is a 250-dimensional point).
Variance Reduction: We want an estimator of the expected discounted payoff to an option (f(x)) with low variance. Since the standard estimator is the mean with standard error sigma / sqrt(N) we get N^(-0.5) convergence. The best estimator has minimum variance for the amount of computation required, not just the lowest sigma. One variance reduction technique is antithetic variates: e.g. for each sample path X_i from a symmetric distribution, use 0.5*( f(X_i) + f(-X_i) ) as the i'th sample: useful if f(X) monotone but usefulness decreases with large N. The control variance method uses a derivative with a known closed-form solution which is similar to the one we are trying to price. For example, if we are trying to price derivative F and we know the price of G in closed form, compute estimators F~ and G~ from N sample paths and then a good estimate of F, F*, is F* = F~ - (G~ - G). Can use this to price Asian options using Geometric Asian options as control. Moment matching adjusts sample paths to match moments of true distribution (e.g. we know variance and mean of terminal stock price). Stratified samples (and Latin hypercube sampling in higher dimensions) sample equally from each quantile of a distribution. Numerical examples for pricing Asian options indicate variance reductions of 5% to 80% for all the methods except control variate, which gives up to factor of 100 variance reduction! (because a good control exists). Antithetic variates is generally the least effective method. Also, in pricing a down-and-out call, where a good control isn't available, the control variates methods loses its huge advantage. Some special case variance reduction methods include importance sampling, which draws samples from a different distribution than the true one but reweights them based on the relative probability weight in the true and shifted distribution. This is very useful pricing deep out-of-the-money options where we want to sample paths from a distribution with a reasonable probability of non-zero payoff. Also, conditional monte carlo uses VAR( E(X | Y) ) <= VAR(X): for example, for a down-and-in call, simulate paths but any time the barrier is crossed return the Black Scholes price at that time. Next he points out that Monte-Carlo has error O(N^-0.5), numerical integration via the trapezoidal method is O(N^ [-2/D]) D = # dimensions. He mentions (giving no details) low discrepancy sequences, that spread points evenly, in some manner, about a hypercube, and integrating over these sequences can give better results, though the theoretical bounds are loose. His numerical results indicate that integrating over a Sobol sequence (for pricing an option on the max of two assets) gives much lower error.
Computing Hedge Parameters. He focuses on delta = dc/dS (c = call price, S = underlying price). With D=delta, e=epsilon, he notes that D~ = (1/e)[ c(S_0+e) - c(S_0) ] has VAR(D~) = O( 1/e^2), so e must go to zero slowly as N increases (for example, e~= N^(-1/4) is good but low convergence rate). Using common random numbers to simulate the initial and perturbed option price helps a little with continuous payoffs. But these derivative estimates based on finite differences remain biased, and require resimulation for each perturbed parameter. Some direct methods estimate the derivative price without recomputing paths. For example, for a call option: dc/dS_0 = (dc / dS_T ) * ( dS_T / dS_0 ), where S_T = S_0*exp( [r-0.5s^2]T + s*sqrt(T)*Z), and c(S_T) = exp(-rT)*MAX(S_t - K,0), and derivativs are computed from these equations easily. This is unbiased if derivative and expectation are interchangeable (see Shreve's book for when this is true). Asset or nothing options have a discontinuous payoff, so these methods don't work.
Lastly the paper covers some algorithms to approximate optimal stopping policies for American calls. Tiley's bundling algorithm partitions price space into bundles, and estimates the option value at some (price,time) bundle as the greater of the exercise value and the value of continuing, which is the average of the value at the next time step of the paths leaving that (price,time) bundle: this is solved backwards in time via dynamic programming. The paper also covers a more complicated version developed by Broadie and Glasserman, which is less biased.