TY - JOUR
T1 - Hybrid chernoff tau-leap
AU - Moraes, Alvaro
AU - Tempone, Raul
AU - Vilanova, Pedro
PY - 2014
Y1 - 2014
N2 - Markovian pure jump processes model a wide range of phenomena, including chemical reactions at the molecular level, dynamics of wireless communication networks, and the spread of epidemic diseases in small populations. There exist algorithms such as Gillespie's stochastic simulation algorithm (SSA) and Anderson's modified next reaction method (MNRM) that simulate a single path with the exact distribution of the process, but this can be time consuming when many reactions take place during a short time interval. Gillespie's approximated tau-leap method, on the other hand, can be used to reduce computational time, but it may lead to nonphysical values due to a positive one-step exit probability, and it also introduces a time discretization error. Here, we present a novel hybrid algorithm for simulating individual paths which adaptively switches between the SSA and the tau-leap method. The switching strategy is based on a comparison of the expected interarrival time of the SSA and an adaptive time step derived from a Chernoff-type bound for the one-step exit probability. Because this bound is nonasymptotic, we do not need to make any distributional approximation for the tau-leap increments. This hybrid method allows us (i) to control the global exit probability of any simulated path and (ii) to obtain accurate and computable estimates of the expected value of any smooth observable of the process with minimal computational work. We present numerical examples that illustrate the performance of the proposed method.
AB - Markovian pure jump processes model a wide range of phenomena, including chemical reactions at the molecular level, dynamics of wireless communication networks, and the spread of epidemic diseases in small populations. There exist algorithms such as Gillespie's stochastic simulation algorithm (SSA) and Anderson's modified next reaction method (MNRM) that simulate a single path with the exact distribution of the process, but this can be time consuming when many reactions take place during a short time interval. Gillespie's approximated tau-leap method, on the other hand, can be used to reduce computational time, but it may lead to nonphysical values due to a positive one-step exit probability, and it also introduces a time discretization error. Here, we present a novel hybrid algorithm for simulating individual paths which adaptively switches between the SSA and the tau-leap method. The switching strategy is based on a comparison of the expected interarrival time of the SSA and an adaptive time step derived from a Chernoff-type bound for the one-step exit probability. Because this bound is nonasymptotic, we do not need to make any distributional approximation for the tau-leap increments. This hybrid method allows us (i) to control the global exit probability of any simulated path and (ii) to obtain accurate and computable estimates of the expected value of any smooth observable of the process with minimal computational work. We present numerical examples that illustrate the performance of the proposed method.
KW - Error control
KW - Error estimates
KW - Exit probability
KW - Hybrid algorithms
KW - Tau-leap
KW - Weak approximation
UR - http://www.scopus.com/inward/record.url?scp=84904014999&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904014999&partnerID=8YFLogxK
U2 - 10.1137/130925657
DO - 10.1137/130925657
M3 - Article
AN - SCOPUS:84904014999
SN - 1540-3459
VL - 12
SP - 581
EP - 615
JO - Multiscale Modeling and Simulation
JF - Multiscale Modeling and Simulation
IS - 2
ER -