David F. Anderson

David F. Anderson, Desmond J. Higham

We show how to extend a recently proposed multi-level Monte Carlo approach to the continuous time Markov chain setting, thereby greatly lowering the computational complexity needed to compute expected values of functions of the state of the system to a specified accuracy. The extension is non-trivial, exploiting a coupling of the requisite processes that is easy to simulate while providing a small variance for the estimator. Further, and in a stark departure from other implementations of multi-level Monte Carlo, we show how to produce an unbiased estimator that is significantly less computationally expensive than the usual unbiased estimator arising from exact algorithms in conjunction with crude Monte Carlo. We thereby dramatically improve, in a quantifiable manner, the basic computational complexity of current approaches that have many names and variants across the scientific literature, including the Bortz-Kalos-Lebowitz algorithm, discrete event simulation, dynamic Monte Carlo, kinetic Monte Carlo, the n-fold way, the next reaction method,the residence-time algorithm, the stochastic simulation algorithm, Gillespie's algorithm, and tau-leaping. The new algorithm applies generically, but we also give an example where the coupling idea alone, even without a multi-level discretization, can be used to improve efficiency by exploiting system structure. Stochastically modeled chemical reaction networks provide a very important application for this work. Hence, we use this context for our notation, terminology, natural scalings, and computational examples.

David F. Anderson, Desmond J. Higham, Yu Sun

Tau-leaping is a popular discretization method for generating approximate paths of continuous time, discrete space, Markov chains, notably for biochemical reaction systems. To compute expected values in this context, an appropriate multilevel Monte Carlo form of tau-leaping has been shown to improve efficiency dramatically. In this work we derive new analytic results concerning the computational complexity of multilevel Monte Carlo tau-leaping that are significantly sharper than previous ones. We avoid taking asymptotic limits, and focus on a practical setting where the system size is large enough for many events to take place along a path, so that exact simulation of paths is expensive, making tau-leaping an attractive option. We use a general scaling of the system components that allows for the reaction rate constants and the abundances of species to vary over several orders of magnitude, and we exploit the random time change representation developed by Kurtz. The key feature of the analysis that allows for the sharper bounds is that when comparing relevant pairs of processes we analyze the variance of their difference directly rather than bounding via the second moment. Use of the second moment is natural in the setting of a diffusion equation, where multilevel was first developed and where strong convergence results for numerical methods are readily available, but is not optimal for the Poisson-driven jump systems that we consider here. We also present computational results that illustrate the new analysis.

David F. Anderson, Desmond J. Higham, Yu Sun

We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This allows a range of widely used competing strategies to be judged systematically. Our setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some path functional of the state of the system at a fixed time point. We study the use of standard Monte Carlo when samples are produced by exact simulation and by approximation with tau-leaping or an Euler-Maruyama discretization of a diffusion approximation. Appropriate modifications of recently proposed multilevel Monte Carlo algorithms are also studied for the tau-leaping and Euler-Maruyama approaches. In order to quantify computational complexity in a tractable yet meaningful manner, we consider a parameterization that, in the mass action chemical kinetics setting, corresponds to the classical system size scaling. We base the analysis on a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that, under the specific assumptions made in the manuscript, if the bias inherent in the diffusion approximation is smaller than the required accuracy, then multilevel Monte Carlo for the diffusion approximation is most efficient, besting multilevel Monte Carlo with tau-leaping by a factor of a logarithm of the scaling parameter. However, if the bias of the diffusion model is greater than the error tolerance, or if the bias can not be bounded analytically, multilevel versions of tau-leaping are often the optimal choice.

David F. Anderson

We present an efficient finite difference method for the computation of parameter sensitivities that is applicable to a wide class of continuous time Markov chain models. The estimator for the method is constructed by coupling the perturbed and nominal processes in a natural manner, and the analysis proceeds by utilizing a martingale representation for the coupled processes. The variance of the resulting estimator is shown to be an order of magnitude lower due to the coupling. We conclude that the proposed method produces an estimator with a lower variance than other methods, including the use of Common Random Numbers, in most situations. Often the variance reduction is substantial. The method is no harder to implement than any standard continuous time Markov chain algorithm, such as "Gillespie's algorithm." The motivating class of models, and the source of our examples, are the stochastic chemical kinetic models commonly used in the biosciences, though other natural application areas include population processes and queuing networks.

David F. Anderson, Masanori Koyama

The simplest, and most common, stochastic model for population processes, including those from biochemistry and cell biology, are continuous time Markov chains. Simulation of such models is often relatively straightforward as there are easily implementable methods for the generation of exact sample paths. However, when using ensemble averages to approximate expected values, the computational complexity can become prohibitive as the number of computations per path scales linearly with the number of jumps of the process. When such methods become computationally intractable, approximate methods, which introduce a bias, can become advantageous. In this paper, we provide a general framework for understanding the weak error, or bias, induced by different numerical approximation techniques in the current setting. The analysis takes into account both the natural scalings within a given system and the step-size of the numerical method. Examples are provided to demonstrate the main analytical results as well as the reduction in computational complexity achieved by the approximate methods.

Elizabeth Skubak Wolf, David F. Anderson

We present an efficient finite difference method for the approximation of second derivatives, with respect to system parameters, of expectations for a class of discrete stochastic chemical reaction networks. The method uses a coupling of the perturbed processes that yields a much lower variance than existing methods, thereby drastically lowering the computational complexity required to solve a given problem. Further, the method is simple to implement and will also prove useful in any setting in which continuous time Markov chains are used to model dynamics, such as population processes. We expect the new method to be useful in the context of optimization algorithms that require knowledge of the Hessian.

David F. Anderson, Masanori Koyama

