skip to content

Multi-level Monte Carlo: adaptive algorithms and distribution estimation

Presented by: 
Ruth Baker
Thursday 21st January 2016 - 13:30 to 14:15
INI Seminar Room 1
Co-authors: Christopher Lester (University of Oxford), Christian Yates (University of Bath), Daniel Wilson (University of Oxford)

Discrete-state, continuous-time Markov models are widely used to model biochemical reaction networks. Their complexity generally precludes analytic solution, and so we rely on Monte Carlo simulation to estimate system statistics of interest. 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 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 employing a variance reduction approach that involves generating sample paths with different accuracies 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 a relatively small number of paired paths are required to calculate each correction term.

This talk will outline two main extensions to the multi-level method. First, I will discuss how to extend the multi-level method to use an adaptive time-stepping approach. This enables use of the method to explore systems where the reaction activity changes significantly over the timescale of interest. Second, I will discuss how to harness the multi-level approach to estimate probability distributions of species of interest, giving examples of the utility of this approach by applying it to systems that exhibit bistable behaviour.  
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons