Complexity of multilevel Monte Carlo tau-Leaping

David F. Anderson, Desmond J. Higham, Yu Sun

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

Tau-leaping is a popular discretization method for generating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are significantly sharper than previous ones. We avoid taking asymptotic limits and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tau-leaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary over
several orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel Monte Carlo was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poisson-driven jump systems that we consider
here. We also present computational results that illustrate the new analysis.
LanguageEnglish
Pages3106-3127
Number of pages22
JournalSIAM Journal on Numerical Analysis
Volume52
Issue number6
Early online date18 Dec 2014
DOIs
Publication statusPublished - 2014

Fingerprint

Markov processes
Reaction rates
Rate constants
Computational complexity
Numerical methods
Path
Random Time Change
Jump System
Exact Simulation
Moment
Asymptotic Limit
Discretization Method
Sharp Bound
Reaction Rate
Rate Constant
Expected Value
Strong Convergence
Diffusion equation
Convergence Results
Computational Results

Keywords

  • computational complexity
  • coupling
  • continuous time Markov chain
  • tau-leaping
  • variance
  • multilevel Monte Carlo

Cite this

Anderson, David F. ; Higham, Desmond J. ; Sun, Yu. / Complexity of multilevel Monte Carlo tau-Leaping. In: SIAM Journal on Numerical Analysis. 2014 ; Vol. 52, No. 6. pp. 3106-3127.
@article{f393f23c6e1b4106812d42a8ac970d7e,
title = "Complexity of multilevel Monte Carlo tau-Leaping",
abstract = "Tau-leaping is a popular discretization method for generating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are significantly sharper than previous ones. We avoid taking asymptotic limits and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tau-leaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary overseveral orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel Monte Carlo was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poisson-driven jump systems that we considerhere. We also present computational results that illustrate the new analysis.",
keywords = "computational complexity, coupling, continuous time Markov chain, tau-leaping, variance, multilevel Monte Carlo",
author = "Anderson, {David F.} and Higham, {Desmond J.} and Yu Sun",
year = "2014",
doi = "10.1137/130940761",
language = "English",
volume = "52",
pages = "3106--3127",
journal = "SIAM Journal on Numerical Analysis",
issn = "0036-1429",
number = "6",

}

Complexity of multilevel Monte Carlo tau-Leaping. / Anderson, David F.; Higham, Desmond J.; Sun, Yu.

In: SIAM Journal on Numerical Analysis, Vol. 52, No. 6, 2014, p. 3106-3127.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Complexity of multilevel Monte Carlo tau-Leaping

AU - Anderson, David F.

AU - Higham, Desmond J.

AU - Sun, Yu

PY - 2014

Y1 - 2014

N2 - Tau-leaping is a popular discretization method for generating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are significantly sharper than previous ones. We avoid taking asymptotic limits and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tau-leaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary overseveral orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel Monte Carlo was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poisson-driven jump systems that we considerhere. We also present computational results that illustrate the new analysis.

AB - Tau-leaping is a popular discretization method for generating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are significantly sharper than previous ones. We avoid taking asymptotic limits and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tau-leaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary overseveral orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel Monte Carlo was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poisson-driven jump systems that we considerhere. We also present computational results that illustrate the new analysis.

KW - computational complexity

KW - coupling

KW - continuous time Markov chain

KW - tau-leaping

KW - variance

KW - multilevel Monte Carlo

U2 - 10.1137/130940761

DO - 10.1137/130940761

M3 - Article

VL - 52

SP - 3106

EP - 3127

JO - SIAM Journal on Numerical Analysis

T2 - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

SN - 0036-1429

IS - 6

ER -