Quasi-Monte Carlo method

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".

:

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 subsequenceof 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".

Application areas

* Monte Carlo methods in finance

See also

* Monte Carlo method

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: [http://citeseer.ist.psu.edu/morokoff94quasirandom.html] )"
* William J. Morokoff and Russel E. Caflisch, "Quasi-Monte Carlo integration", J. Comput. Phys. 122 (1995), no. 2, 218--230. "(At CiteSeer: [http://citeseer.ist.psu.edu/morokoff95quasimonte.html] )"
* Oto Strauch and Štefan Porubský, "Distribution of Sequences: A Sampler", Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2
* R. E. Caflisch, "Monte Carlo and quasi-Monte Carlo methods", Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.

External links

* [http://www.puc-rio.br/marco.ind/quasi_mc.html A very intuitive and comprehensive introduction to Quasi-Monte Carlo methods]