Perturbation results for nearly uncoupled Markov chains with applications to iterative methods (Q1326392)

The standard perturbation theory for linear equations states that nearly uncoupled Markov chains (NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that show that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping criteria, iterative aggregation/disaggregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to \textit{W. K. Grassman}, \textit{M. I. Taksar} and \textit{D. P. Heyman} [Oper. Res. 33, 1107-1116 (1985; Zbl 0576.60083)] was recently shown by \textit{C. A. O'Cinneide} [Error analysis of a variant of Gaussian elemination for steady-state distribution of Markov chains. Techn. Rep., Purdue Univ., West Lafayette (1992)] to achieve such bounds.