High-dimensional integrals in hundreds or thousands of variables occur commonly in finance. These integrals have to be computed numerically to within a threshold ϵ {\displaystyle \epsilon } . If the integral is of dimension d {\displaystyle d} then in the worst case, where one has a guarantee of error at most ϵ {\displaystyle \epsilon } , the computational complexity is typically of order ϵ − d {\displaystyle \epsilon ^{-d}} . That is, the problem suffers the curse of dimensionality. In 1977 P. Boyle, University of Waterloo, proposed using Monte Carlo (MC) to evaluate options. Starting in early 1992, J. F. Traub, Columbia University, and a graduate student at the time, S. Paskov, used quasi-Monte Carlo (QMC) to price a Collateralized mortgage obligation with parameters specified by Goldman Sachs. Even though it was believed by the world's leading experts that QMC should not be used for high-dimensional integration, Paskov and Traub found that QMC beat MC by one to three orders of magnitude and also enjoyed other desirable attributes. Their results were first published in 1995. Today QMC is used in the financial sector to value financial derivatives; see list of books below. QMC is not a panacea for all high-dimensional integrals. A number of explanations have been proposed for why QMC is useful for financial derivatives. This continues to be a research area.
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 ϵ {\displaystyle \epsilon } . It is well known that if a worst case guarantee of error at most ϵ {\displaystyle \epsilon } is required then the computational complexity of integration may be exponential in d {\displaystyle d} , 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
φ M C ( f ) = 1 n ∑ i = 1 n f ( x i ) , {\displaystyle \varphi ^{\mathop {\rm {MC}} }(f)={\frac {1}{n}}\sum _{i=1}^{n}f(x_{i}),}
where the evaluation points x i {\displaystyle x_{i}} are randomly chosen. It is well known that the expected error of Monte Carlo is of order n − 1 / 2 {\displaystyle n^{-1/2}} . Thus, the cost of the algorithm that has error ϵ {\displaystyle \epsilon } is of order ϵ − 2 {\displaystyle \epsilon ^{-2}} 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 2 d {\displaystyle 2^{d}} 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). An example of distribution with 500 LDS points is given in Figure 2.
Numerous LDS have been created named after their inventors, for example:
Halton, Hammersley, Sobol, Faure, Niederreiter. Generally, the quasi-Monte Carlo (QMC) method is defined by
φ Q M C ( f ) = 1 n ∑ i = 1 n f ( x i ) , {\displaystyle \varphi ^{\mathop {\rm {QMC}} }(f)={\frac {1}{n}}\sum _{i=1}^{n}f(x_{i}),}
where the x i {\displaystyle x_{i}} 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
( log n ) d n , {\displaystyle {\frac {(\log n)^{d}}{n}},}
… excerpt ends here. Continue reading the full article.
