Editing Quasi-Monte Carlo method (section)

== 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.<ref>Moshe Dror, Pierre L’Ecuyer and Ferenc Szidarovszky, ''Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications'', Springer 2002, pp. 419-474</ref>  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) <ref>Bruno Tuffin, ''Randomization of Quasi-Monte Carlo Methods for Error Estimation: Survey and Normal Approximation'', Monte Carlo Methods and Applications mcma. Volume 10, Issue 3-4, Pages 617–628, ISSN (Online) 1569-3961, ISSN (Print) 0929-9629, {{doi|10.1515/mcma.2004.10.3-4.617}}, May 2008</ref>