Exact algorithms for singular tridiagonal systems with applications to Markov chains

摘要

In this paper, we propose two exact algorithms to solve the steady state probability distributions of irreducible Markov chains whose generator matrices have tridiagonal structure. The first exact algorithm is based on divide-and-conquer procedure and the second one is a parallel algorithm. Examples on random walks and queuing networks are given to demonstrate the usefulness of the algorithms.