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

DOI10.1137/18M1168261zbMATH Open1409.60113arXiv1801.09507MaRDI QIDQ4628404FDOQ4628404

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

Publication date: 13 March 2019

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1801.09507

Recommendations

• Numerically stable methods for the computation of exit rates in Markov chains
• Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming
• Approximating exit times of continuous Markov processes
• A multiple time interval finite state projection algorithm for the solution to the chemical master equation
• Bounds and approximations for continuous-time Markovian transition probabilities and large systems

zbMATH Keywords

first passage timescontinuous-time Markov chainsoccupation measureexit distributionexit timesfinite state projectionexit time finite state projection

Mathematics Subject Classification ID

Applications of continuous-time Markov processes on discrete state spaces (60J28) Numerical analysis or methods applied to Markov chains (65C40) Continuous-time Markov processes on discrete state spaces (60J27) Algorithms with automatic result verification (65G20)

Cites Work

• SUNDIALS
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• Title not available (Why is that?)
• A guide to first-passage processes
• Title not available (Why is that?)
• Stochastic processes in physics and chemistry.
• Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
• Continuous-time Markov chains. An applications-oriented approach
• First-passage phenomena and their applications
• The Randomization Technique as a Modeling Tool and Solution Procedure for Transient Markov Processes
• Title not available (Why is that?)
• A multiple time interval finite state projection algorithm for the solution to the chemical master equation
• Randomization Procedures in the Computation of Cumulative-Time Distributions over Discrete State Markov Processes
• Spectral approximation of solutions to the chemical master equation
• Solving chemical master equations by adaptive wavelet compression
• Explosion, implosion, and moments of passage times for continuous-time Markov chains: a semimartingale approach
• Title not available (Why is that?)
• Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming
• Exponentially slow transitions on a Markov chain: the frequency of Calcium Sparks
• Probabilistic Model Checking for Continuous-Time Markov Chains via Sequential Bayesian Inference
• On the Integro-Differential Equations of Purely Discontinuous Markoff Processes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation and inference methods for stochastic biochemical kinetics -- a tutorial review
• WKB theory of large deviations in stochastic populations
• Numerical Computation of Sojourn-Time Distributions in Queuing Networks
• Title not available (Why is that?)
• On three classical problems for Markov chains with continuous time parameters
• Solving the chemical master equation by a fast adaptive finite state projection based on the stochastic simulation algorithm
• Title not available (Why is that?)
• An improved finite state projection algorithm for the numerical solution of the chemical master equation with applications
• A Comment on the Book "Continuous-Time Markov Chains" by W.J. Anderson
• Exploiting fast-variables to understand population dynamics and evolution
• Accurate chemical master equation solution using multi-finite buffers
• Tackling large state spaces in performance modelling

Cited In (3)

• Finite-time boundedness and chaos-like dynamics of a class of Markovian jump linear systems
• Bounding mean first passage times in population continuous-time Markov chains
• Characteristic of exit moments and models of enlargement of states for finite Markov chains in terms of global memory functionals

Uses Software

• SUNDIALS

This page was built for publication: The exit time finite state projection scheme: bounding exit distributions and occupation measures of continuous-time Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628404)