Euler and Milstein Discretization - frouah.com

1 Euler and Milstein Discretization by Fabrice Douglas Rouah "Monte Carlo simulation" in the context of option pricing refers to a set of techniques to generate underlying values typically stock prices or interest rates over time. Typically the dynamics of these stock prices and interest rates are assumed to be driven by a continuous-time stochastic process. Simulation, however, is done at discrete time steps. Hence, the rst step in any simulation scheme is to nd a way to "discretize" a continuous-time process into a dis- crete time process. In this Note we present two Discretization schemes, Euler and Milstein Discretization , and illustrate both with the Black-Scholes and the Heston models. We assume that the stock price St is driven by the stochastic di erential equation (SDE). dSt = (St ; t) dt + (St ; t) dWt (1). where Wt is Brownian motion.

2 We simulate St over the time interval [0; T ], which we assume to be is discretized as 0 = t1 < t2 < < tm = T , where the time increments are equally spaced with width dt: Equally-spaced time increments is primarily used for notational convenience, because it allows us to write ti ti 1 as simply dt: All the results derived with equally-spaced increments are easily generalized to unequal spacing. Integrating dSt from t to t + dt produces Z t+dt Z t+dt St+dt = St + (Su ; u) du + (Su ; u) dWu : (2). t t Equation (2) is the starting point for any Discretization scheme. At time t, the value of St is known, and we wish to obtain the next value St+dt . 1 Euler Scheme The simplest way to discretize the process in Equation (2) is to use Euler dis- cretization. This is equivalent to approximating the integrals using the left- point rule. Hence the rst integral is approximated as the product of the integrand at time t, and the integration range dt Z t+dt Z t+dt (Su ; u) du (St ; t) du t t = (St ; t) dt: We use the left-point rule since at time t the value (St ; t) is known.

3 The right-hand rule would require that (St+dt ; t + dt) be known at time t. In an 1. identical fashion, the second integral is approximated as Z t+dt Z t+dt (Su ; u) dWu (St ; t) dWu t t = (St ; t) (Wt+dt Wt ). p = (St ; t) dtZ;. p since Wt+dt Wt and dtZ are identical in distribution, where Z is a standard normal variable. Hence, Euler Discretization of (2) is p St+dt = St + (St ; t) dt + (St ; t) dtZ: (3). Euler Scheme for the Black-Scholes Model The Black-Scholes stock price dynamics under the risk neutral measure are dSt = rSt dt + St dWt : (4). An application of Equation (3) produces Euler Discretization for the Black- Scholes model p St+dt = St + rSt dt + St dtZ: (5). Alternatively, we can generate log-stock prices, and exponentiate the result. By It o's lemma ln St follows the process 1 2. d ln St = r dt + dWt : (6). 2. Euler Discretization via Equation (3) produces 1 2.

4 P ln St+dt = ln St + r dt + dtZ. 2. so that 1 2. p St+dt = St exp r dt + dtZ : (7). 2. where dt = ti ti 1. Euler Scheme for the Heston Model The Heston model is described by the bivariate stochastic process for the stock price St and its variance vt p dSt = rSt dt + vt St dW1;t (8). p dvt = ( vt ) dt + vt dW2;t where E [dW1;t dW2;t ] = dt. 2. Discretization of vt The SDE for vt in (8) in integral form is Z t+dt Z t+dt p vt+dt = vt + ( vu ) du + vu dW2;u : (9). t t The Euler Discretization approximates the integrals using the left-point rule Z t+dt ( vu ) du ( vt ) dt t Z t+dt p p vu dW2;u vt (Wt+dt Wt ). t p = vt dtZv where Zv is a standard normal random variable. The right hand side involves ( vt ) rather than ( vt+dt ) since at time t we don't know the value of vt+dt . This leaves us with p vt+dt = vt + ( vt ) dt + vt dtZv : To avoid negative variances, we can replace vt with vt+ = max (0; vt ).

5 This is the full truncation scheme. The re ection scheme replaces vt with its absolute value jvt j. Process for St In a similar fashion, the SDE for St in (8) is written in integral form as Z t+dt Z t+dt p St+dt = St + r Su du + vu Su dWu : t t Euler Discretization approximates the integrals with the left-point rule Z t+dt Su du St dt t Z t+dt p p vu Su dW1;u vt St (Wt+dt Wt ). t p = vt dtSt Zs where Zs is a standard normal random variable that has correlation with Zv . We end up with p St+dt = St + rSt dt + vt dtSt Zs : 3. Process for ln St By It o's lemma ln St follows the di usion 1 p d ln St = r vt dt + vt dW1;t 2. or in integral form Z t Z t 1 p ln St+dt = ln St + r vu du + vu dW1;u : 0 2 0. Euler Discretization of the process for ln St is thus 1 p ln St+dt = ln St + r vt dt + vt (W1;t+dt W1;t ) (10). 2. 1 p = ln St + r vt dt + vt dtZs : 2.

