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.
KeywordsInvariant Measures of Markov ChainsInherent Numerical Instability of Linear Difference EquationsGeneralized Continued FractionsConvergence Criteria for Generalized Continued FractionsTruncation Procedures for Infinite Matrices
Karlin, S. and Taylor, H.M. (1981) A Second Course in Stochastic Processes. Academic Press, New York.
Miller, K.S. (1968) Linear Difference Equations. Benjamin, New York.
Cash, J.R. (1980) A Note on the Numerical Solution of Linear Recurrence Relations. Numerische Mathematik, 34, 371-386. https://doi.org/10.1007/BF01403675
Gautschi, W. (1967) Computational Aspects of Three-Term Recurrence Relations. SIAM Review, 9, 24-82. https://doi.org/10.1137/1009002
Gautschi, W. (1972) Zur Numerik rekurrenter Relationen. Computing, 9, 107-126. https://doi.org/10.1007/BF02236961
Lozier, S.W. (1980) Numerical Solution of Linear Difference Equations. Report NBSIR 80-1976, National Bureau of Standards, US Dept. of Commerce, Washington DC. https://doi.org/10.6028/NBS.IR.80-1976
Mattheij, R.M.M. (1980) Characterization of Dominant and Dominated Solutions of Linear Recursions. Numerische Mathematik, 35, 421-442. https://doi.org/10.1007/BF01399009
Wimp, J. (1984) Computation with Recurrence Relations. Pitman, Boston.
Hanschke, T. (1992) Markov Chains and Generalized Continued Fractions. Journal of Applied Probability, 29, 838-849. https://doi.org/10.1017/S0021900200043710
Jacobi, C.G.J. (1868) Allgemeine Theorie der kettenbruchahnlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird. [General Theory of Continued-Fraction-Type Algorithms in Which Every Number Is Generated by the Three Preceding Ones.] Journal für die reine und angewandte Mathematik, 69, 29-64. https://doi.org/10.1515/crll.1868.69.29
Perron, O. (1907) Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus. [Fundamentals for a Theory of Jacobi’s Continued-Fraction Algorithm.] Mathematische Annalen, 64, 1-76. https://doi.org/10.1007/BF01449880
Perron, O. (1907) über die Konvergenz der Jacobi-Kettenalgorithmen mit komplexen Elementen. [On the Convergence of Jacobi’s Continued-Fraction Algorithms with Complex Elements.] Sitzungsber. Akad. München, 37, 401-482.
Van der Cruyssen, P. (1979) Linear Difference Equations and Generalized Continued Fractions. Computing, 22, 269-278. https://doi.org/10.1007/BF02243567
Perron, O. (1909) über lineare Differenzen-und Differentialgleichungen. [On Linear Difference and Differential Equations.] Mathematische Annalen, 66, 446-487. https://doi.org/10.1007/BF01450044
Hanschke, T. (1991) über die Minimallosung der Poincare-Perronschen Differenzengleichung. [On the Minimal Solution of the Poincaré-Perron Difference Equation.] Monatshefte für Mathematik, 112, 281-295. https://doi.org/10.1007/BF01351769
Hanschke, T. (1998) Ein verallgemeinerter Jacobi-Perron-Algorithmus zur Reduktion linearer Differenzengleichungssysteme. [A Generalized Jacobi-Perron Algorithm for the Reduction of Systems of Linear Difference Equations.] Monatshefte für Mathematik, 126, 287-311. https://doi.org/10.1007/BF01299054
Levrie, P. and Bultheel, A. (1996) Matrix Continued Fractions Related to First-Order Linear Recurrence Systems. Electronic Transactions on Numerical Analysis, 4, 46-63.
Levrie, P. (1986) Pringsheim’s Theorem for Generalized Continued Fractions. Journal of Computational and Applied Mathematics, 14, 439-445.
de Bruin, M.G. (1978) Convergence of Generalized C-Fractions. Journal of Approximation Theory, 24, 177-207. https://doi.org/10.1016/0021-9045(78)90023-0
Seneta, E. (1967) Finite Approximations to Infinite Non-Negative Matrices. Proceedings of the Cambridge Philosophical Society, 63, 983-992. https://doi.org/10.1017/S0305004100042006
Seneta, E. (1968) Finite Approximations to Infinite Non-Negative Matrices II. Proceedings of the Cambridge Philosophical Society, 64, 465-470. https://doi.org/10.1017/S0305004100043061
Seneta, E. (1980) Computing the Stationary Distribution for Infinite Markov Chains. Linear Algebra and Its Applications, 34, 259-267.
Golub, G. and Seneta, E. (1974) Computation of the Stationary Distribution of an Infinite Stochastic Matrix of Special Form. Bulletin of the Australian Mathematical Society, 10, 255-261. https://doi.org/10.1017/S0004972700040867
Reuter, G.E.H. (1957) Denumerable Markov Processes and the Associated Contraction Semigroup on L. Acta Mathematica, 97, 1-46. https://doi.org/10.1007/BF02392391
Kendall, D.G. and Reuter, G.E.H. (1957) The Calculation of the Ergodic Projection for Markov Chains and Processes with a Countable Infinity of States. Acta Mathematica, 97, 103-144. https://doi.org/10.1007/BF02392395
Tweedie, R.L. (1973) The Calculation of Limit Probabilities for Denumerable Markov Processes from Infinitesimal Properties. Journal of Applied Probability, 10, 84-99. https://doi.org/10.1017/S0021900200042108
Tweedie, R.L. (1975) Sufficient Conditions for Regularity, Recurrence and Ergodicity of Markov Processes. Mathematical Proceedings of the Cambridge Philosophical Society, 78, 125-136. https://doi.org/10.1017/S0305004100051562
Gross, D., Shortle, J.F., Thompson, J.M. and Harris, C.M. (2008) Fundamentals of Queueing Theory. 4th Edition, Wiley, New Jersey. https://doi.org/10.1002/9781118625651
Baumann, H. (2017) Generalized Continued Fractions: Definitions, Convergence and Applications to Markov Chains. Habilitationsschrift. Clausthal University of Technology, Clausthal-Zellerfeld.
Seneta, E. (1981) Non-Negative Matrices and Markov Chains. Springer, New York. https://doi.org/10.1007/0-387-32792-4
Hanschke, T. (1999) A Matrix Continued Fraction Algorithm for the Multiserver Repeated Order Queue. Mathematical and Computer Modelling, 30, 159-170.
Baumann, H. and Sandmann, W. (2010) Numerical Solution of Level Dependent Quasi-Birth-and-Death Processes. Procedia Computer Science, 1, 1561-1569. https://doi.org/10.1016/j.procs.2010.04.175
Bright, L. and Taylor, P.G. (1995) Calculating the Equilibrium Distribution in Level Dependent Quasi-Birth-and-Death Processes. Communication in Statistics. Stochastic Models, 11, 497-525. https://doi.org/10.1080/15326349508807357
Baumann, H. and Sandmann, W. (2013) Computing Stationary Expectations in Level-Dependent QBD Processes. Journal of Applied Probability, 50, 151-165. https://doi.org/10.1017/S0021900200013176