Editing Quasi-Monte Carlo method (section)

== Monte Carlo and quasi-Monte Carlo for multidimensional integrations ==

For one-dimensional integration, quadrature methods such as the [[trapezoidal rule]], [[Simpson's rule]], or [[Newton–Cotes formulas]] are known to be efficient if the function is smooth. These approaches can be also used for multidimensional integrations by repeating the one-dimensional integrals over multiple dimensions. However, the number of function evaluations grows exponentially as&nbsp;''s'', the number of dimensions, increases. Hence, a method that can overcome this [[curse of dimensionality]] should be used for multidimensional integrations. The standard Monte Carlo method is frequently used when the quadrature methods are difficult or expensive to implement.<ref name="morokoffNcaflisch">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])''</ref> Monte Carlo and quasi-Monte Carlo methods are accurate and relatively fast when the dimension is high, up to 300 or higher.<ref>Rudolf Schürer, ''A comparison between (quasi-)Monte Carlo and cubature rule based methods for solving high-dimensional integration problems'',  Mathematics and Computers in Simulation, Volume 62, Issues 3–6, 3 March 2003, 509–517</ref>

Morokoff and Caflisch <ref name="morokoffNcaflisch" /> studied the performance of Monte Carlo and quasi-Monte Carlo methods for integration. In the paper, Halton, Sobol, and Faure sequences for quasi-Monte Carlo are compared with the standard Monte Carlo method using pseudorandom sequences. They found that the Halton sequence performs best for dimensions up to around 6; the Sobol sequence performs best for higher dimensions; and the Faure sequence, while outperformed by the other two, still performs better than a pseudorandom sequence.

However, Morokoff and Caflisch <ref name="morokoffNcaflisch" /> gave examples where 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.