University of Cambridge > > Isaac Newton Institute Seminar Series > Multi-level Monte Carlo: adaptive algorithms and distribution estimation

Multi-level Monte Carlo: adaptive algorithms and distribution estimation

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact INI IT.

SDBW01 - Opening workshop

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.  

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity