I will analyze and compare the computational complexity of different simulati on strategies for continuous time Markov chains. I consider the task of approximating the expected v alue of some functional of the state of the system over a compact time interval. This task is a bott leneck in many large-scale computations arising in biochemical kinetics and cell biology. In this co ntext\, the terms '\;Gillespie'\;s method 9\;\, '\;The Stochastic Simulation Algorithm 9\; and '\;The Next Reaction Method'\; are w idely used to describe exact simulation methods. F or example\, Google Scholar records more than 6\,0 00 citations to Gillespie'\;s seminal 1977 pape r. 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-Maru yama discretization of a diffusion approximation. In particular\, I will point out some possible pit falls when computational complexity is analysed. A ppropriate modifications o f recently proposed mul tilevel Monte Carlo algorithms will then be studie d for the tau-leaping and Euler-Maruyama approache s. I will pay particular attention to a parameteri zation of the problem that\, in the mass action ch emical kinetics setting\, corresponds to the class ical system size scaling.

Related Links LOCATION:Seminar Room 1\, Newton Institute CONTACT:info@newton.ac.uk END:VEVENT END:VCALENDAR