Koksma–Hlawka inequality

Remarks

For $s = 1$ this is Koksma's inequality, and $V(f)$ is the ordinary total variation of $f$ on $[0,1]$. In that case the proof writes the error as a Riemann–Stieltjes integral $\int_0^1 \big(A(t)/N - t\big) \, df(t)$ by integration by parts, and bounds the integrand by $D_N^*$. In higher dimension the same idea works with a multivariate integration by parts, which produces one term for each face of the cube. The Hardy–Krause variation collects the variations of $f$ on all these faces. The bound separates the two sources of error: $V(f)$ depends only on the integrand, and $D_N^*$ depends only on the points. For a low-discrepancy sequence such as the Halton sequence, $D_N^* = O\big((\log N)^s / N\big)$, so the quasi-Monte Carlo error is $O\big((\log N)^s / N\big)$ for every $f$ of finite variation. This beats the rate $N^{-1/2}$ of plain Monte Carlo integration for large $N$. The hypothesis of finite variation is needed: the indicator of a ball in $[0,1]^2$ has infinite Hardy–Krause variation, and the bound gives nothing for it.

Going deeper

For a student

The inequality is the basic error bound of quasi-Monte Carlo integration. It turns the design of good integration rules into the purely geometric task of finding point sets with small star discrepancy. Halton, Sobol and other digital sequences reach $D_N^* = O\big((\log N)^s / N\big)$. The bound is sharp in a worst-case sense. But $V(f)$ is often hard to compute, and it is infinite for simple functions with jumps along surfaces not aligned with the axes. Variants replace $D_N^*$ and $V(f)$ by other pairs of dual quantities, for example $L^2$ discrepancy and a Sobolev-type norm.