ENTRYWISE PERTURBATION-THEORY AND ERROR ANALYSIS FOR MARKOV-CHAINS

Grassmann, Taksar, and Heyman introduced a variant of Gaussian elimina tion for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem it self is well-conditioned, in the sense of entrywise relative error. Th us the algorithm computes each entry of the steady-state vector with l ow relative error. Even the small steady-state probabilities are compu ted accurately. The key to our analysis is to focus on entrywise relat ive error in both the data and the computed solution, rather than maki ng the standard assessments of error based on norms. Our conclusions d o not depend on any condition numbers for the problem.