Computing mean first exit times for stochastic processes using multi-level Monte Carlo

Desmond Higham, Mikolaj Roj

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

Abstract

The multi-level approach developed by Giles (2008) can be used to estimate mean first exit times for stochastic differential equations, which are of interest in finance, physics and chemical kinetics. Multi-level improves the computational expense of standard Monte Carlo in this setting by an order of magnitude. More precisely, for a target accuracy of TOL, so that the root mean square error of the estimator is O(TOL), the O(TOL-4) cost of standard Monte Carlo can be reduced to O(TOL-3|log(TOL)|1/2) with a multi-level scheme. This result was established in Higham, Mao, Roj, Song, and Yin (2013), and illustrated on some scalar examples. Here, we briefly overview the algorithm and present some new computational results in higher dimensions.
LanguageEnglish
Title of host publicationProceedings of the 2012 Winter Simulation Conference
Subtitle of host publicationWashington D.C.
EditorsC. Laroque, J. Himmelspach, R. Pasupathy, O. Rose, A.M. Uhrmacher
PublisherIEEE
Number of pages10
DOIs
Publication statusPublished - 2012

Fingerprint

stochastic processes
finance
root-mean-square errors
kinetics
estimators
reaction kinetics
differential equations
scalars
costs
physics
estimates

Keywords

  • complexity theory
  • networking
  • multi-level Monte Carlo method
  • computational efficiency

Cite this

Higham, D., & Roj, M. (2012). Computing mean first exit times for stochastic processes using multi-level Monte Carlo. In C. Laroque, J. Himmelspach, R. Pasupathy, O. Rose, & A. M. Uhrmacher (Eds.), Proceedings of the 2012 Winter Simulation Conference: Washington D.C. IEEE. https://doi.org/10.1109/WSC.2012.6465219
Higham, Desmond ; Roj, Mikolaj. / Computing mean first exit times for stochastic processes using multi-level Monte Carlo. Proceedings of the 2012 Winter Simulation Conference: Washington D.C.. editor / C. Laroque ; J. Himmelspach ; R. Pasupathy ; O. Rose ; A.M. Uhrmacher. IEEE, 2012.
@inproceedings{2597ad92db79470b9231cc5c6765906a,
title = "Computing mean first exit times for stochastic processes using multi-level Monte Carlo",
abstract = "The multi-level approach developed by Giles (2008) can be used to estimate mean first exit times for stochastic differential equations, which are of interest in finance, physics and chemical kinetics. Multi-level improves the computational expense of standard Monte Carlo in this setting by an order of magnitude. More precisely, for a target accuracy of TOL, so that the root mean square error of the estimator is O(TOL), the O(TOL-4) cost of standard Monte Carlo can be reduced to O(TOL-3|log(TOL)|1/2) with a multi-level scheme. This result was established in Higham, Mao, Roj, Song, and Yin (2013), and illustrated on some scalar examples. Here, we briefly overview the algorithm and present some new computational results in higher dimensions.",
keywords = "complexity theory, networking, multi-level Monte Carlo method, computational efficiency",
author = "Desmond Higham and Mikolaj Roj",
year = "2012",
doi = "10.1109/WSC.2012.6465219",
language = "English",
editor = "C. Laroque and J. Himmelspach and R. Pasupathy and O. Rose and A.M. Uhrmacher",
booktitle = "Proceedings of the 2012 Winter Simulation Conference",
publisher = "IEEE",

}

Higham, D & Roj, M 2012, Computing mean first exit times for stochastic processes using multi-level Monte Carlo. in C Laroque, J Himmelspach, R Pasupathy, O Rose & AM Uhrmacher (eds), Proceedings of the 2012 Winter Simulation Conference: Washington D.C.. IEEE. https://doi.org/10.1109/WSC.2012.6465219

Computing mean first exit times for stochastic processes using multi-level Monte Carlo. / Higham, Desmond; Roj, Mikolaj.

Proceedings of the 2012 Winter Simulation Conference: Washington D.C.. ed. / C. Laroque; J. Himmelspach; R. Pasupathy; O. Rose; A.M. Uhrmacher. IEEE, 2012.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Computing mean first exit times for stochastic processes using multi-level Monte Carlo

AU - Higham, Desmond

AU - Roj, Mikolaj

PY - 2012

Y1 - 2012

N2 - The multi-level approach developed by Giles (2008) can be used to estimate mean first exit times for stochastic differential equations, which are of interest in finance, physics and chemical kinetics. Multi-level improves the computational expense of standard Monte Carlo in this setting by an order of magnitude. More precisely, for a target accuracy of TOL, so that the root mean square error of the estimator is O(TOL), the O(TOL-4) cost of standard Monte Carlo can be reduced to O(TOL-3|log(TOL)|1/2) with a multi-level scheme. This result was established in Higham, Mao, Roj, Song, and Yin (2013), and illustrated on some scalar examples. Here, we briefly overview the algorithm and present some new computational results in higher dimensions.

AB - The multi-level approach developed by Giles (2008) can be used to estimate mean first exit times for stochastic differential equations, which are of interest in finance, physics and chemical kinetics. Multi-level improves the computational expense of standard Monte Carlo in this setting by an order of magnitude. More precisely, for a target accuracy of TOL, so that the root mean square error of the estimator is O(TOL), the O(TOL-4) cost of standard Monte Carlo can be reduced to O(TOL-3|log(TOL)|1/2) with a multi-level scheme. This result was established in Higham, Mao, Roj, Song, and Yin (2013), and illustrated on some scalar examples. Here, we briefly overview the algorithm and present some new computational results in higher dimensions.

KW - complexity theory

KW - networking

KW - multi-level Monte Carlo method

KW - computational efficiency

UR - http://www.scopus.com/inward/record.url?scp=84874694507&partnerID=8YFLogxK

U2 - 10.1109/WSC.2012.6465219

DO - 10.1109/WSC.2012.6465219

M3 - Conference contribution book

BT - Proceedings of the 2012 Winter Simulation Conference

A2 - Laroque, C.

A2 - Himmelspach, J.

A2 - Pasupathy, R.

A2 - Rose, O.

A2 - Uhrmacher, A.M.

PB - IEEE

ER -

Higham D, Roj M. Computing mean first exit times for stochastic processes using multi-level Monte Carlo. In Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM, editors, Proceedings of the 2012 Winter Simulation Conference: Washington D.C.. IEEE. 2012 https://doi.org/10.1109/WSC.2012.6465219