Chapter 2: FAQs 227
whereD∗N(x 1 ,...,(x)N) is the discrepancy of the se-
quence. (This discrepancy measures the deviation from
a uniform distribution. It is calculated by looking at
how many of the sampling points can be found in sub
intervals compared with how many there would be for
a uniform distribution and then taking the worst case.)
Rather than the details, the important point concerning
this result is that the bound is a product of one term
specific to the function (its variation, which is indepen-
dent of the set of sampling points) and a term specific
to the set of sampling points (and independent of the
function being sampled). So once you have found a set
of points that is good, of low discrepancy, then it will
work for all integrands of bounded variation.
The popular low-discrepancy sequences mentioned
above have
D∗N<C(lnN)n
NwhereCis a constant. Therefore convergence of this
quasi Monte Carlonumerical quadrature method is
faster than genuinely random Monte Carlo.
Another advantage of these low-discrepancy sequences
is that if you collapse the points onto a lower dimension
(for example, let all of the points in a two-dimensional
plot fall down onto the horizontal axis) they will not be
repeated, they will not fall on top of one another. This
means that if there is any particularly strong depen-
dence on one of the variables over the others then the
method will still give an accurate answer because it will
distribute points nicely over lower dimensions.
Unfortunately, achieving a good implementation of
some low-discrepancy sequences remains tricky. Some
practitioners prefer to buy off-the-shelf software for
generating quasi-random numbers.