Complexity of Multilevel Monte Carlo Tau-Leaping

DOI10.1137/130940761zbMATH Open1327.60136arXiv1310.2676OpenAlexW2050083387MaRDI QIDQ5245403FDOQ5245403

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

Publication date: 8 April 2015

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1310.2676

Recommendations

• scientific article; zbMATH DE number 2000348
• Multilevel Monte Carlo approximation of functions
• On the acceleration of the multi-level Monte Carlo method
• Multilevel Monte Carlo in approximate Bayesian computation
• Multilevel Monte Carlo approximation of distribution functions and densities
• On the effective dimension and multilevel Monte Carlo
• scientific article; zbMATH DE number 3878357

zbMATH Keywords

computational complexityvariancecouplingcontinuous-time Markov chainsmultilevel Monte Carlo methodtau-leaping

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Biochemistry, molecular biology (92C40) Probabilistic models, generic numerical methods in probability and statistics (65C20) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Continuous-time Markov processes on discrete state spaces (60J27)

Cited In (21)

• Stochastic representations of ion channel kinetics and exact stochastic simulation of neuronal dynamics
• Analysis of nested multilevel Monte Carlo using approximate normal random variables
• Multilevel Monte Carlo for cortical circuit models
• Stochastic switching in biology: from genotype to phenotype
• Multilevel hybrid split-step implicit tau-leap
• Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
• Modelling biochemical reaction systems by stochastic differential equations with reflection
• Efficiency of the Girsanov transformation approach for parametric sensitivity analysis of stochastic chemical kinetics
• Conditional Monte Carlo for reaction networks
• Low variance couplings for stochastic models of intracellular processes with time-dependent rate functions
• Quasi-Monte Carlo methods applied to tau-leaping in stochastic biological systems
• Fast approximate simulation of finite long-range spin systems
• Multilevel Monte Carlo for stochastic differential equations with small noise
• Coupling sample paths to the thermodynamic limit in Monte Carlo estimators with applications to gene expression
• Error analysis of tau-leap simulation methods
• Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
• Multilevel Monte Carlo EM scheme for MV-SDEs with small noise
• Robustly simulating biochemical reaction kinetics using multi-level Monte Carlo approaches
• Non-nested adaptive timesteps in multilevel Monte Carlo computations
• Thinning and multilevel Monte Carlo methods for piecewise deterministic (Markov) processes with an application to a stochastic Morris-Lecar model
• An introduction to multilevel Monte Carlo for option valuation

This page was built for publication: Complexity of Multilevel Monte Carlo Tau-Leaping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5245403)