Quasi-Monte Carlo method
Encyclopedia
In numerical analysis
, a quasi-Monte Carlo method is a method for the computation of an integral
(or some other problem) that is based on low-discrepancy sequence
s. This is in contrast to a regular Monte Carlo method
, which is based on sequences of pseudorandom numbers.
Monte Carlo and quasi-Monte Carlo methods are stated in a similar way.
The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x1, ..., xN.
where Īs is the s-dimensional unit cube, Īs = [0, 1] × ... × [0, 1]. (Thus each xi is a vector of s elements.)
In a Monte Carlo method,
the set x1, ..., xN is a subsequence
of pseudorandom numbers.
In a quasi-Monte Carlo method,
the set is a subsequence of a low-discrepancy sequence.
The approximation error of a method of the above type is bounded by a term proportional to the discrepancy of the set x1, ..., xN, by the Koksma-Hlawka inequality.
The discrepancy of sequences typically used for the quasi-Monte Carlo method is bounded by a constant times
In comparison, with probability one, the expected discrepancy of a uniform random sequence (as used in the Monte Carlo method) has an order of convergence
by the law of the iterated logarithm
.
Thus it would appear that the accuracy of the quasi-Monte Carlo method increases faster than that of the Monte Carlo method. However, Morokoff and Caflisch cite examples of problems in which the advantage of the quasi-Monte Carlo is less than expected theoretically. Still, in the examples studied by Morokoff and Caflisch, the quasi-Monte Carlo method did yield a more accurate result than the Monte Carlo method with the same number of points.
Morokoff and Caflisch remark that the advantage of the quasi-Monte Carlo method is greater if the integrand is smooth, and the number of dimensions s of the integral is small. A technique, coined randomized quasi-Monte Carlo, that mixes quasi-Monte Carlo with traditional Monte Carlo, extends the benefits of quasi-Monte Carlo to medium to large s.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, a quasi-Monte Carlo method is a method for the computation of an integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
(or some other problem) that is based on low-discrepancy sequence
Low-discrepancy sequence
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a low discrepancy....
s. This is in contrast to a regular Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
, which is based on sequences of pseudorandom numbers.
Monte Carlo and quasi-Monte Carlo methods are stated in a similar way.
The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x1, ..., xN.
where Īs is the s-dimensional unit cube, Īs = [0, 1] × ... × [0, 1]. (Thus each xi is a vector of s elements.)
In a Monte Carlo method,
the set x1, ..., xN is a subsequence
of pseudorandom numbers.
In a quasi-Monte Carlo method,
the set is a subsequence of a low-discrepancy sequence.
The approximation error of a method of the above type is bounded by a term proportional to the discrepancy of the set x1, ..., xN, by the Koksma-Hlawka inequality.
The discrepancy of sequences typically used for the quasi-Monte Carlo method is bounded by a constant times
In comparison, with probability one, the expected discrepancy of a uniform random sequence (as used in the Monte Carlo method) has an order of convergence
by the law of the iterated logarithm
Law of the iterated logarithm
In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Y. Khinchin . Another statement was given by A.N...
.
Thus it would appear that the accuracy of the quasi-Monte Carlo method increases faster than that of the Monte Carlo method. However, Morokoff and Caflisch cite examples of problems in which the advantage of the quasi-Monte Carlo is less than expected theoretically. Still, in the examples studied by Morokoff and Caflisch, the quasi-Monte Carlo method did yield a more accurate result than the Monte Carlo method with the same number of points.
Morokoff and Caflisch remark that the advantage of the quasi-Monte Carlo method is greater if the integrand is smooth, and the number of dimensions s of the integral is small. A technique, coined randomized quasi-Monte Carlo, that mixes quasi-Monte Carlo with traditional Monte Carlo, extends the benefits of quasi-Monte Carlo to medium to large s.