Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
From MaRDI portal
Abstract: We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This allows a range of widely used competing strategies to be judged systematically. Our setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some path functional of the state of the system at a fixed time point. We study the use of standard Monte Carlo when samples are produced by exact simulation and by approximation with tau-leaping or an Euler-Maruyama discretization of a diffusion approximation. Appropriate modifications of recently proposed multilevel Monte Carlo algorithms are also studied for the tau-leaping and Euler-Maruyama approaches. In order to quantify computational complexity in a tractable yet meaningful manner, we consider a parameterization that, in the mass action chemical kinetics setting, corresponds to the classical system size scaling. We base the analysis on a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that, under the specific assumptions made in the manuscript, if the bias inherent in the diffusion approximation is smaller than the required accuracy, then multilevel Monte Carlo for the diffusion approximation is most efficient, besting multilevel Monte Carlo with tau-leaping by a factor of a logarithm of the scaling parameter. However, if the bias of the diffusion model is greater than the error tolerance, or if the bias can not be bounded analytically, multilevel versions of tau-leaping are often the optimal choice.
Recommendations
- scientific article; zbMATH DE number 953025
- scientific article; zbMATH DE number 3878357
- Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
- Theory and algorithms for mixed Monte Carlo-stochastic dynamics simulations
- Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits
- Efficient sequential Monte Carlo algorithms for integrated population models
- Computational complexity of stochastic programming: Monte Carlo sampling approach
- Complexity of randomized algorithms for underdamped Langevin dynamics
Cites work
- A weak trapezoidal method for a class of stochastic differential equations
- Asymptotic analysis of multiscale approximations to reaction networks
- Complexity of Multilevel Monte Carlo Tau-Leaping
- Divergence of the multilevel Monte Carlo Euler method for nonlinear stochastic differential equations
- Error analysis of tau-leap simulation methods
- scientific article; zbMATH DE number 3864223 (Why is no real title available?)
- scientific article; zbMATH DE number 5070674 (Why is no real title available?)
- scientific article; zbMATH DE number 54145 (Why is no real title available?)
- Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
- Multilevel Monte Carlo for stochastic differential equations with small noise
- Multilevel Monte Carlo Path Simulation
- On reduced models for the chemical master equation
- Stochastic analysis of biochemical systems
- Stochastic approach to chemical kinetics
- Stochastic modelling for systems biology.
- Stochastic population processes. Analysis, approximation, simulations.
- Strong and weak divergence in finite time of Euler's method for stochastic differential equations with non-globally Lipschitz continuous coefficients
- Strong approximation theorems for density dependent Markov chains
- Unbiased estimation with square root convergence for SDE models
- Weak error analysis of numerical methods for stochastic models of population processes
Cited in
(7)- Coupling sample paths to the thermodynamic limit in Monte Carlo estimators with applications to gene expression
- Low variance couplings for stochastic models of intracellular processes with time-dependent rate functions
- Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
- Weak error analysis of numerical methods for stochastic models of population processes
- Conditional Monte Carlo for reaction networks
- Eikonal solutions for moment hierarchies of chemical reaction networks in the limits of large particle number
- Expected residual minimization formulation for stochastic absolute value equations
This page was built for publication: Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4689147)
