event
Monday 24 Nov 2014: SDAC seminar
Ruth Baker - University of Oxford
H103 15:00-16:00
Discrete-state, continuous-time Markov models are widely used in the modelling of biochemical reaction networks. Their complexity generally precludes analytic solution, and so we rely on Monte Carlo simulation to estimate system statistics of interest. Perhaps the most widely used method is the Gillespie algorithm. This algorithm is exact but computationally complex. As such, approximate stochastic simulation algorithms such as the tau-leap algorithm are often used. Sample paths are generated by taking leaps of length tau through time and using an approximate method to generate reactions within leaps. However, tau must be held relatively small to avoid significant estimator bias and this significantly impacts on potential computational advantages of the method.
The multi-level method of Anderson and Higham tackles this problem by cleverly generating a suite of sample paths with different accuracy in order to estimate statistics. A base estimator is computed using many (cheap) paths at low accuracy. The bias inherent in this estimator is then reduced using a number of correction estimators. Each correction term is estimated using a collection of (increasingly expensive) paired sample paths where one path of each pair is generated at a higher accuracy compared to the other. By sharing randomness between these paired sample paths only a relatively small number of pairs are required to calculate each correction term.
In the original multi-level method, paths are simulated using the tau-leap technique with a fixed value of tau. This approach can result in poor performance where the reaction activity of a system changes substantially over the timescale of interest. By introducing a novel, adaptive time-stepping approach we extend the applicability of the multi-level method to such cases. In our algorithm, tau is chosen according to the stochastic behaviour of each sample path. We present an implementation of our adaptive time-stepping multi-level method that, despite its simplicity, performs well across a wide range of sample problems.
