Convergent Iterations for Computing Stationary Distributions of Markov Chains

Abstract

Classical iterative schemes such as the Gauss–Seidel method and its variations constitute powerful tools for computing stationary distribution vectors for large-scale Markov process, such as those arising in queueing network analysis. The coefficient matrix A in these processes in a Q-matrix, i.e., a singular irreducible M-matrix with zero column sums and, unlike the nonsingular case, the classical iterations for A do not always converge. The purpose of this paper is to survey the recent literature and to analyze the behavior of these methods completely in terms of the graph structure of A. The results given here hold under somewhat weaker assumptions on A.