Multilevel Monte Carlo For L Evy Driven Sdes: Felix Heidenreich

Multilevel Monte Carlo for Lvy Driven SDEs e
Felix Heidenreich
TU Kaiserslautern AG Computational Stochastics
August 2011
joint work with Steen Dereich Philipps-Universitt Marburg a supported within DFG-SPP 1324
F. Heidenreich (TU Kaiserslautern) MLMC for Lvy Driven SDEs e August 2011 1 / 17
Outline
Introduction
The Multilevel Monte Carlo Algorithm
Approximation of the Driving Lvy Process e
Result and Examples
F. Heidenreich (TU Kaiserslautern)
MLMC for Lvy Driven SDEs e
August 2011
2 / 17
Introduction
The Problem
SDE dYt = a(Yt ) dXt , Y0 = y0 , with a square integrable Lvy process X = (Xt )t[0,1] , e a deterministic initial value y0 , a Lipschitz continuous function a. t [0, 1],
August 2011
3 / 17
Introduction
The Problem
SDE dYt = a(Yt ) dXt , Y0 = y0 , with a square integrable Lvy process X = (Xt )t[0,1] , e a deterministic initial value y0 , a Lipschitz continuous function a. Computational problem: Compute S(f ) = E[f (Y )] for functionals f : D[0, 1] R. t [0, 1],
August 2011
3 / 17
Introduction
The Problem
SDE dYt = a(Yt ) dXt , Y0 = y0 , with a square integrable Lvy process X = (Xt )t[0,1] , e a deterministic initial value y0 , a Lipschitz continuous function a. Computational problem: Compute S(f ) = E[f (Y )] for functionals f : D[0, 1] R. Example: payo f of a path dependent option.
t [0, 1],
Introduction
Standard Monte Carlo

For approximation Y of Y , 1 S(f ) = E[f (Y )] E[f (Y )] n
n
f (Yi ),
i=1 =:S MC (f )
where (Yi )i=1,...,n i.i.d. copies of Y .
August 2011
4 / 17
Introduction

n
f (Yi ),
i=1 =:S MC (f )
where (Yi )i=1,...,n i.i.d. copies of Y . Error decomposition into weak error and Monte Carlo error 1 E[|S(f ) S MC (f )|2 ] = | E[f (Y ) f (Y )] |2 + Var(f (Y )) . n
=:bias(f (Y )) =Var(S MC (f ))
August 2011
4 / 17
Introduction

n
f (Yi ),
i=1 =:S MC (f )
where (Yi )i=1,...,n i.i.d. copies of Y . Error decomposition into weak error and Monte Carlo error 1 E[|S(f ) S MC (f )|2 ] = | E[f (Y ) f (Y )] |2 + Var(f (Y )) . n
=:bias(f (Y )) =Var(S MC (f ))
Classical approach: Use approximation Y with small bias, e.g. higher-order weak It-Taylor schemes, or extrapolation techniques. o
Introduction
Path-independent functions f in the diusion case

Classical setting: Brownian motion as driving process, i.e. X = W . Compute expectations w.r.t. marginal in T > 0, i.e. S(f ) = E[f (Y (T ))] for f : R R.
August 2011
5 / 17
Introduction

Classical setting: Brownian motion as driving process, i.e. X = W . Compute expectations w.r.t. marginal in T > 0, i.e. S(f ) = E[f (Y (T ))] for f : R R. Relation of error and computational cost: Weak approximation of order yields E[|S(f ) S MC (f )|2 ]
2
with computational cost O(
1 2
).
Remedy: Only for suciently smooth f C 2(+1) .
August 2011
5 / 17
Introduction

Classical setting: Brownian motion as driving process, i.e. X = W . Compute expectations w.r.t. marginal in T > 0, i.e. S(f ) = E[f (Y (T ))] for f : R R. Relation of error and computational cost: Weak approximation of order yields E[|S(f ) S MC (f )|2 ]
2
1 2
).
Remedy: Only for suciently smooth f C 2(+1) . Note: Variance reduction via Multilevel algorithm S ML yields E[|S(f ) S ML (f )|2 ] Holds for f Lipschitz.
log( )2 ).
Multilevel Monte Carlo Algorithms

