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 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
:
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''.

Contents

Application areas

See also

References

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:[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