Abstract

Co-authors: David F. Anderson (University of Wisconsin-Madison), Yu Sun (University of Wisconsin-Madison)

I will analyze and compare the computational complexity of different simulation strategies for continuous time Markov chains. I consider the task of approximating the expected value of some functional of the state of the system over a compact time interval. This task is a bottleneck in many large-scale computations arising in biochemical kinetics and cell biology. In this context, the terms 'Gillespie's method', 'The Stochastic Simulation Algorithm' and 'The Next Reaction Method' are widely used to describe exact simulation methods. For example, Google Scholar records more than 6,000 citations to Gillespie's seminal 1977 paper. I will look at 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. In particular, I will point out some possible pitfalls when computational complexity is analysed. Appropriate modifications o f recently proposed multilevel Monte Carlo algorithms will then be studied for the tau-leaping and Euler-Maruyama approaches. I will pay particular attention to a parameterization of the problem that, in the mass action chemical kinetics setting, corresponds to the classical system size scaling.

Related Links

• http://personal.strath.ac.uk/d.j.higham/