Computational complexity analysis for Monte Carlo approximations of classically scaled population processes

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

Research output: Working paper

Abstract

We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some function 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 then introduce a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that for this particular scaling a diffusion approximation offers little from a computational standpoint. Instead, we find that multilevel tau-leaping, which combines exact and tau-leaped samples, is the most promising method. In particular, multilevel tau-leaping provides an unbiased estimate and, up to a logarithm factor, is as efficient as a diffusion approximation combined with multilevel Monte Carlo. Computational experiments confirm the effectiveness of the multilevel tau-leaping approach.
LanguageEnglish
Number of pages23
Publication statusPublished - 4 Dec 2015

Fingerprint

Complexity Analysis
Computational Analysis
Computational complexity
Computational Complexity
Diffusion Approximation
Approximation
Scaling
Euler
Parameterization
Reaction kinetics
Exact Simulation
Chemical Kinetics
Monte Carlo Algorithm
Expected Value
Logarithm
Computational Experiments
Quantify
Discretization
Experiments
Estimate

Keywords

  • Monte Carlo
  • biochemical systems
  • multilevel tau-leaping

Cite this

@techreport{bb6fddb8b68f4073a582ddc7da310f6f,
title = "Computational complexity analysis for Monte Carlo approximations of classically scaled population processes",
abstract = "We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some function 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 then introduce a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that for this particular scaling a diffusion approximation offers little from a computational standpoint. Instead, we find that multilevel tau-leaping, which combines exact and tau-leaped samples, is the most promising method. In particular, multilevel tau-leaping provides an unbiased estimate and, up to a logarithm factor, is as efficient as a diffusion approximation combined with multilevel Monte Carlo. Computational experiments confirm the effectiveness of the multilevel tau-leaping approach.",
keywords = "Monte Carlo, biochemical systems, multilevel tau-leaping",
author = "Anderson, {David F.} and Higham, {Desmond J.} and Yu Sun",
year = "2015",
month = "12",
day = "4",
language = "English",
type = "WorkingPaper",

}

Computational complexity analysis for Monte Carlo approximations of classically scaled population processes. / Anderson, David F.; Higham, Desmond J.; Sun, Yu.

2015.

Research output: Working paper

TY - UNPB

T1 - Computational complexity analysis for Monte Carlo approximations of classically scaled population processes

AU - Anderson, David F.

AU - Higham, Desmond J.

AU - Sun, Yu

PY - 2015/12/4

Y1 - 2015/12/4

N2 - We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some function 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 then introduce a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that for this particular scaling a diffusion approximation offers little from a computational standpoint. Instead, we find that multilevel tau-leaping, which combines exact and tau-leaped samples, is the most promising method. In particular, multilevel tau-leaping provides an unbiased estimate and, up to a logarithm factor, is as efficient as a diffusion approximation combined with multilevel Monte Carlo. Computational experiments confirm the effectiveness of the multilevel tau-leaping approach.

AB - We analyze and compare the computational complexity of different simulation strategies for Monte Carlo in the setting of classically scaled population processes. This setting includes stochastically modeled biochemical systems. We consider the task of approximating the expected value of some function 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 then introduce a novel asymptotic regime where the required accuracy is a function of the model scaling parameter. Our new analysis shows that for this particular scaling a diffusion approximation offers little from a computational standpoint. Instead, we find that multilevel tau-leaping, which combines exact and tau-leaped samples, is the most promising method. In particular, multilevel tau-leaping provides an unbiased estimate and, up to a logarithm factor, is as efficient as a diffusion approximation combined with multilevel Monte Carlo. Computational experiments confirm the effectiveness of the multilevel tau-leaping approach.

KW - Monte Carlo

KW - biochemical systems

KW - multilevel tau-leaping

UR - http://arxiv.org/abs/1512.01588v1

M3 - Working paper

BT - Computational complexity analysis for Monte Carlo approximations of classically scaled population processes

ER -