Quasi-Monte Carlo Methods in Finance - Monte Carlo and Quasi-Monte Carlo Methods

Monte Carlo and Quasi-Monte Carlo Methods

Integrals in hundreds or thousands of variables are common in computational finance. These have to be approximated numerically to within an error threshold . It is well known that if a worst case guarantee of error at most is required then the computational complexity of integration may be exponential in, the dimension of the integrand; See Ch. 3 for details. To break this curse of dimensionality one can use the Monte Carlo (MC) method defined by

where the evaluation points are randomly chosen. It is well known that the expected error of Monte Carlo is of order . Thus the cost of the algorithm that has error is of order breaking the curse of dimensionality.

Of course in computational practice pseudo-random points are used. Figure 1 shows the distribution of 500 pseudo-random points on the unit square.

Note there are regions where there are no points and other regions where there are clusters of points. It would be desirable to sample the integrand at uniformly distributed points. A rectangular grid would be uniform but even if there were only 2 grid points in each Cartesian direction there would be points. So the desideratum should be as few points as possible chosen as uniform as possible.

It turns out there is a well-developed part of number theory which deals exactly with this desideratum. Discrepancy is a measure of deviation from uniformity so what one wants are low discrepancy sequences (LDS). Numerous LDS have been created named after their inventors, e.g.

• Halton
• Hammersley
• Sobol
• Faure
• Niederreiter

Figure 2. gives the distribution of 500 LDS points.

The quasi-Monte Carlo (QMC) method is defined by

where the belong to an LDS. The standard terminology quasi-Monte Carlo is somewhat unfortunate since MC is a randomized method whereas QMC is purely deterministic.

The uniform distribution of LDS is desirable. But the worst case error of QMC is of order

where is the number of sample points. See for the theory of LDS and references to the literature. The rate of convergence of LDS may be contrasted with the expected rate of convergence of MC which is . For small the rate of convergence of QMC is faster than MC but for large the factor is devastating. For example, if, then even with the QMC error is proportional to . Thus it was widely believed by the world's leading experts that QMC should not be used for high dimensional integration. For example, in 1992 Bratley, Fox and Niederreiter performed extensive testing on certain mathematical problems. They conclude "in high-dimensional problems (say ), QMC seems to offer no practical advantage over MC". In 1993, Rensburg and Torrie compared QMC with MC for the numerical estimation of high dimensional integrals which occur in computing virial coefficients for the hard-sphere fluid. They conclude QMC is more effective than MC only if . As we shall see, tests on 360-dimensional integrals arising from a collateralized mortgage obligation (CMO) lead to very different conclusions.

Woźniakowski's 1991 paper showing the connection between average case complexity of integration and QMC led to new interest in QMC. Woźniakowski's result received considerable coverage in the scientific press . In early 1992, I. T. Vanderhoof, New York University, became aware of Woźniakowski's result and gave Woźniakowski's colleague J. F. Traub, Columbia University, a CMO with parameters set by Goldman Sachs. This CMO had 10 tranches each requiring the computation of a 360 dimensional integral. Traub asked a Ph.D. student, Spassimir Paskov, to compare QMC with MC for the CMO. In 1992 Paskov built a software system called FinDer and ran extensive tests. To the Columbia's research group's surprise and initial disbelief Paskov reported that QMC was always superior to MC in a number of ways. Details are given below. Preliminary results were presented by Paskov and Traub to a number of Wall Street firms in Fall 1993 and Spring 1994. The firms were initially skeptical of the claim that QMC was superior to MC for pricing financial derivatives. A January 1994 article in Scientific American by Traub and Woźniakowski discussed the theoretical issues and reported that "Preliminary results obtained by testing certain finance problems suggests the superiority of the deterministic methods in practice". In Fall 1994 Paskov wrote a Columbia University Computer Science Report which appeared in slightly modified form in 1997.

In Fall 1995 Paskov and Traub published a paper in the "Journal of Portfolio Management". They compared MC and two QMC methods. The two deterministic methods used Sobol and Halton points. Since better LDS were created later, no comparison will be made between Sobol and Halton sequences. The experiments drew the following conclusions regarding the performance of MC and QMC on the 10 tranche CMO:

• QMC methods converge significantly faster than MC
• MC is sensitive to the initial seed
• The convergence of QMC is smoother than the convergence of MC. This makes automatic termination easier for QMC.

To summarize, QMC beats MC for the CMO on accuracy, confidence level, and speed.

This paper was followed by reports on tests by a number of researchers which also led to the conclusion the QMC is superior to MC for a variety of high-dimensional finance problems. This includes papers by Caflisch and Morokoff (1996), Joy, Boyle, Tan (1996), Ninomiya and Tezuka (1996), Papageorgiou and Traub (1996), Ackworth, Broadie and Glasserman (1997)

Further testing of the CMO was carried out by Anargyros Papageorgiou, who developed an improved version of the FinDer software system. The new results include the following:

• Small number of sample points: For the hardest CMO tranche QMC using the generalized Faure LDS due to S. Tezuka achieves accuracy with just 170 points. MC requires 2700 points for the same accuracy. The significance of this is that due to future interest rates and prepayment rates being unknown, financial firms are content with accuracy of .
• Large number of sample points: The advantage of QMC over MC is further amplified as the sample size and accuracy demands grow. In particular, QMC is 20 to 50 times faster that MC with moderate sample sizes, and can be up to 1000 times faster than MC when high accuracy is desired QMC.