A Revised Stochastic Complementation Algorithm for Nearly Completely Decomposable Markov Chains

This paper presents a new algorithm which uses stochastic complementation to compute the stationary distribution vector of a nearly completely decomposable (NCD) Markov chain. NCD problems are ill-conditioned, and many methods suffer from loss of accuracy. A formal error analysis and test results from a series of NCD problems are presented which show that the new algorithm computes accurate solutions to this type of problem. Operation counts and timings from experiments are presented which highlight the efficiency of the new algorithm.

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