See Heinrich [1998], Giles [2006], Creutzig, Dereich, Mller-Gronbach, Ritter u [2009], Avikainen [2009], Kloeden, Neuenkirch, Pavani [2009], Hickernell, Mller-Gronbach, Niu, Ritter [2010], Marxen [2010],... u Talks by Burgos, Giles, Roj, Szpruch, Xia...
August 2011
6 / 17

Basic idea: Y (1) , Y (2) , . . . strong approximations for the solution Y with increasing accuracy and increasing numerical cost. Telescoping sum:
m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
August 2011
6 / 17

m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
Approximate E[D (1) ], . . . , E[D (m) ] by independent Monte Carlo methods

m
S(f ) =
k=1 (k)
1 nk
nk
Di ,
i=1
(k)
for (Di )i=1,...,nj being i.i.d. copies of D (k) , k = 1, . . . , m.
August 2011
6 / 17

m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
Approximate E[D (1) ], . . . , E[D (m) ] by independent Monte Carlo methods

m
S(f ) =
k=1 (k)
1 nk
nk
Di ,
i=1
(k)
for (Di )i=1,...,nj being i.i.d. copies of D (k) , k = 1, . . . , m. Note: (Y (k) , Y (k1) ) are coupled via X so that the variance of D (k) decreases.
Approximation of the driving Lvy process X e

Lvy-Ito-decomposition: X sum of three independent processes. e Xt = Wt + bt + Lt , Brownian motion W , drift b = E[X1 ] R, L2 -martingale of compensated jumps L (jump-intensity measure ). t 0.
August 2011
7 / 17

Lvy-Ito-decomposition: X sum of three independent processes. e Xt = Wt + bt + Lt , Brownian motion W , drift b = E[X1 ] R, L2 -martingale of compensated jumps L (jump-intensity measure ). Assumption: Simulations of |(h,h)c /((h, h)c ) feasible for h > 0. Thus: Cuto of the small jumps. t 0.
August 2011
7 / 17

Lvy-Ito-decomposition: X sum of three independent processes. e Xt = Wt + bt + Lt , t 0.
Assumption: Simulations of |(h,h)c /((h, h)c ) feasible for h > 0. Thus: Cuto of the small jumps. Dene Lt
(h)
=
s[0,t]
Xs 1{|Xs |h} t l
x (dx),
(h,h)c
August 2011
7 / 17

(h)
=
s[0,t]
Xs 1{|Xs |h} t l
x (dx),
(h,h)c
and approximate X by X (h,) = (Wt + bt + Lt )tT (h,) on random time discretization T (h,) with parameters h, > 0
(h)
August 2011
7 / 17

(h)
=
s[0,t]
Xs 1{|Xs |h} t l
x (dx),
(h,h)c
and approximate X by X (h,) = (Wt + bt + Lt )tT (h,) on random time discretization T (h,) with parameters h, > 0 such that all the jump times of L(h) are included in T (h,) , step-size is at most (for approximation of W ).
(h)
The coupled approximation

Compound Poisson approximations (L(h) , L(h ) ).
compensated jumps greater h
0.2
0.0
Lt
(h)
0.2
0.4
0.6
0.0
0.2
0.4 time
0.6
0.8
1.0
August 2011
8 / 17

Compound Poisson approximations (L(h) , L(h ) ).
compensated jumps greater h compensated jumps greater h'
0.2
0.2
0.0
0.0
(h)
Lt
0.4
Lt
(h)
0.2
0.2
0.4
0.6
0.6
0.0
0.2
0.4 time
0.6
0.8
1.0
0.0
0.2
0.4 time
0.6
0.8
1.0
August 2011
8 / 17

Approximation of W on T (h, ) T (h , ) .
Brownian motion
0.2
0.0
Wt
0.2
0.4
0.6
0.0
0.2
0.4 time
0.6
0.8
1.0
August 2011
8 / 17

