Monte Carlo and quasi-Monte Carlo methods Quasi-Monte Carlo methods in finance

figure 1. 500 pseudo-random points

note there regions there no points , other regions there clusters of points. desirable sample integrand @ uniformly distributed points. rectangular grid uniform if there 2 grid points in each cartesian direction there




2

d




{\displaystyle 2^{d}}

points. desideratum should few points possible chosen uniform possible.

it turns out there well-developed part of number theory deals desideratum. discrepancy measure of deviation uniformity 1 wants low discrepancy sequences (lds). numerous lds have been created named after inventors, e.g.

halton
hammersley
sobol
faure
niederreiter

figure 2. gives distribution of 500 lds points.

figure 2. 500 low discrepancy points

the quasi-monte carlo (qmc) method defined by

φ



q
m
c




(
f
)
=


1
n



∑

i
=
1


n


f
(

x

i


)
,


{\displaystyle \varphi ^{\mathop {\rm {qmc}}}(f)={\frac {1}{n}}\sum _{i=1}^{n}f(x_{i}),}

where




x

i




{\displaystyle x_{i}}

belong lds. standard terminology quasi-monte carlo unfortunate since mc randomized method whereas qmc purely deterministic.

the uniform distribution of lds desirable. worst case error of qmc of order

(
log
⁡
n

)

d



n


,


{\displaystyle {\frac {(\log n)^{d}}{n}},}

where



n


{\displaystyle n}

number of sample points. see theory of lds , references literature. rate of convergence of lds may contrasted expected rate of convergence of mc




n

−
1

/

2




{\displaystyle n^{-1/2}}

.



d


{\displaystyle d}

small rate of convergence of qmc faster mc



d


{\displaystyle d}

large factor



(
log
⁡
n

)

d




{\displaystyle (\log n)^{d}}

devastating. example, if



d
=
360


{\displaystyle d=360}

,



log
⁡
n
=
2


{\displaystyle \log n=2}

qmc error proportional




2

360




{\displaystyle 2^{360}}

. believed world s leading experts qmc should not used high-dimensional integration. example, in 1992 bratley, fox , niederreiter performed extensive testing on mathematical problems. conclude in high-dimensional problems (say



d
>
12


{\displaystyle d>12}

), qmc seems offer no practical advantage on mc . in 1993, rensburg , torrie compared qmc mc numerical estimation of high-dimensional integrals occur in computing virial coefficients hard-sphere fluid. conclude qmc more effective mc if



d
<
10


{\displaystyle d<10}

. shall see, tests on 360-dimensional integrals arising collateralized mortgage obligation (cmo) lead different conclusions.

woźniakowski s 1991 paper showing connection between average case complexity of integration , qmc led new interest in qmc. woźniakowski s result received considerable coverage in scientific press . in 1992, i. t. vanderhoof, new york university, became aware of woźniakowski s result , gave woźniakowski s colleague j. f. traub, columbia university, cmo parameters set goldman sachs. cmo had 10 tranches each requiring computation of 360 dimensional integral. traub asked ph.d. student, spassimir paskov, compare qmc mc cmo. in 1992 paskov built software system called finder , ran extensive tests. columbia s research group s surprise , initial disbelief paskov reported qmc superior mc in number of ways. details given below. preliminary results presented paskov , traub number of wall street firms in fall 1993 , spring 1994. firms skeptical of claim qmc superior mc pricing financial derivatives. january 1994 article in scientific american traub , woźniakowski discussed theoretical issues , reported preliminary results obtained testing finance problems suggests superiority of deterministic methods in practice . in fall 1994 paskov wrote columbia university computer science report appeared in modified form in 1997.

in fall 1995 paskov , traub published paper in journal of portfolio management . compared mc , 2 qmc methods. 2 deterministic methods used sobol , halton points. since better lds created later, no comparison made between sobol , halton sequences. experiments drew following conclusions regarding performance of mc , qmc on 10 tranche cmo:

qmc methods converge faster mc
mc sensitive initial seed
the convergence of qmc smoother convergence of mc. makes automatic termination easier qmc.

to summarize, qmc beats mc cmo on accuracy, confidence level, , speed.

this paper followed reports on tests number of researchers led conclusion qmc superior mc variety of high-dimensional finance problems. includes papers caflisch , morokoff (1996), joy, boyle, tan (1996), ninomiya , tezuka (1996), papageorgiou , traub (1996), ackworth, broadie , glasserman (1997), kucherenko , co-authors

further testing of cmo carried out anargyros papageorgiou, developed improved version of finder software system. new results include following:

small number of sample points: hardest cmo tranche qmc using generalized faure lds due s. tezuka achieves accuracy




10

−
2




{\displaystyle 10^{-2}}

170 points. mc requires 2700 points same accuracy. significance of due future interest rates , prepayment rates being unknown, financial firms content accuracy of




10

−
2




{\displaystyle 10^{-2}}

.
large number of sample points: advantage of qmc on mc further amplified sample size , accuracy demands grow. in particular, qmc 20 50 times faster mc moderate sample sizes, , can 1000 times faster mc when high accuracy desired qmc.

currently highest reported dimension qmc outperforms mc 65536. software sobol sequence generator sobolseq65536 generates sobol sequences satisfying property dimensions , property adjacent dimensions.

sobolseq generators outperform other known generators both in speed , accuracy