In biochemical systems, stochastic e↵ects can be caused by the presence of small numbers of certain reactant molecules. In this setting, discrete statespace and stochastic simulation approaches were proved to be more relevant than continuous statespace and deterministic ones. These stochastic models constitute the theory of stochastic reaction networks (SRNs). Furthermore, in some cases, the dynamics of fast and slow time scales can be well separated and this is characterized by what is called sti↵ness. For such problems, the existing discrete spacestate stochastic path simulation methods, such as the stochastic simulation algorithm (SSA) and the explicit tauleap method, can be very slow. Therefore, implicit tauleap approxima tions were developed to improve the numerical stability and provide more e cient simulation algorithms for these systems. One of the interesting tasks for SRNs is to approximate the expected values of some observables of the process at a certain fixed time T. This is can be achieved using Monte Carlo (MC) techniques. However, in a recent work, Anderson and Higham in 2013, proposed a more computationally e cient method which combines multilevel Monte Carlo (MLMC) technique with explicit tauleap schemes.
In this MSc thesis, we propose new fast stochastic algorithm, particularly designed
5
to address sti↵ systems, for approximating the expected values of some observables of
SRNs. In fact, we take advantage of the idea of MLMC techniques and driftimplicit tauleap approximation to construct a driftimplicit MLMC tauleap estimator. In addition to accurately estimating the expected values of a given observable of SRNs at a final time T , our proposed estimator ensures the numerical stability with a lower cost than the MLMC explicit tauleap algorithm, for systems including simultane ously fast and slow species. The key contribution of our work is the coupling of two driftimplicit tauleap paths, which is the basic brick for constructing our proposed driftimplicit MLMC tauleap estimator. As an example of sti↵ problem, we used the decayingdimerizing reaction as a test example to show the advantage of our driftimplicit method over the explicit one. Through our numerical experiments, we checked the convergence properties of our coupling algorithm and showed that our proposed estimator is outperforming the explicit MLMC estimator about three times in terms of computational work. We also illustrated in a second example how our driftimplicit MLMC tauleap estimator can be forty times faster than the explicit MLMC.
Date of Award  May 12 2015 

Original language  English (US) 

Awarding Institution   Computer, Electrical and Mathematical Science and Engineering


Supervisor  Raul Tempone (Supervisor) 

 stochastic reaction networks
 Multilevel Monte Carlo
 driftimplicit tauleap