---
tag: XAW51D9E62
kind: definition
name: Quasi-Monte Carlo method
msc: [65D30, 11K45, 65C05]
defines: ABSRB2KXA6
uses: [XSPX1KW9AQ, ADSVMCY77A, 0W29TBTY12]
sources:
  - url: https://en.wikipedia.org/wiki/Quasi-Monte_Carlo_method
---

## Definition

Let $s \ge 1$ be an integer and let $f \colon [0, 1]^s \to \R$ be a [[Riemann integrable|0W29TBTY12]] function.
A *quasi-Monte Carlo method* for $\int_{[0,1]^s} f(x)\, dx$ is an equal-weight [[quadrature rule|ADSVMCY77A]]
$$Q_N(f) = \frac{1}{N} \sum_{i=1}^{N} f(x_i),$$
with $N \ge 1$.
Here $x_1, x_2, \ldots$ are the points of a deterministic [[low-discrepancy sequence|XSPX1KW9AQ]] in $[0, 1)^s$, or the $N$ points of a deterministic point set of low discrepancy.

## 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.