A Two-Stage Iteration for Solving Nearly Uncoupled Markov Chains

Abstract

This paper is concerned with an iteration for determining the steady-state probability vector of a nearly uncoupled Markov Chain. The states of these chains can be partitioned into aggregates with low probabilities of transitions between aggregates. The iteration consists of alternating block Gauss--Seidel iterations with Rayleigh--Ritz refinements. Under natural regularity conditions, the composite iteration reduces the error by a factor proportional to the size of the coupling between aggregates, so that the more loosely the chain is coupled, the faster the convergence.