Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
From MaRDI portal
Publication:2909532
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.
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
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
- Stochastic representations of ion channel kinetics and exact stochastic simulation of neuronal dynamics
- Learning-based importance sampling via stochastic optimal control for stochastic reaction networks
- A multilevel adaptive reaction-splitting simulation method for stochastic reaction networks
- A multilevel Monte Carlo method for asymptotic-preserving particle schemes in the diffusive limit
- Multilevel Monte Carlo for cortical circuit models
- Analysis of nested multilevel Monte Carlo using approximate normal random variables
- 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
- Variance-reduced simulation of lattice discrete-time Markov chains with applications in reaction networks
- Continuous-time random walks for the numerical solution of stochastic differential equations
- 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
- Multilevel rejection sampling for approximate Bayesian computation
- Variance reduction with array-RQMC for tau-leaping simulation of stochastic biological and chemical reaction networks
- Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution
- Reduction for stochastic biochemical reaction networks with multiscale conservations
- 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
- Extending the multi-level method for the simulation of stochastic biological systems
- Tensor product approach to modelling epidemics on networks
- 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)
