226 Frequently Asked Questions In Quantitative Finance
rule. This means evaluating the integrand at a number
of points, and as the number of function evaluations
increases so the accuracy of the method improves.
Unfortunately, in higher dimensions evaluating the
function at uniformly spaced points becomes compu-
tationally inefficient.
If the domain of integration is a unit hypercube (and, of
course, it can always be transformed into one) then the
value of the integral is the same as the average of the
function over that domain:
∫ 1
0
...
∫ 1
0
f(x)dx≈
1
N
∑N
i= 1
f(xi).
Where thexiare uniformly distributed. This suggests
that an alternative method of numerical evaluation of
the integral is to select the points in the hypercube
from a uniform random distribution and then compute
their average. IfNfunction evaluations are performed
then the method converges likeO(N−^1 /^2 ). This is the
Monte Carlo method of numerical integration. Although
very simple to perform it suffers from problems associ-
ated with the inevitable clustering and gapping that will
happen with randomly chosen numbers.
Clearly we would like to use a sequence of numbers that
do not suffer from the gapping/clustering problem. This
is where low-discrepancy sequences come in.
Low-discrepancy numbers exploit theKoksma-Hlawka
inequalitywhich puts a bound on the error in the
above averaging method for an arbitrary sets of sam-
pling pointsxi. The Koksma-Hlawka inequality says that
iff(x) is of bounded variationV(f)then
∣
∣
∣
∫ 1
0
...
∫ 1
0
f(x)dx−
1
N
∑N
i= 1
f(xi)
∣
∣
∣≤V(f)D∗N(x 1 ,...,(x)N)
