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"1, ..., "x""N".

: int_{ar 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"1, ..., "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"1, ..., "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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Monte Carlo method — Not to be confused with Monte Carlo algorithm. Computational physics …   Wikipedia

  • Quasi-Monte Carlo methods in finance — High dimensional integrals in hundreds or thousands of variables occur commonly in finance. These integrals have to be computed numerically to within a threshold epsilon. If the integral is of dimension d then in the worst case, where one has a… …   Wikipedia

  • Monte Carlo methods for electron transport — The Monte Carlo method for electron transport is a semiclassical Monte Carlo(MC) approach of modeling semiconductor transport. Assuming the carrier motion consists of free flights interrupted by scattering mechanisms, a computer is utilized to… …   Wikipedia

  • Monte Carlo methods in finance — Monte Carlo methods are used in finance and mathematical finance to value and analyze (complex) instruments, portfolios and investments by simulating the various sources of uncertainty affecting their value, and then determining their average… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Low-discrepancy sequence — In mathematics, a low discrepancy sequence is a sequence with the property that for all values of N , its subsequence x 1, ..., x N has a low discrepancy.Roughly speaking, the discrepancy of a sequence is low if the number of points in the… …   Wikipedia

  • List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… …   Wikipedia

  • Outline of finance — The following outline is provided as an overview of and topical guide to finance: Finance – addresses the ways in which individuals, businesses and organizations raise, allocate and use monetary resources over time, taking into account the risks… …   Wikipedia

  • Joseph F Traub — Infobox Scientist name = Joseph Frederick Traub caption = birth date = Birth date|1932|06|24 birth place = death date = death place = residence = nationality = field = Computer Science work institution = Columbia University alma mater = doctoral… …   Wikipedia

  • Analyse numérique — L’analyse numérique est une discipline des mathématiques. Elle s’intéresse tant aux fondements théoriques qu’à la mise en pratique des méthodes permettant de résoudre, par des calculs purement numériques, des problèmes d’analyse mathématique.… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.