This paper is concerned with elucidating a relationship between two common coupling methods for the continuous time Markov chain models utilized in the cell biology literature. The couplings considered here are primarily used in a computational framework by providing reductions in variance for different Monte Carlo estimators, thereby allowing for significantly more accurate results for a fixed amount of computational time. Common applications of the couplings include the estimation of parametric sensitivities via finite difference methods and the estimation of expectations via multi-level Monte Carlo algorithms. While a number of coupling strategies have been proposed for the models considered here, and a number of articles have experimentally compared the different strategies, to date there has been no mathematical analysis describing the connections between them. Such analyses are critical in order to determine the best use for each. In the current paper, we show a connection between the common reaction path (CRP) method and the split coupling (SC) method, which is termed coupled finite differences (CFD) in the parametric sensitivities literature. In particular, we show that the two couplings are both limits of a third coupling strategy we call the "local-CRP" coupling, with the split coupling method arising as a key parameter goes to infinity, and the common reaction path coupling arising as the same parameter goes to zero. The analysis helps explain why the split coupling method often provides a lower variance than does the common reaction path method, a fact previously shown experimentally.

David F. Anderson, Chaojie Yuan

A number of coupling strategies are presented for stochastically modeled biochemical processes with time-dependent parameters. In particular, the stacked coupling is introduced and is shown via a number of examples to provide an exceptionally low variance between the generated paths. This coupling will be useful in the numerical computation of parametric sensitivities and the fast estimation of expectations via multilevel Monte Carlo methods. We provide the requisite estimators in both cases.

David F. Anderson, Badal Joshi, Abhishek Deshpande

This paper is concerned with the utilization of deterministically modeled chemical reaction networks for the implementation of (feed-forward) neural networks. We develop a general mathematical framework and prove that the ordinary differential equations (ODEs) associated with certain reaction network implementations of neural networks have desirable properties including (i) existence of unique positive fixed points that are smooth in the parameters of the model (necessary for gradient descent), and (ii) fast convergence to the fixed point regardless of initial condition (necessary for efficient implementation). We do so by first making a connection between neural networks and fixed points for systems of ODEs, and then by constructing reaction networks with the correct associated set of ODEs. We demonstrate the theory by constructing a reaction network that implements a neural network with a smoothed ReLU activation function, though we also demonstrate how to generalize the construction to allow for other activation functions (each with the desirable properties listed previously). As there are multiple types of "networks" utilized in this paper, we also give a careful introduction to both reaction networks and neural networks, in order to disambiguate the overlapping vocabulary in the two settings and to clearly highlight the role of each network's properties.

David F. Anderson, Desmond J. Higham, Yu Sun

We consider the problem of numerically estimating expectations of solutions to stochastic differential equations driven by Brownian motions in the commonly occurring small noise regime. We consider (i) standard Monte Carlo methods combined with numerical discretization algorithms tailored to the small noise setting, and (ii) a multilevel Monte Carlo method combined with a standard Euler-Maruyama implementation. Under the assumptions we make on the underlying model, the multilevel method combined with Euler-Maruyama is often found to be the most efficient option. Moreover, under a wide range of scalings the multilevel method is found to give the same asymptotic complexity that would arise in the idealized case where we have access to exact samples of the required distribution at a cost of $O(1)$ per sample. A key step in our analysis is to analyze the variance between two coupled paths directly, as opposed to their $L^2$ distance. Careful simulations are provided to illustrate the asymptotic results.

Elizabeth Skubak Wolf, David F. Anderson

Stochastic models are often used to help understand the behavior of intracellular biochemical processes. The most common such models are continuous time Markov chains (CTMCs). Parametric sensitivities, which are derivatives of expectations of model output quantities with respect to model parameters, are useful in this setting for a variety of applications. In this paper, we introduce a class of hybrid pathwise differentiation methods for the numerical estimation of parametric sensitivities. The new hybrid methods combine elements from the three main classes of procedures for sensitivity estimation, and have a number of desirable qualities. First, the new methods are unbiased for a broad class of problems. Second, the methods are applicable to nearly any physically relevant biochemical CTMC model. Third, and as we demonstrate on several numerical examples, the new methods are quite efficient, particularly if one wishes to estimate the full gradient of parametric sensitivities. The methods are rather intuitive and utilize the multilevel Monte Carlo philosophy of splitting an expectation into separate parts and handling each in an efficient manner.

David F. Anderson, Arnab Ganguly, Thomas G. Kurtz

We perform an error analysis for numerical approximation methods of continuous time Markov chain models commonly found in the chemistry and biochemistry literature. The motivation for the analysis is to be able to compare the accuracy of different approximation methods and, specifically, Euler tau-leaping and midpoint tau-leaping. We perform our analysis under a scaling in which the size of the time discretization is inversely proportional to some (bounded) power of the norm of the state of the system. We argue that this is a more appropriate scaling than that found in previous error analyses in which the size of the time discretization goes to zero independent of the rest of the model. Under the present scaling, we show that midpoint tau-leaping achieves a higher order of accuracy, in both a weak and a strong sense, than Euler tau-leaping; a result that is in contrast to previous analyses. We present examples that demonstrate our findings.

David F. Anderson, Jonathan C. Mattingly

We present a numerical method for the approximation of solutions for the class of stochastic differential equations driven by Brownian motions which induce stochastic variation in fixed directions. This class of equations arises naturally in the study of population processes and chemical reaction kinetics. We show that the method constructs paths that are second order accurate in the weak sense. The method is simpler than many second order methods in that it neither requires the construction of iterated Ito integrals nor the evaluation of any derivatives. The method consists of two steps. In the first an explicit Euler step is used to take a fractional step. This fractional point is then combined with the initial point to obtain a higher order, trapezoidal like, approximation. The higher order of accuracy stems from the fact that both the drift and the quadratic variation of the underlying SDE are approximated to second order.