Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
From MaRDI portal
Publication:2909532
DOI10.1137/110840546zbMATH Open1262.60072arXiv1107.2181OpenAlexW2962834951MaRDI QIDQ2909532FDOQ2909532
Authors: Desmond J. Higham, David F. Anderson 
Publication date: 30 August 2012
Published in: Multiscale Modeling \& Simulation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1107.2181
Recommendations
- Complexity of Multilevel Monte Carlo Tau-Leaping
- Robustly simulating biochemical reaction kinetics using multi-level Monte Carlo approaches
- Importance sampling for a robust and efficient multilevel Monte Carlo estimator for stochastic reaction networks
- Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Biochemistry, molecular biology (92C40) Probabilistic models, generic numerical methods in probability and statistics (65C20) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35)
Cited In (46)
- Estimation of parameter sensitivities for stochastic reaction networks using tau-leap simulations
- Decision-making under uncertainty: using MLMC for efficient estimation of EVPPI
- A Multilevel Monte Carlo Asymptotic-Preserving Particle Method for Kinetic Equations in the Diffusion Limit
- Multifidelity multilevel Monte Carlo to accelerate approximate Bayesian parameter inference for partially observed stochastic processes
- Automated importance sampling via optimal control for stochastic reaction networks: a Markovian projection-based approach
- Learning-based importance sampling via stochastic optimal control for stochastic reaction networks
- Stochastic representations of ion channel kinetics and exact stochastic simulation of neuronal dynamics
- A multilevel adaptive reaction-splitting simulation method for stochastic reaction networks
- Analysis of nested multilevel Monte Carlo using approximate normal random variables
- A multilevel Monte Carlo method for asymptotic-preserving particle schemes in the diffusive limit
- Multilevel Monte Carlo for cortical circuit models
- Stochastic switching in biology: from genotype to phenotype
- Multilevel hybrid split-step implicit tau-leap
- Multiscale Simulation of Stochastic Reaction-Diffusion Networks
- A first step to implement Gillespie's algorithm with rejection sampling
- Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
- Continuous-time random walks for the numerical solution of stochastic differential equations
- Variance-reduced simulation of lattice discrete-time Markov chains with applications in reaction networks
- Stability and Strong Convergence for Spatial Stochastic Kinetics
- Conditional Monte Carlo for reaction networks
- Continuum approximation of invasion probabilities
- Multiscale Global Sensitivity Analysis for Stochastic Chemical Systems
- Variance reduction with array-RQMC for tau-leaping simulation of stochastic biological and chemical reaction networks
- Multilevel rejection sampling for approximate Bayesian computation
- Reduction for stochastic biochemical reaction networks with multiscale conservations
- Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution
- Statistical inference for dynamical systems: a review
- Low variance couplings for stochastic models of intracellular processes with time-dependent rate functions
- Exact variance-reduced simulation of lattice continuous-time Markov chains with applications in reaction networks
- Quasi-Monte Carlo methods applied to tau-leaping in stochastic biological systems
- Jump-Diffusion Approximation of Stochastic Reaction Dynamics: Error Bounds and Algorithms
- Importance sampling for a robust and efficient multilevel Monte Carlo estimator for stochastic reaction networks
- Fast approximate simulation of finite long-range spin systems
- Tensor product approach to modelling epidemics on networks
- Extending the multi-level method for the simulation of stochastic biological 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
- A multilevel approach to stochastic trace estimation
- A highly parallel algorithm for computing the action of a matrix exponential on a vector based on a multilevel Monte Carlo method
- A probabilistic linear solver based on a multilevel Monte Carlo method
- 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
- Slow-scale split-step tau-leap method for stiff stochastic chemical systems
- Central limit theorems for multilevel Monte Carlo methods
- On the implementation of multilevel Monte Carlo simulation of the stochastic volatility and interest rate model using multi-GPU clusters
This page was built for publication: Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909532)
