In numerical analysis, the quasiMonte Carlo method is a method for numerical integration and solving some other problems using lowdiscrepancy sequences (also called quasirandom sequences or subrandom sequences). 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 quasiMonte 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}:
Since we are integrating over the sdimensional unit cube, each x_{i} is a vector of s elements. The difference between quasiMonte Carlo and Monte Carlo is the way the x_{i} are chosen. QuasiMonte Carlo uses a lowdiscrepancy sequence such as the Halton sequence, the Sobol sequence, or the Faure sequence, whereas Monte Carlo uses a pseudorandom sequence. The advantage of using lowdiscrepancy sequences is a faster rate of convergence. QuasiMonte Carlo has a rate of convergence close to O(1/N), whereas the rate for the Monte Carlo method is O(N^{−0.5}).^{[1]}
The QuasiMonte Carlo method recently became popular in the area of mathematical finance or computational finance.^{[1]} In these areas, highdimensional numerical integrals, where the integral should be evaluated within a threshold ε, occur frequently. Hence, the Monte Carlo method and the quasiMonte Carlo method are beneficial in these situations.
YouTube Encyclopedic

1/3Views:305 15644 473554

✪ 6. Monte Carlo Simulation

✪ Monte Carlo integration

✪ Mini Courses  SVAN 2016  MC1  Class 01  Scenario Generation And Sampling Methods
Transcription
Contents
Approximation error bounds of quasiMonte Carlo
The approximation error of the quasiMonte Carlo method is bounded by a term proportional to the discrepancy of the set x_{1}, ..., x_{N}. 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). D_{N} is the socalled star discrepancy of the set (x_{1},...,x_{N}) and is defined as
where Q is a rectangular solid in [0,1]^{s} with sides parallel to the coordinate axes.^{[2]} The inequality can be used to show that the error of the approximation by the quasiMonte Carlo method is , whereas the Monte Carlo method has a probabilistic error of . Though we can only state the upper bound of the approximation error, the convergence rate of quasiMonte Carlo method in practice is usually much faster than its theoretical bound.^{[1]} Hence, in general, the accuracy of the quasiMonte Carlo method increases faster than that of the Monte Carlo method. However, this advantage is only guaranteed if N is large enough and if the variation is finite.
Monte Carlo and quasiMonte Carlo for multidimensional integrations
For onedimensional 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 onedimensional integrals over multiple dimensions. However, the number of function evaluations grows exponentially as 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.^{[2]} Monte Carlo and quasiMonte Carlo methods are accurate and relatively fast when the dimension is high, up to 300 or higher.^{[3]}
Morokoff and Caflisch ^{[2]} studied the performance of Monte Carlo and quasiMonte Carlo methods for integration. In the paper, Halton, Sobol, and Faure sequences for quasiMonte 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 ^{[2]} gave examples where the advantage of the quasiMonte Carlo is less than expected theoretically. Still, in the examples studied by Morokoff and Caflisch, the quasiMonte 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 quasiMonte Carlo method is greater if the integrand is smooth, and the number of dimensions s of the integral is small.
Drawbacks of quasiMonte Carlo
Lemieux mentioned the drawbacks of quasiMonte Carlo:^{[4]}
 In order for to be smaller than , needs to be small and needs to be large (e.g. ). For large s and practical N values, the discrepancy of a point set from a lowdiscrepancy generator might be not smaller than for a random set.
 For many functions arising in practice, (e.g. if Gaussian variables are used).
 We only know an upper bound on the error (i.e., ε ≤ V(f) D_{N}) and it is difficult to compute and .
In order to overcome some of these difficulties, we can use a randomized quasiMonte Carlo method.
Randomization of quasiMonte Carlo
Since the low discrepancy sequence are not random, but deterministic, quasiMonte 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_{N}) 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 quasiMonte Carlo method and can be also viewed as a variance reduction technique for the standard Monte Carlo method.^{[5]} Among several methods, the simplest transformation procedure is through random shifting. Let {x_{1},...,x_{N}} be the point set from the low discrepancy sequence. We sample sdimensional random vector U and mix it with {x_{1}, ..., x_{N}}. In detail, for each x_{j}, create
and use the sequence instead of . If we have R replications for Monte Carlo, sample sdimensional random vector U for each replication. Randomization allows to give an estimate of the variance while still using quasirandom sequences. Compared to pure quasi MonteCarlo, 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 MonteCarlo, the variance and the computation speed are slightly better from the experimental results in Tuffin (2008) ^{[6]}
See also
 Monte Carlo method
 Monte Carlo methods in finance
 QuasiMonte Carlo methods in finance
 Biology Monte Carlo method
 Computational physics
 Lowdiscrepancy sequences
 Discrepancy theory
 Markov chain Monte Carlo
References
 ^ ^{a} ^{b} ^{c} Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} William J. Morokoff and Russel E. Caflisch, QuasiMonte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218–230. (At CiteSeer: [1])
 ^ Rudolf Schürer, A comparison between (quasi)Monte Carlo and cubature rule based methods for solving highdimensional integration problems, Mathematics and Computers in Simulation, Volume 62, Issues 3–6, 3 March 2003, 509–517
 ^ Christiane Lemieux, Monte Carlo and QuasiMonte Carlo Sampling, Springer, 2009, ISBN 9781441926760
 ^ Moshe Dror, Pierre L’Ecuyer and Ferenc Szidarovszky, Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, Springer 2002, pp. 419474
 ^ Bruno Tuffin, Randomization of QuasiMonte Carlo Methods for Error Estimation: Survey and Normal Approximation, Monte Carlo Methods and Applications mcma. Volume 10, Issue 34, Pages 617–628, ISSN (Online) 15693961, ISSN (Print) 09299629, DOI: 10.1515/mcma.2004.10.34.617, May 2008
 R. E. Caflisch, Monte Carlo and quasiMonte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1–49.
 Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and QuasiMonte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 9780521191593
 Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasiMonte Carlo Integration and Applications, Compact Textbooks in Mathematics, Birkhäuser, 2014, ISBN 9783319034249
 Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, ISBN 3540626069
 William J. Morokoff and Russel E. Caflisch, Quasirandom sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251–1279 (At CiteSeer:[2])
 Harald Niederreiter. Random Number Generation and QuasiMonte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0898712955
 Harald G. Niederreiter, QuasiMonte Carlo methods and pseudorandom numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041
 Oto Strauch and Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3631540132
External links
 The MCQMC Wiki page contains a lot of free online material on Monte Carlo and quasiMonte Carlo methods
 A very intuitive and comprehensive introduction to QuasiMonte Carlo methods