Computing hitting probabilities of Markov chains: structural results with regard to the solution space of the corresponding system of equations

DOI10.1155/2020/9874072MaRDI QIDQ2176038zbMATH OpenOpenAlexFDO

Authors Hendrik Baumann, Thomas Hanschke

Publication date 30 April 2020

Published in Journal of Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2020/9874072

Mathematics Subject Classification ID

Additive difference equations (39A10) Convergence and divergence of continued fractions (40A15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical methods for functional equations (65Q20)

Review text

Summary: In a previous paper, we have shown that forward use of the steady-state difference equations arising from homogeneous discrete-state space Markov chains may be subject to inherent numerical instability. More precisely, we have proven that, under some appropriate assumptions on the transition probability matrix \(P\), the solution space \(S\) of the difference equation may be partitioned into two subspaces \(S = S_1 \oplus S_2\), where the stationary measure of \(P\) is an element of \(S_1\), and all solutions in \(S_1\) are asymptotically dominated by the solutions corresponding to \(S_2\). In this paper, we discuss the analogous problem of computing hitting probabilities of Markov chains, which is affected by the same numerical phenomenon. In addition, we have to fulfill a somewhat complicated side condition which essentially differs from those conditions one is usually confronted with when solving initial and boundary value problems. To extract the desired solution, an efficient and numerically stable generalized-continued-fraction-based algorithm is developed.

Recommendations

• scientific article; zbMATH DE number 729460
• Stable computation with the fundamental matrix of a Markov chain
• Algorithms for finding steady state probabilities for some special classes of finite state Markov chains
• Numerical Methods in Markov Chain Modeling
• Technical Note—A Markov Chain Partitioning Algorithm for Computing Steady State Probabilities

Cites work

• A generalized Jacobi-Perron algorithm for the reduction of systems of linear difference equations
• A note on the numerical solution of linear recurrence relations
• Characterizations of dominant and dominated solutions of linear recursions
• Computational Aspects of Three-Term Recurrence Relations
• scientific article; zbMATH DE number 3736679 (Why is no real title available?)
• scientific article; zbMATH DE number 3260110 (Why is no real title available?)
• Linear difference equations and generalized continued fractions
• Markov chains and generalized continued fractions
• Markov chains and stochastic stability
• Matrix continued fractions related to first-order linear recurrence systems
• Pringsheim's theorem for generalized continued fractions
• Zur Numerik rekurrenter Relationen
• Über die Minimallösung der Poincaré-Perronschen Differenzengleichung. (On the minimal solution of Poincaré-Perron type difference equations)

This page was built for publication: Computing hitting probabilities of Markov chains: structural results with regard to the solution space of the corresponding system of equations

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