Inherent Numerical Instability in Computing Invariant Measures of Markov Chains

• 作者: Hendrik Baumann Thomas Hanschke
• 来源期刊: 应用数学(英文)
• 学科: 数学
• 关键词: 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
• 年，卷（期）: 2017,（9）
• 页码范围: 1367-1385
• 页数: 19页
• 分类号: O1

摘要

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.