Computation of Steady-State Probabilities for Infinite-State Markov Chains with Repeating Rows

In this paper we consider Markov chains with these properties. The transition matrix is banded, and except for some boundary conditions, when the transition matrix is written in block form, the rows are identical except for a shift to the right. Some authors have used variants of the state reduction method to solve special cases. We present a general algorithm and some of the theoretical underpinnings of these methods. In particular, we give a rigorous proof of convergence. We also provide a simple method to norm the probabilities such that their sum is unity. We describe the connection between this new technique and the matrix-iterative methods of M. F. Neuts. The paper concludes with some numerical examples.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.