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 the computational 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. 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. Appropriate modifications of recently proposed multi-level Monte Carlo algorithms will also 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.
This is joint work with David Anderson and Yu Sun at Wisconsin.