IEOR E4603: Monte-Carlo Simulation Columbia University ...

1 IEOR E4603: Monte-Carlo Simulationc 2017 by Martin HaughColumbia UniversitySimulating stochastic Differential EquationsIn these lecture notes we discuss the Simulation of stochastic differential equations (SDEs), focusing mainly onthe Euler scheme and some simple improvements to it. We discuss the concepts of weak and strong convergenceand note that in financial applications it is typically only weak convergence that is required. We also brieflydiscuss variance reduction for SDE s, the Simulation of SDE s for jump-diffusion processes, and the optimalallocation of a fixed computational budget to minimize the mean-squared error of discretized SDE of the development in these notes follows Chapter 6 of Glasserman (2004) and this reference can beconsulted for further details.

2 Finally, in Appendix 6 we present a brief overview ofmultilevelMonte-Carlo, a newand recent technique that also focuses on the optimal allocation of computational The Euler Scheme for DiffusionsSuppose we have an SDE of the formdXt= (t,Xt)dt+ (t,Xt)dWt(1)and that we wish to simulate values ofXTwithout knowing1its distribution. In this event we can simulate adiscretizedversion of the SDE. In particular, we simulate a discretized process,{ X0, Xh, X2h, .. , Xmh},wheremis the number of time steps,his a constant andm=bT/hc. The smaller the value ofh, the closer ourdiscretized path will be to the continuous-time path of (1) that we wish to simulate. Of course this will be atthe expense of greater computational effort.

3 While there are a number of discretizationschemesavailable, thesimplest and most common scheme is theEulerscheme. This scheme is intuitive, easy to implement and satisfies Xkh= X(k 1)h+ ((k 1)h, X(k 1)h)h+ ((k 1)h, X(k 1)h) hZk(2)where theZk s are IIDN(0,1). If we want to estimate :=E[f(XT)]using the Euler scheme, then for a fixednumber of paths,n, and discretization interval,h, we have the following the Euler Scheme to Estimate =E[f(XT)]WhenXtFollows a1-Dimensional SDEforj= 1tont= 0; X=X0fork= 1tobT/hc=:mgenerateZ N(0,1)set X= X+ (t, X)h+ (t, X) h Zsett=t+hend forsetfj=f( X)end forset n= (f1+..+fn))/nset 2n= nj=1(fj n)2/(n 1) (1 ) %CI= n z1 /2 n n1 This could be due to the fact that we cannot solve (1) to obtain an explicit solution forXT, or because we simply cannotdetermine the distribution ofXTeven though we do know how to solve (1).

4 Simulating stochastic Differential Equations2 Remark1 Observe that even though we only care aboutXT, we still need to generate intermediate values,Xih, if we are to minimize thediscretization error. Because of this discretization error, nis no longer anunbiased estimator of .Remark2If we wished to estimate =E[f(Xt1,..,Xtp)]then in general we would need to keep track of(Xt1,..,Xtp)inside the inner for-loop of the you think of a derivative where the payoff depends on(Xt1,..,Xtp), but where it wouldnotbe necessary to keep track of(Xt1,..,Xtp)on each sample path? The Euler Scheme for Multidimensional DiffusionsIn the multidimensional case,Xt Rd,Wt Rpand (t,Xt) Rdin (1) are now vectors, and (t,Xt) Rd pis a matrix.

5 This situation arises when we have aseriesof SDE s in our model. This couldoccur in a number of financial engineering contexts. Some examples include:(1)Modeling the evolution of multiple stocks. This might be necessary if we are trying to pricederivatives whose values depend on multiple stocks or state variables, or if we are studying the propertiesof some portfolio strategy with multiple assets.(2)Modeling the evolution of a single stock where we assume that the volatility of the stock is itselfstochastic. Such a model is termed astochastic volatilitymodel.(3)Modeling the evolution of interest rates. For example, if we assume that the short rate,rt, isdriven by a number of factors which themselves are stochastic and satisfy SDE s, then simulatingrtamounts to simulating the SDE s that drive the factors.