6 Hence the Euler Discretization of St is 1 p St+dt = St exp r vt dt + vt dtZs : 2. Again, to avoid negative variances we must apply the full truncation or re ection scheme by replacing vt everywhere with vt+ or with jvt j. Process for (St ; vt ) or (ln St ; vt ). Start with the initial values S0 for the stock price and v0 for the variance. Given a value for vt at time t, we rst obtain vt+dt from p vt+dt = vt + ( vt ) dt + vt dtZv and we obtain St+dt from p St+dt = St + rSt dt + vt dtSt Zs or from 1 p St+dt = St exp r vt dt + vt dtZs : 2. To generate Zv and Zs with correlation , we rst generate two independent standard p normal variable Z1 and Z2 , and we set Zv = Z1 and Zs = Z1 +. 1 2Z . 2. 4. 2 Milstein Scheme This scheme is described in Glasserman [2] and in Kloeden and Platen [4] for general processes, and in Kahl and Jackel [3] for stochastic volatility models.

7 The scheme works for SDEs for which the coe cients (St ) and (St ) depend only on S, and do not depend on t directly. Hence we assume that the stock price St is driven by the SDE. dSt = (St ) dt + (St ) dWt (11). = t dt + t dWt : In integral form Z t+dt Z t+dt St+dt = St + s ds + s dWs : (12). t t The key to the Milstein scheme is that the accuracy of the Discretization is increased by considering expansions of the coe cients t = (St ) and t =. (St ) via It o's lemma. This is sensible since the coe cients are functions of S. Indeed, we can apply It o's Lemma to the functions t and t as we would for any di erentiable function of S. By It o's lemma, then, the SDEs for the coe cients are 0 1 00 2 0. d t = t t + t t dt + ( t t ) dWt 2. 0 1 00 2 0. d t = t t+ t t dt + ( t t ) dWt 2. where the prime refers to di erentiation in S and where the derivatives in t are zero because we assume that t and t have no direct dependence on t.

8 The integral form of the coe cients at time s (with t < s < t + dt). Z s Z s 0 1 00 2. s = t + u u + u u du + ( 0u u ) dWu t 2 t Z s Z s 0 1 00 2. s = t+ u u+ u u du + ( 0u u ) dWu : t 2 t Substitute for s and s in (12) to produce Z t+dt Z s Z s 0 1 00 2 0. St+dt = St + t + u u + u u du + ( u u ) dWu ds t t 2 t Z t+dt Z s Z s 0 1 00 2 0. + t + u u + u u du + ( u u ) dWu dWs t t 2 t 2 3=2. The terms higher than order one are dsdu = O (dt) and dsdWu = O (dt). and are ignored. The term involving dWu dWs is retained since dWu dWs =. 5. O (dt) is of order one. This leaves us with Z t+dt Z t+dt Z t+dt Z s 0. St+dt = St + t ds + t dWs + ( u u ) dWu dWs : (13). t t t t Apply Euler Discretization to the last term to obtain Z t+dt Z s Z t+dt Z s 0 0. u u dWu dWs t t dWu dWs (14). t t t t Z t+dt 0. = t t (Ws Wt ) dWs t Z ! t+dt 0. = t t Ws dWs Wt Wt+dt + Wt2.

9 T Now de ne dYt = Wt dWt . Using It o's Lemma, it is easy to show1 that Yt has solution Yt = 21 Wt2 12 t so that Z t+dt 1 2 1 2 1. Ws dWs = Yt+dt Yt = W W dt: (15). t 2 t+dt 2 t 2. Substitute back into (14) to obtain Z t+dt Z s h i 0 1 0 2. u u dWu dWs u u (Wt+dt Wt ) dt t t 2. 1 h i 0 2. = : u u ( Wt ) dt : 2. p where Wt = Wt+dt Wt , which is equal in distribution to dtZ with Z. distributed as standard normal. Combining Equations (13) and (15) the general form of Milstein Discretization is therefore p 1 0. St+dt = St + t dt + t dtZ + t t dt Z2 1 : (16). 2. Milstein Scheme for the Black-Scholes Model In the Black-Scholes model Equation (4) we have (St ) = rSt and (St ) = St so the Milstein scheme (16) is p 1 2. St+dt = St + rSt dt + St dtZ + dt Z 2 1. 2. which adds the correction term 21 2 dt Z 2 1 to the Euler scheme in (5). In the Black-Scholes model for the log-stock price, Equation (6), we have (St ) =.

10 1 Indeed, @Y = 1 @Y @2Y 1 1. @t 2 ; = W , and @W 2. = 1, so that dYt = 2. +0+ 2. 1 1 dt +. (Wt 1) dWt = Wt dWt . 6. r 12 2 and (St ) = so that 0. t = 0. t = 0: The Milstein scheme (16) is therefore 1 2. p ln St+dt = ln St + r dt + dtZ. 2. which is identical to the Euler scheme in (7). Hence, while the Milstein scheme improves the Discretization of St in the Black-Scholes model, it does not improve the Discretization of ln St . Milstein Scheme for the Heston Model Recall that this model is given in Equation (8) as p dSt = rSt dt + vt St dW1;t p dvt = ( vt ) dt + vt dW2;t Process for vt p The coe cients of the variance process are (vt ) = ( vt ) and (vt ) = vt so an application of Equation (16) for vt produces p 1 2. vt+dt = vt + ( vt ) dt + vt dtZv + dt Zv2 1 (17). 4. which can be written 2. p 1 p 1 2. vt+dt = vt + dtZv + ( vt ) dt dt: 2 4.