Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics

David Anderson, Desmond Higham

Research output: Contribution to journalArticle

32 Citations (Scopus)

Abstract

We show how to extend a recently proposed multi-level Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is non-trivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multi-level Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the Bortz-Kalos-Lebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the n-fold way, the next reaction method,the residence-time algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tau-leaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multi-level discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.
LanguageEnglish
Pages146-179
Number of pages34
JournalMultiscale Modeling and Simulation: A SIAM Interdisciplinary Journal
Volume10
Issue number1
Early online date8 Mar 2012
DOIs
Publication statusPublished - 2012

Fingerprint

Continuous-time Markov Chain
Markov chains
Markov chain
Markov processes
Kinetics
kinetics
estimators
Unbiased estimator
Computational Complexity
Computational complexity
Chemical Reaction Networks
Kinetic Monte Carlo
Residence Time
Stochastic Simulation
Exact Algorithms
Discrete Event Simulation
terminology
Expected Value
Notation
Discrete event simulation

Keywords

  • markov chain
  • Monte Carlo Markov chains
  • biochemical kinetics
  • reaction network
  • computational complexity
  • Gillespie
  • random time change
  • tau-leaping

Cite this

@article{fea85ff37d984add942ed2a7966ed95c,
title = "Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics",
abstract = "We show how to extend a recently proposed multi-level Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is non-trivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multi-level Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the Bortz-Kalos-Lebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the n-fold way, the next reaction method,the residence-time algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tau-leaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multi-level discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.",
keywords = "markov chain, Monte Carlo Markov chains, biochemical kinetics, reaction network, computational complexity, Gillespie, random time change, tau-leaping",
author = "David Anderson and Desmond Higham",
year = "2012",
doi = "10.1137/110840546",
language = "English",
volume = "10",
pages = "146--179",
journal = "Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal",
issn = "1540-3459",
number = "1",

}

Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics. / Anderson, David; Higham, Desmond.

In: Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal , Vol. 10, No. 1, 2012, p. 146-179.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics

AU - Anderson, David

AU - Higham, Desmond

PY - 2012

Y1 - 2012

N2 - We show how to extend a recently proposed multi-level Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is non-trivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multi-level Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the Bortz-Kalos-Lebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the n-fold way, the next reaction method,the residence-time algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tau-leaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multi-level discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.

AB - We show how to extend a recently proposed multi-level Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is non-trivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multi-level Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the Bortz-Kalos-Lebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the n-fold way, the next reaction method,the residence-time algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tau-leaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multi-level discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.

KW - markov chain

KW - Monte Carlo Markov chains

KW - biochemical kinetics

KW - reaction network

KW - computational complexity

KW - Gillespie

KW - random time change

KW - tau-leaping

U2 - 10.1137/110840546

DO - 10.1137/110840546

M3 - Article

VL - 10

SP - 146

EP - 179

JO - Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal

T2 - Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal

JF - Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal

SN - 1540-3459

IS - 1

ER -