Quasi-Monte Carlo method

From Wikipedia, the free 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 sequences. 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 x₁, ..., x_N.

$\int_{\bar I^s} f(u)\,du \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i),$

where Ī^s is the s-dimensional unit cube, Ī^s = [0, 1] × ... × [0, 1]. (Thus each x_i is a vector of s elements.) In a Monte Carlo method, the set x₁, ..., x_N 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 x₁, ..., x_N, by the Koksma-Hlawka inequality. The discrepancy of sequences typically used for the quasi-Monte Carlo method is bounded by a constant times

$\frac{(\log N)^s}{N}.$

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

$\sqrt{\frac{\log \log N}{2N}}$

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.

[edit] Application areas

Monte Carlo methods in finance

[edit] See also

Monte Carlo method

[edit] References

Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, ISBN 3-540-62606-9
Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5
Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957--1041
William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251--1279 (At CiteSeer:[1])
William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [2])
Oto Strauch and Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2

Retrieved from "http://en.wikipedia.org../../../q/u/a/Quasi-Monte_Carlo_method_47aa.html"

Categories: Monte Carlo methods | Quasirandomness

Quasi-Monte Carlo method

From Wikipedia, the free encyclopedia

[edit] Application areas

[edit] See also

[edit] References

Views

Navigation

interaction

Search