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 tauleaping or an EulerMaruyama discretization of a diffusion approximation. Appropriate modifications of recently proposed multilevel Monte Carlo algorithms are also studied for the tauleaping and EulerMaruyama 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 tauleaping 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 tauleaping are often the optimal choice.
Original language  English 

Pages (fromto)  12061226 
Number of pages  21 
Journal  Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal 
Volume  16 
Issue number  3 
DOIs  
Publication status  Published  7 Aug 2018 
Keywords
 computational complexity
 Monte Carlo
 tauleaping
Fingerprint Dive into the research topics of 'Computational complexity analysis for Monte Carlo approximations of classically scaled population processes'. Together they form a unique fingerprint.
Profiles

Desmond Higham
 School of Mathematics  Professor of Numerical Analysis
Person: Academic: Research Active (Teaching)