is moderate (for example d · 15) it makes a great deal of di¬erence whether we

use Halton, Faure or Sobol sequences. There is evidence that the starting values

for the Sobol sequences have an e¬ect on the speed of convergence, and that

Sobol sequences can be generated more quickly than Faure Moreover neither

the Faure nor Sobol sequence provides a “black-box” method because both are

sensitive to intitialization. I will not attempt to adjudicate the considerable

literature on this topic here, but provide only a fragment of evidence that, at

least in the kind of example discussed in the variance reduction chapter, there

is little to choose between the various methods. Of course this integral, the

EXAMPLES OF LOW DISCREPANCY SEQUENCES 321

discounted payo¬ from a call option as a function of the uniform input, is a

one-dimensional integral so the Faure, Halton and Van der Corput sequences

are all the same thing in this case. In Figure 6.8 we plot the (expected) squared

error as a function of sample size for n = 1, ..., 100000 for crude Monte Carlo

( the dashed line) and the Van der Corput sequence. The latter, although it

oscillates somewhat, is substantially better at all sample sizes, and its mean

squared error is equivalent to a variance reduction of around 1000 by the time

we reach n = 100, 000. The di¬erent slope indicates an error approaching zero

at rate close to n’1 rather than the rate n’1/2 for the Crude Monte Carlo

estimator. The Sobol sequence, although highly more variable as a function

of sample size, appears to show even more rapid convergence along certain

subsequences.

Figure 6.8: (Expected) squared error vs. sample size in the estimation of an

Call option price for Crude MC and Van der Corput sequence.

322 CHAPTER 6. QUASI- MONTE CARLO MULTIPLE INTEGRATION

The Sobol and Faure sequences are particular cases of (t, s) ’ nets. In order

to de¬ne then we need the concept of an elementary interval.

Elementary Intervals and Nets

De¬nition: elementary interval

An elementary interval in base b is n interval E in I s of the form

¶

s

Y aj (aj + 1)

(6.10)

E= , ,

bdj bdj

j=1

with dj ≥ 0, 0 · aj · bdj and aj , dj are integers.

In other words an elementary interval is a multidemsional generalization of

a rectangle with sides of length bd parallel to the axes. A net is a ¬nite sequence

which is perfectly balanced in the sense that certain elementary intervals all

have exactly the same number of elements of the sequence.

De¬nition: (t, m, s) - net

Let 0 · t · m be integers. A (t.m.s) - net in base b is a ¬nite sequence with

bm points from I s such that every elementary interval in base b of volume bt’m

contains exactly bt points of the sequence.

De¬nition: (t, s) - sequence

An in¬nite sequence of points {xi } ∈ I s is a (t,s)-sequence in base b if for all

k ≥ 0 and m > t, the ¬nite sequence xkbm , . . . , x(k+1)bm’1 forms a (t,m,s) - net

in base b.

It is known that for a (t, s)-sequence in base b, we can obtain an upper bound

for the star discrepancy of the form:

(log N )s (log N )s’1

—

DN · C (6.11)

+ O( ).

N N

EXAMPLES OF LOW DISCREPANCY SEQUENCES 323

Special constructions of such sequences for s ≥ 2 have the smallest discrep-

ancy that is currently known (Niederreiter, 1992).

Tan(1998) provides a thorough investigation into various improvements in

Quasi-Monte Carlo sampling, as well as the evidence of the high e¬ciency of

these methods when valuing Rainbow Options in high dimensions. Papageor-

giou and Traub (1996) tested what Tezuka called generalized Faure points. They

concluded that these points were superior to Sobol points in a particular prob-

lem, important for ¬nancial computation snce a reasonably small error could be

achieved with few evaluations. For example, just 170 generalized Faure points

were su¬cient to achieve an error of less than one part in a hundred for a 360

dimensional problem. See also Traub and Wozniakowski (1994) and Paskov

and Traub (1995).

In summary, Quasi-Monte Carlo frequently generates estimates superior to

Monte-Carlo methods in many problems of low or intermediate e¬ective dimen-

sion. If the dimension d is large, but a small number of variables determine

most of the variability in the simulation, then we might expect Quasi Monte-

Carlo methods to continue to perform well. Naturally we pay a price for the

smaller error often associated with quasi Monte-Carlo methods and other nu-

merical techniques or, in some cases any technique which other than a crude

simulation of the process. Attempts to increase the e¬ciency for the estimation

of a particular integral work by sacri¬cing information on the distribution of

other functionals of the process of interest. If there are many objectives to a

simulation, including establishing the distribution of a large number of di¬erent

variables (some of which are necessarily not smooth), often only a crude Monte

Carlo simulation will su¬ce. In addition, the theory supporting low-discrepancy

sequences, both the measures of discrepancy themselves and the variation mea-

sure V (f ) are arti¬ciall tied to the arbitrary direction of the axes. For example

if f (x) represents the indicator function of a square with sides parallel to the

axes in dimension d = 2, then V (f ) = 0. However, if we rotate this rectangle

324 CHAPTER 6. QUASI- MONTE CARLO MULTIPLE INTEGRATION

by 45 degrees, the variation becomes in¬nite, indicating that functions with

steep isoclines at a 45 degree angle to the axes may be particularly di¬cult to

integrate using Quasi Monte Carlo.

Problems

1. Use 3-dimensional Halton sequences to integrate the function

Z Z Z

1 1 1

f (x, y, z)dxdydz

0 0 0

where f (x, y, z) = 1 if x < y < z and otherwise f (x, y, z) = 0. Compare

your answer with the true value of the integral and with crude Monte

Carlo integral of the same function.

2. Use your program from Question 1 to generate 50 points uniformly dis-

tributed in the unit cube. Evaluate the Chi-squared statistic χ2 for a

obs

test that these points are independent uniform on the cube where we di-

vide the cube into 8 subcubes, each having sides of length 1/2. Carry

out the test by ¬nding P [χ2 > χ2 ] where χ2 is a random chi-squared

obs

variate with the appropriate number of degrees of freedom. This quantity

P [χ2 > χ2 ] is usually referrred to as the “signi¬cance probability” or

obs

“p-value” for the test. If we suspected too much uniformity to be con-

sistent with assumption of independent uniform, we might use the other

tail of the test, i.e. evaluate P [χ2 < χ2 ]. Do so and comment on your

obs

results.