On the Perturbation of Markov Chains with Nearly Transient States

To Appear in Numerische Mathematik Let $A$ be an irreducible stochastic matrix of the form \[ A = \bmx{cc} A_{11} & E_{12} \\ A_{21} & A_{22} \emx. \] If $E_{22}$ were zero, the states corresponding to $A_{22}$ would be transient in the sense that if the steady state vector $y\trp$ is partitioned conformally in the form $(y_1\trp \; y_2\trp)$ then $y_2\trp = 0$. If $E_{22}$ is small, then $y_2\trp$ will be small, and the states are said to be nearly transient. It this paper it is shown that small relative perturbations in $A_{11}$, $A_{21}$, and $A_{22}$, though potentially larger than $y_2\trp$, induce only small relative perturbations in $y_2\trp$. (Also cross-referenced as UMIACS-TR-92-14