Approximation of Functionals of SDEs and Application to a Recent Multilevel MC Method

Approximation of Functionals of SDEs and Application to a Recent Multilevel MC Method

Rainer Avikainen

University of Jyv¨askyl¨a

Helsinki University of Technology, August 27 2008

SDE

Consider the SDE

( X0 =x0,

dX_t=σ(t, X_t)dW_t+b(t, X_t)dt,

wherex0∈R,σ, b: [0, T]×R→RandW is a standard one-dimensional Brownian motion.

Assumptions

Assume that σ, b∈C([0, T]×R) and forf ∈ {σ, b}there exists a constant C_T such that

1) |f(t, x)−f(t, y)| ≤CT|x−y|

2) |f(t, x)−f(s, x)| ≤CT(1 +|x|)|t−s|

3) X_T has a bounded density.

Assumption 3) may be replaced by the uniform ellipticity condition 3⁰) σ, b∈C_b^∞([0, T]×R) and

σ(t, x)≥β >0 for all (t, x)∈[0, T]×R.

Theorem 1 (Caballero, Fern´andez, Nualart 1998)

Assume that σ andb areC² in x, the second derivatives have polynomial growth, the functions |σ(0, x)|,|σ_x(t, x)|,|b(0, x)|and|b_x(t, x)|are bounded, and

E

Z t 0

σ(s, X_s)²ds

−p0/2!

<∞

for some p₀ >2 and for allt∈(0, T]. Then for all t∈(0, T]there exists a continuous density fXt of Xt such that for allp >1

fXt(x)≤Cp

Z t 0

σ(s, Xs)²ds −1/2

p

for some constant Cp>0.

Euler scheme

Let πn be the equidistant partition 0 =t0 < t1 <· · ·< tn=T of the interval [0, T] with mesh size |π_n|=T /n.

DefineX^n,E to be the Euler approximation relative to πn , i.e.

X₀^n,E=x0, and

X_t^n,E_i+1 =X_t^n,E_i +b(ti, X_t^n,E_i )(ti+1−ti) +σ(ti, X_t^n,E_i )(Wti+1−Wti).

Then X_T^n,E is the equidistant Euler approximation ofX_T evaluated at the endpointT =t_n.

Theorem 2 (Classical) If1≤p <∞, then

XT −X_T^n,E p ≤Cp

p|π_n|.

Here

C_p ≤e^M(x0,T,CT)p2.

Question

Include a function in the error term.

What is the rate of E|g(X_T)−g(X_T^n,E)|² ifg(x) =χ_[K,∞)(x)?

Ifg is Lipschitz, then E|g(X_T)−g(X_T^n,E)|² ≤L²E|X_T −X_T^n,E|². non-Lipschitz functions

Indicator functions

Theorem 3

Let 0< p <∞ and suppose thatX is a random variable.

IfX has a bounded density f_X, then for all K∈Rand for all random variables Xˆ we have

E|χ_[K,∞)(X)−χ[K,∞)( ˆX)| ≤3(supfX)

p p+1

X−Xˆ

p p+1

p , where _p+1^p is the optimal exponent.

If there existp₀>0andB_X >0such that for all p₀ ≤p <∞, all K ∈R, and all random variablesXˆ we have

E|χ_[K,∞)(X)−χ_[K,∞)( ˆX)| ≤B_X X−Xˆ

p p+1

p , then X has a bounded density.

Functions of bounded variation

Let BV be the class of functions of bounded variation on the real line and denote the variation ofg∈BV byV(g).

For any g∈BV (up to continuity and normalization) there exist a unique σ-finite signed measure µsuch that

g(x) =µ((−∞, x)).

Ifµ=µ1−µ2 is the Jordan decomposition, then |µ|=µ1+µ2.

Result for BV

Theorem 4 (Rate for equidistant Euler scheme)

Let 1≤p <∞ andg∈BV. Then there existsn0∈Nsuch that for n≥n₀ we have

E|g(X_T)−g(X_T^n,E)|^p ≤3^p(supf_XT ∨p

supf_XT)V(g)^pn⁻

1

2+ ^M

(logn)1/3

, where M depends onx0,T and the Lipschitz coefficients.

Idea of the proof

Start by considering the caseg=χ_[K,∞). For 1≤q <∞,

E|χ_[K,∞)(X_T)−χ_[K,∞)(X_T^n,E)| ≤ 3(supf_XT)^q+1q

X_T −X_T^n,E

q q+1

q

≤ 3(supf_XT)^q+1q C

q q+1

q n^−12q+1q . Find optimal q by computing

1≤q<∞inf C

q q+1

q n⁻¹²

q q+1.

Then there exists n0∈Nsuch that for alln≥n0 we have E|χ_[K,∞)(XT)−χ_[K,∞)(X_T^n,E)| ≤3(supfX_T ∨p

supfX_T)n⁻

1

2+ ^M

(logn)1/3

.

Idea of the proof

Then

g(x) =µ((−∞, x)) = Z

Rχ_(−∞,x)(z)dµ(z) = Z

Rχ_(z,∞)(x)dµ(z).

and

E|g(X_T)−g(X_T^n,E)|=E Z

Rχ_(z,∞)(X_T)−χ_(z,∞)(X_T^n,E)dµ(z)

≤ Z

RE

χ_[z,∞)(XT)−χ_[z,∞)(X_T^n,E)

d|µ|(z)

≤3(supf_XT ∨p

supf_XT)V(g)n⁻

1

2+ ^M

(logn)1/3

.

Lower bound

Let S be the geometric Brownian motion.

Theorem 5

There exist K0>0such that lim inf

