<<

. 11
( 11)



and there is not strong evidence at least that when the dimension of the problem
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.

<<

. 11
( 11)