| In this dissertation, we study multilevel Monte Carlo simulation methods and applica- tions to different types of stochastic dynamical models. This dissertation focuses on three selected topics. Firstly, tau-leaping is a popular discretization method for gener- ating approximate paths of continuous time, discrete space Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appro- priate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. The contribution for this topic is deriving new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are signifi- cantly sharper than previous ones. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the vari- ance of their difference directly rather than bounding via the second moment. Secondly, we consider the problem of numerically estimating expectations of solutions to stochas- tic differential equations driven by Brownian motions in the small noise regime. Our complexity analysis shows multilevel Monte Carlo can improve on the complexity of standard Monte Carlo by a factor ?, where ? is the desired accuracy. The take-home message is that, under reasonable assumptions, a basic Euler-Maruyama discretization leads to optimal asymptotic computational complexity when used in a multilevel setting. Thirdly, we analyze and compare the computational complexity of different simulation strategies for classically scaled continuous time Markov chains. We provide numerical examples demonstrating our main conclusions. The three topics have appeared in a series of three papers published or under review. |