Approximation of W on T (h,
Brownian motion for (h,)
and T (h , ) .
Brownian motion for (h',')
0.2
0.2
0.0
0.0
0.2
Wt on T' 0.0 0.2 0.4 time 0.6 0.8 1.0
Wt on T
0.2
0.4
0.4
0.6
0.6
0.0
0.2
0.4 time
0.6
0.8
1.0
August 2011
8 / 17

Piecewise constant approximation of (X (h, ) , X (h , ) ).
approximation for (h,) approximation for (h',')
0.2
0.2
0.0
0.0
()
Xt
0.4
Xt
()
0.2
0.2
0.4
0.6
0.6
0.0
0.2
0.4 time
0.6
0.8
1.0
0.0
0.2
0.4 time
0.6
0.8
1.0
August 2011
8 / 17
Multilevel Euler Algorithm

Remember: Telescoping sum
m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
August 2011
9 / 17

m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
Choice: (Y (k) , Y (k1) ) Euler schemes with coupled input (X (hk ,k ) , X (hk1 ,k1 ) )
August 2011
9 / 17

m
E[f (Y (m) )] = E[f (Y (1) )] +

=D (1) k=2
E[f (Y (k) ) f (Y (k1) )]

=D (k)
Choice: (Y (k) , Y (k1) ) Euler schemes with coupled input (X (hk ,k ) , X (hk1 ,k1 ) ) Parameters of the algorithm S(f ): m (number of levels) h1 > h2 > . . . > hm (approximation of L) 1 > 2 > . . . > m (approximation of W ) n1 , . . . , nm (number of replications per level)
Result and Examples
Result
Error: e 2 (S) = sup E[|S(f ) S(f )|2 ]
f Lip(1)
Here: Lip(1) := {f : D[0, 1] R | f 1 Lipschitz w.r.t. supremum norm}
August 2011
10 / 17
Result and Examples
Result
Error: Cost: e 2 (S) = cost(S)
k=1
sup E[|S(f ) S(f )|2 ]

f Lip(1) m
nk E[#breakpoints(Y (k) ) + 1]
August 2011
10 / 17
Result and Examples
Result
k=1
sup E[|S(f ) S(f )|2 ]

f Lip(1) m
Theorem (Dereich, H.)

Let := inf p>0:
(1,1)
|x|p (dx) <
[0, 2]
denote the Blumenthal-Getoor-index of the driving Lvy process. e Then, for suitably chosen parameters, cost(Sn ) n and e(Sn ) n( 1 2 ) .
1 1
August 2011
10 / 17
Result and Examples
Result
k=1
sup E[|S(f ) S(f )|2 ]

f Lip(1) m
Theorem (Dereich, H.)

Let := inf p>0:
(1,1)
|x|p (dx) <
[0, 2]
denote the Blumenthal-Getoor-index of the driving Lvy process. e Then, for suitably chosen parameters, cost(Sn ) n and e(Sn ) n( 1 2 ) .
1 1
Remark: Gaussian approximation improves result for 1 (see Dereich, 2010). Order of convergence: 4 1 for = 0 or [1, 4/3], / 6 2 and
64
for = 0 and [1, 4/3].

August 2011 10 / 17
Result and Examples
Remarks
Related results: Jacod, Kurtz, Mlard and Protter [2007] ee Marxen [2010]
August 2011
11 / 17
Result and Examples
Remarks
Related results: Jacod, Kurtz, Mlard and Protter [2007] ee Marxen [2010] Lower bound: Combine results of Creutzig, Dereich, Mller-Gronbach and Ritter [2009] on lower bounds in u relation to quantization numbers and average Kolmogorov widths, and Aurzada and Dereich [2009] on the coding complexity of Lvy processes. e
August 2011
11 / 17
Result and Examples
Remarks
Related results: Jacod, Kurtz, Mlard and Protter [2007] ee Marxen [2010] Lower bound: Combine results of Creutzig, Dereich, Mller-Gronbach and Ritter [2009] on lower bounds in u relation to quantization numbers and average Kolmogorov widths, and Aurzada and Dereich [2009] on the coding complexity of Lvy processes. e In the case X = Y , for every randomized algorithm Sn with cost(Sn ) e(Sn ) up to some logarithmic terms. n 2
1
n,
August 2011
11 / 17
Result and Examples
Example: -stable processes

Truncated symmetric -stable processes with < 2 and truncation level u>0 Lebesgue density of the Lvy measure e g (x) = c 1(u,u) (x), l |x|1+ x R\{0}.
Blumenthal-Getoor-index = .
August 2011
12 / 17
Result and Examples

Blumenthal-Getoor-index = . By the Theorem e(Sn ) n1/2 , n(1/1/2) , < 1, > 1.
August 2011
12 / 17
Result and Examples

Blumenthal-Getoor-index = . By the Theorem e(Sn ) n1/2 , n(1/1/2) , < 1, > 1.
In the sequel: X with u = 1 and c = 0.1, SDE with a(Xt ) = Xt and y0 = 1, Lookback option with xed strike 1 f (Y ) = ( sup (Yt ) 1)+ .
t[0,1]
August 2011
12 / 17
Result and Examples
Adaptive choice of m and n1 , . . . , nm

Choose
k
= 2k and hk such that ((hk , hk )c ) = 2k .
August 2011
13 / 17
Result and Examples

Choose k = 2k and hk such that ((hk , hk )c ) = 2k . Given > 0, determine m and n1 , . . . , nm such that E[|S(f ) S(f )|2 ] = | E[f (Y ) f (Y (m) )] |2 + Var(S(f )) 2 .
=bias(f (Y (m) ))
August 2011
13 / 17
Result and Examples

Choose k = 2k and hk such that ((hk , hk )c ) = 2k . Given > 0, determine m and n1 , . . . , nm such that E[|S(f ) S(f )|2 ] = | E[f (Y ) f (Y (m) )] |2 + Var(S(f )) 2 .
=bias(f (Y (m) ))
First step: Estimate expectations E[D (1) ], . . . , E[D (5) ] and variances Var(D (1) ), . . . , Var(D (5) ).
Bias and variance estimation for =0.5
q q
Bias and variance estimation for =0.8

= bias = variance 1.0
q q
= bias = variance
log10(biask) and log10(vark)
log10(biask) and log10(vark)
1.5
q
2.0
3
q
2.5
q
3.0
3.5 5 1 2 level k 3 4 1 2 3 level k 4 5
August 2011
13 / 17
Result and Examples

Highest level of accuracy m:
August 2011
14 / 17
Result and Examples

Highest level of accuracy m: E[D (1) ], . . . , E[D (5) ] together with extrapolation give control of the bias(f (Y (k) )) for k N. Choose m such that |bias(f (Y (m) ))|2 2 . 2
August 2011
14 / 17
Result and Examples

Highest level of accuracy m: E[D (1) ], . . . , E[D (5) ] together with extrapolation give control of the bias(f (Y (k) )) for k N. Choose m such that |bias(f (Y (m) ))|2 Replication numbers n1 , . . . , nm : 2 . 2
August 2011
14 / 17
Result and Examples

Highest level of accuracy m: E[D (1) ], . . . , E[D (5) ] together with extrapolation give control of the bias(f (Y (k) )) for k N. Choose m such that |bias(f (Y (m) ))|2 Replication numbers n1 , . . . , nm : Var(D (1) ), . . . , Var(D (5) ) together with extrapolation give control of Var(D (k) ) for k = 1, . . . , m. Choose n1 , . . . , nm with minimal cost(S) such that
m
2 . 2
Var(S) =
k=1
Var(D (k) ) 2 . nk 2
August 2011
14 / 17
Result and Examples

Expample of n1 , . . . , nm with = 0.5. Precisions = (0.003, 0.002, 0.001, 0.0006, 0.0003). Highest levels m = (3, 3, 4, 4, 5).
Replication numbers for = 0.5
precision : 6
q
= 0.003 = 0.002 = 0.001 = 6e04 = 3e04
5 log10(nk)
q
q
3 level k
August 2011
15 / 17
Result and Examples

6
q
precision :
q
5
q
= 0.01 = 0.004 = 0.002 = 0.001 = 7e04
log10(nk)
q
q
3
q
2 1 2 3 4 level k 5 6 7
August 2011
15 / 17
Result and Examples

precision : 5.0
q
4.5
q
= 0.02 = 0.01 = 0.007 = 0.005 = 0.0035
4.0
q
log10(nk)
3.5
q
q
q
q
3.0
q q
2.5
q q
2.0
6 level k
10
11
August 2011
15 / 17
Result and Examples
Empirical relation of error and cost

Error and cost of MLMC and classical MC
= MLMC = MC
2.0
q
q q
log10(error)
2.5
q q q q q
= MLMC MC
q q
0.5 0.47 0.45
0.8 0.46 0.34
1.2 0.38 0.23
3.0
3.5
q
= 0.5 = 0.8 = 1.2 4.5 5.0 5.5 log10(cost) 6.0 6.5 7.0
August 2011
16 / 17
Result and Examples
Summary and Conclusions

Summary: Multilevel algorithm for a wide class of functionals and processes. Up to logs asymptotically optimal for Blumenthal-Getoor-index 1. Heuristics to achieve desired precision > 0. Numerical results match the analytical results. Improvement for 1 via Gaussian correction, see Dereich [2010].
August 2011
17 / 17
Result and Examples
Summary and Conclusions

Summary: Multilevel algorithm for a wide class of functionals and processes. Up to logs asymptotically optimal for Blumenthal-Getoor-index 1. Heuristics to achieve desired precision > 0. Numerical results match the analytical results. Improvement for 1 via Gaussian correction, see Dereich [2010]. Work to do: Further examples of Lvy processes. e Implementation of the ML-algorithm with Gaussian correction. The gap between the upper and lower bound for > 1.
August 2011
17 / 17

Multilevel Monte Carlo For L Evy Driven Sdes: Felix Heidenreich

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Multilevel Monte Carlo For L Evy Driven Sdes: Felix Heidenreich

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Multilevel Monte Carlo For L Evy Driven Sdes: Felix Heidenreich

Uploaded by

Copyright:

Available Formats

Multilevel Monte Carlo for Lvy Driven SDEs e

The Multilevel Monte Carlo Algorithm

Approximation of the Driving Lvy Process e

Result and Examples

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Standard Monte Carlo

where (Yi )i=1,...,n i.i.d. copies of Y .

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Standard Monte Carlo

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Standard Monte Carlo

Path-independent functions f in the diusion case

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Path-independent functions f in the diusion case

with computational cost O(

Remedy: Only for suciently smooth f C 2(+1) .

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Path-independent functions f in the diusion case

with computational cost O(

with computational cost O(

The Multilevel Monte Carlo Algorithm

Multilevel Monte Carlo Algorithms

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

The Multilevel Monte Carlo Algorithm

Multilevel Monte Carlo Algorithms

E[f (Y (m) )] = E[f (Y (1) )] +

E[f (Y (k) ) f (Y (k1) )]

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

The Multilevel Monte Carlo Algorithm

Multilevel Monte Carlo Algorithms

E[f (Y (m) )] = E[f (Y (1) )] +

E[f (Y (k) ) f (Y (k1) )]

Approximate E[D (1) ], . . . , E[D (m) ] by independent Monte Carlo methods

for (Di )i=1,...,nj being i.i.d. copies of D (k) , k = 1, . . . , m.

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

The Multilevel Monte Carlo Algorithm

Multilevel Monte Carlo Algorithms

E[f (Y (m) )] = E[f (Y (1) )] +

E[f (Y (k) ) f (Y (k1) )]

Approximate E[D (1) ], . . . , E[D (m) ] by independent Monte Carlo methods

Approximation of the Driving Lvy Process e

Approximation of the driving Lvy process X e

F. Heidenreich (TU Kaiserslautern)

MLMC for Lvy Driven SDEs e

Approximation of the Driving Lvy Process e

Approximation of the driving Lvy process X e