n→∞

√n sup

K≥K0

E|χ_[K,∞)(S₁)−χ_[K,∞)(S₁^n,E)|>0.

Therefore, since V(χ[K,∞)) = 1, it is impossible to findγ > ¹₂ such that E|g(S₁)−g(S₁^n,E)| ≤cV(g)

1 n

γ

. Whether γ = ¹₂ is possible remains open.

Multilevel Monte Carlo Method (Michael B. Giles, 2006)

Define payoff P :=g(XT).

Goal: to approximate the expected payoff EP =Eg(X_T).

1^◦ Define time stepsh_l:= _M^T_l forl= 0,1, . . . , L 2^◦ Approximate X_T by a numerical discretization ˆX_l

using time step hl (e.g. Euler) 3^◦ Approximate P by ˆP_l =g( ˆX_l) 4^◦ Write

EPˆ_L=EPˆ0+

L

X

l=1

E[ ˆP_l−Pˆl−1] 5^◦ Let ˆY₀ be an estimator ofEPˆ₀ using N₀ samples

6^◦ Let ˆYl,l≥1, be an estimator ofE[ ˆPl−Pˆl−1] using Nl paths 7^◦ Consider the combined estimator

Yˆ =

L

XYˆ_l

Multilevel Monte Carlo Method

Example:

Yˆ =

L

X

l=0

Yˆl, where

Yˆ_l = 1 N_l

Nl

X

i=1

Pˆ_l⁽ⁱ⁾−Pˆ_l−1⁽ⁱ⁾ .

It is easy to show that

V ar( ˆY_l) = V ar( ˆP_l−Pˆl−1) Nl

and

C( ˆY_l)≤ cN_l hl

.

Multilevel Monte Carlo Method

Theorem 6 (Giles 2006)

Suppose that there exist independent estimators Yˆ_l based on N_l Monte Carlo samples, and positive constants α≥ ¹₂,β,c1,c2,c3, such that

i) |E[ ˆPl−P]| ≤c1h^α_l,

ii) EYˆ_l =

(EPˆ₀, l= 0, E[ ˆP_l−Pˆ_l−1], l >0, iii) V ar( ˆY_l)≤c₂N_l⁻¹h^β_l,

iv) C( ˆY_l)≤c₃N_lh⁻¹_l .

Multilevel Monte Carlo Method

Then there exists c4>0 such that for anyε <1/ethere are valuesL and N_l for which the multilevel estimator

Yˆ =

L

X

l=0

Yˆl

has

M SE =E( ˆY −EP)² < ε² and

C( ˆY)≤







c4ε⁻², β >1, c₄ε⁻²(logε)², β= 1, c4ε^{−2−(1−β)α} , 0< β <1.

Application

Consider the Euler scheme and the estimator Yˆ_l = 1

Nl N_l

X

i=1

Pˆ_l⁽ⁱ⁾−Pˆ_l−1⁽ⁱ⁾ .

We have to determine the parameters α andβ in the conditions i) |E[ ˆPl−P]| ≤c1h^α_l, and

iii) V ar( ˆY_l)≤c2N_l⁻¹h^β_l,

Parameter α

We have α= 1 in

i) |E[ ˆP_l−P]|=|Eg( ˆX_l)−Eg(X_T)| ≤c₁h^α_l by weak convergence results:

Talay, Tubaro (1990): g∈C_pol^∞, under the assumptionσ, b∈C_b^∞ Bally, Talay (1996): g measurable and bounded, under uniform hypoellipticity

Guyon (2006): extension to measurable functions with exponential growth, under uniform ellipticity

Parameter β

For ˆYl the condition is

iii) V ar( ˆY_l) =N_l⁻¹V ar( ˆP_l−Pˆl−1)≤c₂N_l⁻¹h^β_l, so we have to determineβ in V ar( ˆP_l−Pˆl−1)≤c2h^β_l.

V ar( ˆP_l−Pˆl−1) ≤ q

V ar( ˆP_l−P) + q

V ar( ˆPl−1−P) 2

≤

qE( ˆP_l−P)²+

qE( ˆPl−1−P)² 2

Ifg is Lipschitz, then β= 1.

Ifg∈BV, then Theorem 4 implies that β = ¹₂ − ^A

((llogM)∨B)^1/3.

Theorem 3 applied to the Giles’ method

Corollary 7

Given g∈BV and the assumptions of Theorem 6 with α= 1 and β = ¹₂ − ^A

((llogM)∨B)^1/3, there existsc₄ >0 such that for any ε <1/e there are values Land N_l for which the multilevel estimator

Yˆ =

L

X

l=0

Yˆ_l has

M SE < ε^2−δ(ε), where δ(ε)→0 as ε→0, and

C( ˆY)≤c₄ε^{−2−(1−1/2)1} =c₄ε^−2.5.

References

Vlad Bally, Denis Talay,The Law of the Euler Scheme for SDEs: I. Convergence Rate of the Distribution Function. Probab.

Theory Related Fields 104 (1996), no. 1, 43–60.

Nicolas Bouleau, Dominique L´epingle,Numerical Methods for Stochastic Processes. Wiley, 1994.

Michael B. Giles,Multilevel Monte Carlo Path Simulation. Oper.

Res. 56, 3 (2008), 607–617.

Jean Jacod, Philip Protter,Asymptotic Error Distributions for the Euler Method for Stochastic Differential Equations. Ann. Prob. 26 (1998), no. 1, 267–307.

Peter E. Kloeden, Eckhard Platen,Numerical Solutions of Stochastic Differential Equations. Springer-Verlag, 1992.