Mean exit times and the multilevel Monte Carlo method

Desmond Higham, Xuerong Mao, Mikolaj Roj, Qingshuo Song, George Yin

Research output: Contribution to journalArticle

102 Downloads (Pure)

Abstract

Numerical methods for stochastic differential equations are relatively inefficient when used to approximate mean exit times. In particular, although the basic Euler–Maruyama method has weak order equal to one for approximating the expected value of the solution, the order reduces to one half when it is used in a straightforward manner to approximate the mean value of a (stopped) exit time. Consequently, the widely used standard approach of combining an Euler–Maruyama discretization with a Monte Carlo simulation leads to a computationally expensive procedure. In this work, we show that the multilevel approach developed by Giles [Oper. Res., 56 (2008), pp. 607–617] can be adapted to the mean exit time context. In order to justify the algorithm, we analyze the strong error of the discretization method in terms of its ability to approximate the exit time. We then show that the resulting multilevel algorithm improves the expected computational complexity by an order of magnitude, in terms of the required accuracy. Numerical results are provided to illustrate the analysis.
Original languageEnglish
Pages (from-to)2-18
Number of pages17
JournalSIAM/ASA Journal on Uncertainty Quantification (JUQ)
Volume1
Issue number1
DOIs
Publication statusPublished - 27 Mar 2013

Keywords

  • Euler-Maruyama approximation
  • expected computational cost
  • expected hitting time
  • mean exit time
  • Monte Carlo
  • multilevel Monte carlo
  • stochastic differential equation
  • stochastic simulation
  • strong and weak convergence

Fingerprint Dive into the research topics of 'Mean exit times and the multilevel Monte Carlo method'. Together they form a unique fingerprint.

  • Cite this