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

DOI10.1137/18M1168261MaRDI QIDQ4628404zbMATH OpenFDO

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)

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

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)

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.

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

Cites work

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

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

Describes a project that uses

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)