Variance-reduced simulation of lattice discrete-time Markov chains with applications in reaction networks

P. A. Maginnis, M. West, G. E. Dullerud

Research output: Contribution to journalArticlepeer-review


We propose an algorithm to accelerate Monte Carlo simulation for a broad class of stochastic processes. Specifically, the class of countable-state, discrete-time Markov chains driven by additive Poisson noise, or lattice discrete-time Markov chains. In particular, this class includes simulation of reaction networks via the tau-leaping algorithm. To produce the speedup, we simulate pairs of fair-draw trajectories that are negatively correlated. Thus, when averaged, these paths produce an unbiased Monte Carlo estimator that has reduced variance and, therefore, reduced error. Numerical results for three example systems included in this work demonstrate two to four orders of magnitude reduction of mean-square error. The numerical examples were chosen to illustrate different application areas and levels of system complexity. The areas are: gene expression (affine state-dependent rates), aerosol particle coagulation with emission and human immunodeficiency virus infection (both with nonlinear state-dependent rates). Our algorithm views the system dynamics as a “black-box”, i.e., we only require control of pseudorandom number generator inputs. As a result, typical codes can be retrofitted with our algorithm using only minor changes. We prove several analytical results. Among these, we characterize the relationship of covariances between paths in the general nonlinear state-dependent intensity rates case, and we prove variance reduction of mean estimators in the special case of affine intensity rates.

Original languageEnglish (US)
Pages (from-to)400-414
Number of pages15
JournalJournal of Computational Physics
StatePublished - Oct 1 2016


  • Antithetic sampling
  • Monte Carlo
  • Reaction networks
  • Stochastic simulation
  • Tau-leaping
  • Variance reduction

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Variance-reduced simulation of lattice discrete-time Markov chains with applications in reaction networks'. Together they form a unique fingerprint.

Cite this