Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
Anderson, David and Higham, Desmond (2012) Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics. Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 10 (1). pp. 146179. ISSN 15403459

PDF
8509181.pdf Download (463kB)  Preview 
Abstract
We show how to extend a recently proposed multilevel Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is nontrivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multilevel Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the BortzKalosLebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the nfold way, the next reaction method,the residencetime algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tauleaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multilevel discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.
Item type:  Article 

ID code:  36279 
Keywords:  markov chain, Monte Carlo Markov chains, biochemical kinetics, reaction network, computational complexity, Gillespie, random time change, tauleaping, Probabilities. Mathematical statistics, Physics and Astronomy(all), Modelling and Simulation, Chemistry(all), Ecological Modelling, Computer Science Applications 
Subjects:  Science > Mathematics > Probabilities. Mathematical statistics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Pure Administrator 
Date Deposited:  01 Dec 2011 17:16 
Last modified:  28 Apr 2016 19:37 
URI:  http://strathprints.strath.ac.uk/id/eprint/36279 