Sanjiv R. Das and Alistair Sinclair
Derivative security pricing and risk measurement relies increasingly on lattice representations of stochastic processes, which are a discrete approximation of the movement of the underlying securities. Pricing is undertaken by summation of node values on the lattice. When the lattice is large (which is the case when high accuracy is required), exhaustive enumeration of the nodes becomes prohibitively costly. Instead, Monte Carlo simulation is used to estimate the lattice value by sampling appropriately from the nodes. Most sampling methods become extremely error-prone in situations where the node values vary widely. This paper presents a Markov chain Monte Carlo scheme, adapted from Sinclair and Jerrum (Information and Computation 82 (1989)), that is able to overcome this problem, provided some partial (possibly very inaccurate) information about the lattice sum is available. This partial information is used to direct the sampling, in similar fashion to traditional importance sampling methods. The key difference is that the algorithm allows backtracking on the lattice, which acts in a “self-correcting” manner to minimize the bias in the importance sampling.