Editing Quasi-Monte Carlo method (section)

== Approximation error bounds of quasi-Monte Carlo ==
The approximation error of the quasi-Monte Carlo method is bounded by a term proportional to the discrepancy of the set ''x''<sub>1</sub>, ..., ''x''<sub>''N''</sub>. Specifically, the [[Low-discrepancy sequence#The Koksma.E2.80.93Hlawka inequality|Koksma–Hlawka inequality]] states that the error

:<math> \varepsilon = \left| \int_{[0,1]^s} f(u)\,{\rm d}u - \frac{1}{N}\,\sum_{i=1}^N f(x_i) \right| </math>
is bounded by 
:<math> |\varepsilon| \leq V(f) D_N, </math>

where ''V''(''f'') is the Hardy–Krause variation of the function ''f'' (see Morokoff and Caflisch (1995) <ref name="morokoffNcaflisch" /> for the detailed definitions). ''D''<sub>''N''</sub> is the so-called star discrepancy of the set (''x''<sub>1</sub>,...,''x''<sub>''N''</sub>) and is defined as

:<math> D_N = \sup_{Q \subset [0,1]^s} \left| \frac{\text{number of points in } Q} N - \operatorname{volume}(Q) \right|, </math>

where ''Q'' is a rectangular solid in [0,1]<sup>''s''</sup> with sides parallel to the coordinate axes.<ref name="morokoffNcaflisch" /> The inequality <math> |\varepsilon| \leq V(f) D_N </math> can be used to show that the error of the approximation by the quasi-Monte Carlo method is <math> O\left(\frac{(\log N)^s}{N}\right) </math>, whereas the Monte Carlo method has a probabilistic error of <math> O\left(\frac 1 {\sqrt N}\right) </math>. Thus, for sufficiently large <math> N </math>, quasi-Monte Carlo will always outperform random Monte Carlo. However, <math> \log(N)^s </math> grows exponentially quickly with the dimension, meaning a poorly-chosen sequence can be much worse than Monte Carlo in high dimensions. In practice, it is almost always possible to select an appropriate low-discrepancy sequence, or apply an appropriate transformation to the integrand, to ensure that quasi-Monte Carlo performs at least as well as Monte Carlo (and often much better).<ref name="asmunssen_glynn_book" />