ABSTRACT
Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Outline of the Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Step 1: State-Space Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Step 2: Markov Chain Approximation . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.3 Step 3: Time Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.4 Step 4: Solving the Sequence of LCPs . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Stability Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.1 The Explicit Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.2 The Fully Implicit Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.3 The θ Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Boundary Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6.1 Geometric Average Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6.2 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.6.3 Experimental Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.6.5 Error Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.6.6 Timings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.6.6.1 Generator Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.6.6.2 Time Stepping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.6.7 Boundary Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.7 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Abstract: We investigate a new method for pricing high-dimensional American options. The method is of finite difference type, in that we obtain solutions on a constant grid of representative states through time. We alleviate the well-known problems associated with applying standard finite difference techniques in high-dimensional spaces by using an irregular grid, as can be generated for example by a Monte Carlo or quasi-Monte Carlo method. The use of such a grid calls for an alternative method for discretizing the convectiondiffusion operator in the pricing partial differential equation; this is done by considering the grid points as states of an approximating continuous-time Markov chain, and constructing transition intensities by appealing to local consistency conditions in the spirit of Kushner and Dupuis [22]. The actual computation of the transition intensities is done by means of linear programming, which is a time-consuming process but one that can be easily parallelized. Once the transition matrix has been constructed, prices can be computed quickly. The method is tested on geometric average options in up to ten dimensions. Accurate results are obtained, in particular when use is made of a simple bias control technique.
