TITLE:
Inherent Numerical Instability in Computing Invariant Measures of Markov Chains
AUTHORS:
Hendrik Baumann, Thomas Hanschke
KEYWORDS:
Invariant Measures of Markov Chains, Inherent Numerical Instability of Linear Difference Equations, Generalized Continued Fractions, Convergence Criteria for Generalized Continued Fractions, Truncation Procedures for Infinite Matrices
JOURNAL NAME:
Applied Mathematics,
Vol.8 No.9,
September
30,
2017
ABSTRACT: Invariant measures of Markov chains in discrete or continuous time with a
countable set of states are characterized by its steady state recurrence relations.
Exemplarily, we consider transition matrices and Q-matrices with upper
bandwidth n and lower bandwidth 1 where the invariant measures satisfy
an (n + 1)-order linear difference equation. Markov chains of this type arise
from applications to queueing problems and population dynamics. It is the
purpose of this paper to point out that the forward use of this difference equation
is subject to some hitherto unobserved aspects. By means of the concept
of generalized continued fractions (GCFs), we prove that each invariant
measure is a dominated solution of the difference equation such that forward
computation becomes numerically unstable. Furthermore, the GCF-based approach
provides a decoupled recursion in which the phenomenon of numerical
instability does not appear. The procedure results in an iteration scheme
for successively computing approximants of the desired invariant measure
depending on some truncation level N. Increasing N leads to the desired solution.
A comparison study of forward computation and the GCF-based approach
is given for Q-matrices with upper bandwidth 1 and 2.