6 Examples include the multi-factor Gaussianand CIR models. Such models also occur in HJM and LIBOR market all of these cases, whether or not we will have to simulate the SDE s will depend on the model in questionand on the particular quantity that we wish to compute. If we do need to discretize the SDE s and simulatetheir discretized versions, then it is very straightforward. If there arepcorrelated Brownian motions,Wt, drivingthe SDE s, then at each time step,ti, we must generatepIIDN(0,1)random variables. We would then use theCholesky Decomposition to generateXti+1. This is exactly analogous to our method of generating correlatedgeometric Brownian motions. In the context of simulating multidimensional SDE s, however, it is more commonto use independent Brownian motions as any correlations between components of the vector,Xt, can beinduced through the matrix, (t,Xt).

7 Weak and Strong Convergence of Discretization SchemesThere are two approaches for measuring the error in a discretization scheme{ X0, Xh, X2h, .. , Xmh}withm=bT/hc. Astrongerror criterion might take the formE[|| Xmh XT||q](3)E[sup0 t T|| Xbt/hch Xt||]for some vector norm|| ||and withq= 1orq= 2in (3). In contrast, aweakerror criterion takes the form E[f( Xmh)] E[f(XT)] (4)wherefranges over smooth functions fromRdtoR. Note that with a weak error criterion, all that matters isthe distribution of Xmhand how it compares to the distribution ofXTand so it s possible to have a very smallweak error even if XmhandXTlive on different probability spaces. In finance applications we generally careabout derivatives prices which are (risk-neutral) expectations and so the weak criterion of (4) is moreappropriate.

8 Given an error criterion, we can assess the performance of the Euler scheme (and others) via itsorder of convergence. We have the following stochastic Differential Equations3 Definition1We say the discretization Xhas astrong order of convergenceof >0ifE[|| Xmh XT||] ch (5)for some constantcand all sufficiently say the discretization Xhas aweak order of convergenceof >0if E[f( Xmh)] E[f(XT)] ch (6)for some constantc(possibly depending onf), all sufficiently smallh, and allf C2 +2 PwhereC2 +2 Pconsistsof functions whose derivatives of all orders up to2 + 2are note that a larger value of in (5) and (6) is better in that it implies a faster convergence of thediscretization error to0.

9 In practice, it is often the case that a given discretization scheme will have a smallerstrong order of convergence than its weak order of convergence. The Euler scheme, for example, has a strongorder of = 1/2whereas3its weak order is = is also worth noting that the conditions onfin Definition 2 are often not met in practice. For example, iffrepresents the payoff of a simple European call option, thenfwill not be differentiable and certainly we will nothavef C2 +2P. Similarly, technical conditions on (t,Xt)and are also sometimes violated in practice. Thismeans, for example, that if we are using an Euler scheme for such an SDE then there is no theoretical guaranteethat it will have a weak order of convergence of = 1.

10 As a result, experimentation is often required tounderstand which schemes perform better, have a superior order (of weak) convergence for a given payofffand / or Other Discretization SchemesThere are several other discretization schemes that (typically) improve on the Euler scheme. We briefly discussthem The Milstein SchemeConsider a scalar SDE of the formdXt= (Xt)dt+ (Xt)dWtwith corresponding Euler scheme Xkh= X(k 1)h+ ( X(k 1)h)h+ ( X(k 1)h) going into the specific details, we can apply It o s Lemma to (Xt)to construct a superiorapproximation for the diffusion term over the interval[(k 1)h,kh]. This leads to the Milstein scheme Xkh= X(k 1)h+ ( X(k 1)h)h+ ( X(k 1)h) hZk+12 ( X(k 1)h) ( X(k 1)h)h(Z2k 1)(7)where (x)denotes the derivative of tox.