Multilevel hybrid Chernoff tau-leap

DOI10.1137/130925657zbMATH Open1348.60112arXiv1403.2943OpenAlexW2093122667WikidataQ61773061 ScholiaQ61773061MaRDI QIDQ285281FDOQ285281

Alvaro Moraes, Pedro Vilanova, R. Tempone

Publication date: 19 May 2016

Published in: Multiscale Modeling & Simulation, BIT (Search for Journal in Brave)

Abstract: In this work, we extend the hybrid Chernoff tau-leap method to the multilevel Monte Carlo (MLMC) setting. Inspired by the work of Anderson and Higham on the tau-leap MLMC method with uniform time steps, we develop a novel algorithm that is able to couple two hybrid Chernoff tau-leap paths at different levels. Using dual-weighted residual expansion techniques, we also develop a new way to estimate the variance of the difference of two consecutive levels and the bias. This is crucial because the computational work required to stabilize the coefficient of variation of the sample estimators of both quantities is often unaffordable for the deepest levels of the MLMC hierarchy. Our method bounds the global computational error to be below a prescribed tolerance, $TOL$, within a given confidence level. This is achieved with nearly optimal computational work. Indeed, the computational complexity of our method is of order $mathcalOleft(TO{L}^{-2}ight)$, the same as with an exact method, but with a smaller constant. Our numerical examples show substantial gains with respect to the previous single-level approach and the Stochastic Simulation Algorithm.

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

Recommendations

• Multilevel hybrid Chernoff tau-leap
• Multilevel hybrid split-step implicit tau-leap
• A new hybrid stochastic approximation algorithm
• scientific article; zbMATH DE number 1160628
• Hybridization of accelerated gradient descent method
• Hybrid Grid Adaptation in TAU
• On the convergence of a hybrid optimization algorithm
• scientific article
• A hybrid optimization strategy and its convergence analysis

zbMATH Keywords

computational complexityerror estimatesnumerical examplecontinuous-time Markov chainsweak approximationChernoff tau-leap methoddual-weighted estimationerror controlexit probabilityglobal error controlhybrid algorithmshybrid simulation methodsjump processesmodified next reaction methodmultilevel Monte Carlo methodstochastic reaction networksstochastic simulation algorithmstrong error estimationtau-leap

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) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Ordinary differential equations and systems with randomness (34F05) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Continuous-time Markov processes on discrete state spaces (60J27) Numerical solutions to stochastic differential and integral equations (65C30) Algorithms with automatic result verification (65G20)

Cites Work

• Computer methods for sampling from gamma, beta, Poisson and binomial distributions
• Multilevel Monte Carlo Path Simulation
• An analysis of variance test for normality (complete samples)
• A continuation multilevel Monte Carlo algorithm
• Multilevel hybrid Chernoff tau-leap
• Mathematical Models in Population Biology and Epidemiology
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Convergence analysis of multilevel Monte Carlo variance estimators and application for random obstacle problems
• Bounds on tail probabilities of discrete distributions
• Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
• Towards automatic global error control: Computable weak error expansion for the tau-leap method
• A multilevel approach to control variates
• Analysis of Explicit Tau-Leaping Schemes for Simulating Chemically Reacting Systems
• Weak Error Analysis of Numerical Methods for Stochastic Models of Population Processes
• Complexity of Multilevel Monte Carlo Tau-Leaping
• Analysis of Computer Networks
• Consistency and Stability of Tau-Leaping Schemes for Chemical Reaction Systems
• Title not available (Why is that?)

Cited In (20)

• Conditional Monte Carlo for Reaction Networks
• Multi-index Monte Carlo: when sparsity meets sampling
• Multilevel hybrid Chernoff tau-leap
• Goal-oriented adaptive finite element multilevel Monte Carlo with convergence rates
• An efficient forward–reverse expectation-maximization algorithm for statistical inference in stochastic reaction networks
• Optimization of mesh hierarchies in multilevel Monte Carlo samplers
• Non-nested Adaptive Timesteps in Multilevel Monte Carlo Computations
• Synchronization in Stochastic Biochemical Oscillators Subject to Common Multiplicative Extrinsic Noise
• Multilevel hybrid split-step implicit tau-leap
• Multiscale Simulation of Stochastic Reaction-Diffusion Networks
• Data-driven, variational model reduction of high-dimensional reaction networks
• SOME NEW BOUNDS AND APPROXIMATIONS ON TAIL PROBABILITIES OF THE POISSON AND OTHER DISCRETE DISTRIBUTIONS
• Estimation of Parameter Sensitivities for Stochastic Reaction Networks Using Tau-Leap Simulations
• Low variance couplings for stochastic models of intracellular processes with time-dependent rate functions
• Overview of the Hybrid RANS Code TAU
• Importance sampling for a robust and efficient multilevel Monte Carlo estimator for stochastic reaction networks
• A Multilevel Adaptive Reaction-splitting Simulation Method for Stochastic Reaction Networks
• Robustly simulating biochemical reaction kinetics using multi-level Monte Carlo approaches
• Slow-scale split-step tau-leap method for stiff stochastic chemical systems
• Central limit theorems for multilevel Monte Carlo methods

This page was built for publication: Multilevel hybrid Chernoff tau-leap

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