Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Research , Report 01 Jan 2021Embargo end date: 01 Sep 2019 United Kingdom English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Review, volume 63, pages 3-64 (issn: 0036-1445, eissn: 1095-7200,

Copyright policy )Funded by:UKRI | EPSRC Centre for Mathemat..., EC | COSY-BIO, UKRI | Doctoral Training Grant +1 projects

Authors: Kuntz, Juan; Thomas, Philipp; Stan, Guy-Bart; Barahona, Mauricio;

doi: 10.1137/19m1289625 , 10.48550/arxiv.1909.05794

arXiv: 1909.05794

handle: 10044/1/81806

Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations

- Summary
- Subjects
- Metrics

Abstract

Computing the stationary distributions of a continuous-time Markov chain (CTMC) involves solving a set of linear equations. In most cases of interest, the number of equations is infinite or too large, and the equations cannot be solved analytically or numerically. Several approximation schemes overcome this issue by truncating the state space to a manageable size. In this review, we first give a comprehensive theoretical account of the stationary distributions and their relation to the long-term behaviour of CTMCs that is readily accessible to non-experts and free of irreducibility assumptions made in standard texts. We then review truncation-based approximation schemes for CTMCs with infinite state spaces paying particular attention to the schemes' convergence and the errors they introduce, and we illustrate their performance with an example of a stochastic reaction network of relevance in biology and chemistry. We conclude by discussing computational trade-offs associated with error control and several open questions.

Country

United Kingdom

Related Organizations

University of Warwick
United Kingdom
Imperial College London
United Kingdom

Keywords

90C05, stochastic reaction networks, q-bio.PE, Molecular Networks (q-bio.MN), Numerical & Computational Mathematics, FOS: Physical sciences, math.PR, ergodic distributions, 510, 90C90 (Secondary), chemical master equation, 0102 Applied Mathematics, Linear programming, Computational methods in Markov chains, FOS: Mathematics, 60J22, Quantitative Biology - Molecular Networks, 60J27 (Primary), cond-mat.stat-mech, Quantitative Biology - Populations and Evolution, Mathematics - Optimization and Control, Condensed Matter - Statistical Mechanics, boundedness in probability, math.OC, censored chain, Statistical Mechanics (cond-mat.stat-mech), Probability (math.PR), reducible Markov chains, Populations and Evolution (q-bio.PE), q-bio.MN, linear programming, error bounds, level-dependent quasi-birth-death processes, finite state projection algorithm, 0906 Electrical and Electronic Engineering, Applications of mathematical programming, Optimization and Control (math.OC), FOS: Biological sciences, Foster-Lyapunov criteria, 65C40, 60J27 (Primary), 60J22, 65C40, 90C05, 90C90 (Secondary), Numerical analysis or methods applied to Markov chains, optimal approximations, truncation-and-augmentation scheme, Mathematics - Probability, Continuous-time Markov processes on discrete state spaces

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	24
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%