<< стр. 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
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)СОДЕРЖАНИЕ