The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x1, ..., xN: Since we are integrating over the s-dimensional unit cube, each xi is a vector of s elements.
The advantage of using low-discrepancy sequences is a faster rate of convergence.
The approximation error of the quasi-Monte Carlo method is bounded by a term proportional to the discrepancy of the set x1, ..., xN.
Specifically, the Koksma–Hlawka inequality states that the error is bounded by where V(f) is the Hardy–Krause variation of the function f (see Morokoff and Caflisch (1995) [2] for the detailed definitions).
DN is the so-called star discrepancy of the set (x1,...,xN) and is defined as where Q is a rectangular solid in [0,1]s with sides parallel to the coordinate axes.
can be used to show that the error of the approximation by the quasi-Monte Carlo method is
Hence, a method that can overcome this curse of dimensionality should be used for multidimensional integrations.
However, Morokoff and Caflisch [2] 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.
[5] Among several methods, the simplest transformation procedure is through random shifting.
Let {x1,...,xN} be the point set from the low discrepancy sequence.
We sample s-dimensional random vector U and mix it with {x1, ..., xN}.
Randomization allows to give an estimate of the variance while still using quasi-random sequences.
Compared to pure quasi Monte-Carlo, the number of samples of the quasi random sequence will be divided by R for an equivalent computational cost, which reduces the theoretical convergence rate.
Compared to standard Monte-Carlo, the variance and the computation speed are slightly better from the experimental results in Tuffin (2008) [6]