The exit time finite state projection scheme: bounding exit distributions and occupation measures of continuous-time Markov chains

File Description SizeFormat 
Kuntz_ETFSP.pdfAccepted version3.31 MBAdobe PDFView/Open
Title: The exit time finite state projection scheme: bounding exit distributions and occupation measures of continuous-time Markov chains
Authors: Kuntz, J
Thomas, P
Stan, G-B
Barahona, M
Item Type: Journal Article
Abstract: We introduce the exit time finite state projection (ETFSP) scheme, a truncation- based method that yields approximations to the exit distribution and occupation measure associated with the time of exit from a domain (i.e., the time of first passage to the complement of the domain) of time-homogeneous continuous-time Markov chains. We prove that: (i) the computed approximations bound the measures from below; (ii) the total variation distances between the approximations and the measures decrease monotonically as states are added to the truncation; and (iii) the scheme converges, in the sense that, as the truncation tends to the entire state space, the total variation distances tend to zero. Furthermore, we give a computable bound on the total variation distance between the exit distribution and its approximation, and we delineate the cases in which the bound is sharp. We also revisit the related finite state projection scheme and give a comprehensive account of its theoretical properties. We demonstrate the use of the ETFSP scheme by applying it to two biological examples: the computation of the first passage time associated with the expression of a gene, and the fixation times of competing species subject to demographic noise.
Issue Date: 12-Mar-2019
Date of Acceptance: 23-Jan-2019
URI: http://hdl.handle.net/10044/1/66083
DOI: https://dx.doi.org/10.1137/18M1168261
ISSN: 1064-8275
Publisher: Society for Industrial and Applied Mathematics
Start Page: A748
End Page: A769
Journal / Book Title: SIAM Journal on Scientific Computing
Volume: 41
Issue: 2
Copyright Statement: © 2019 Society for Industrial and Applied Mathematics
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/I017267/1
EP/N014529/1
Keywords: Science & Technology
Physical Sciences
Mathematics, Applied
Mathematics
exit times
first passage times
continuous-time Markov chains
exit time finite state projection
finite state projection
exit distribution
occupation measure
CHEMICAL MASTER EQUATION
COMPUTATION
MOMENTS
NOISE
math.PR
math.PR
cond-mat.stat-mech
math.OC
q-bio.MN
q-bio.PE
60J27, 60J28, 65C40, 65G20
math.PR
math.PR
cond-mat.stat-mech
math.OC
q-bio.MN
q-bio.PE
60J27, 60J28, 65C40, 65G20
Numerical & Computational Mathematics
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
0802 Computation Theory and Mathematics
Publication Status: Published
Online Publication Date: 2019-03-12
Appears in Collections:Faculty of Engineering
Bioengineering
Mathematics
Applied Mathematics and Mathematical Physics
Faculty of Natural Sciences



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons