In numerical analysis, the quasi-Monte Carlo method is a method for numerical integration and solving some other problems using low-discrepancy sequences (also called quasi-random sequences or sub-random sequences) to achieve variance reduction. This is in contrast to the regular Monte Carlo method or Monte Carlo integration, which are 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<sub>1</sub>, ..., x<sub>N</sub>:
:<math> \int_{[0,1]^s} f(u)\,{\rm d}u \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i). </math>
Since we are integrating over the s-dimensional unit cube, each x<sub>i</sub> is a vector of s elements. The difference between quasi-Monte Carlo and Monte Carlo is the way the x<sub>i</sub> are chosen. Quasi-Monte Carlo uses a low-discrepancy sequence such as the Halton sequence, the Sobol sequence, or the Faure sequence, whereas Monte Carlo uses a pseudorandom sequence. The advantage of using low-discrepancy sequences is a faster rate of convergence. Quasi-Monte Carlo has a rate of convergence close to O(1/N), whereas the rate for the Monte Carlo method is O(N<sup>−0.5</sup>).
The Quasi-Monte Carlo method recently became popular in the area of mathematical finance or computational finance. Monte Carlo and quasi-Monte Carlo methods are accurate and relatively fast when the dimension is high, up to 300 or higher.
Morokoff and Caflisch
- In order for <math> O\left(\frac{(\log N)^s}{N}\right) </math> to be smaller than <math> O\left(\frac{1}{\sqrt{N\right) </math>, <math>s</math> needs to be small and <math>N</math> needs to be large (e.g. <math> N>2^s </math>). For large s, depending on the value of N, the discrepancy of a point set from a low-discrepancy generator might be not smaller than for a random set.
- For many functions arising in practice, <math> V(f) = \infty </math> (e.g. if Gaussian variables are used).
- We only know an upper bound on the error (i.e., ε ≤ V(f) D<sub>N</sub>) and it is difficult to compute <math> D_N^* </math> and <math> V(f) </math>.
In order to overcome some of these difficulties, we can use a randomized quasi-Monte Carlo method.
Randomization of quasi-Monte Carlo
Since the low discrepancy sequence are not random, but deterministic, quasi-Monte Carlo method can be seen as a deterministic algorithm or derandomized algorithm. In this case, we only have the bound (e.g., ε ≤ V(f) D<sub>N</sub>) for error, and the error is hard to estimate. In order to recover our ability to analyze and estimate the variance, we can randomize the method (see randomization for the general idea). The resulting method is called the randomized quasi-Monte Carlo method and can be also viewed as a variance reduction technique for the standard Monte Carlo method. Among several methods, the simplest transformation procedure is through random shifting. Let {x<sub>1</sub>,...,x<sub>N</sub>} be the point set from the low discrepancy sequence. We sample s-dimensional random vector U and mix it with {x<sub>1</sub>, ..., x<sub>N</sub>}. In detail, for each x<sub>j</sub>, create
: <math> y_j = x_j + U \pmod 1</math>
and use the sequence <math>(y_j)</math> instead of <math>(x_j)</math>. If we have R replications for Monte Carlo, sample s-dimensional random vector U for each replication. 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)