Quasi-Monte Carlo method

Remarks

Example: $s = 1$, $f(x) = x$ and the van der Corput points $\frac12, \frac14, \frac34, \frac18$; for $N = 4$ one gets $Q_4(f) = \frac{1}{4}\left(\frac12 + \frac14 + \frac34 + \frac18\right) = \frac{13}{32}$, against the exact value $\frac12$, and for $N = 3$ one gets exactly $\frac12$. Non-example: the same average with independent uniform random points $x_i$ is plain Monte Carlo integration. It is not a quasi-Monte Carlo method, because the points are random rather than a fixed low-discrepancy sequence. Riemann integrability makes $Q_N(f) \to \int f$ for every uniformly distributed sequence; error bounds of order $(\log N)^s/N$ need more, for instance bounded variation in the sense of Hardy and Krause. Randomized quasi-Monte Carlo methods apply a random shift or scrambling to a low-discrepancy point set. Each point becomes uniform while the set keeps its low discrepancy, and this allows statistical error estimates. Rank-1 lattice rules, with $x_i = \{ i z / N \}$ for an integer vector $z$, are point sets of this kind used for periodic integrands.