Abstract
Tauleaping is a popular discretization method for generating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tauleaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tauleaping that are significantly sharper than previous ones. We avoid taking asymptotic limits and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tauleaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary overseveral orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel Monte Carlo was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poissondriven jump systems that we considerhere. We also present computational results that illustrate the new analysis.
Original language  English 

Pages (fromto)  31063127 
Number of pages  22 
Journal  Siam journal on numerical analysis 
Volume  52 
Issue number  6 
DOIs  
Publication status  Published  18 Dec 2014 
Keywords
 computational complexity
 coupling
 continuous time Markov chain
 tauleaping
 variance
 multilevel Monte Carlo
Fingerprint
Dive into the research topics of 'Complexity of multilevel Monte Carlo tauLeaping'. Together they form a unique fingerprint.Profiles

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