ENTRYWISE PERTURBATION-THEORY AND ERROR ANALYSIS FOR MARKOV-CHAINS

Grassmann, Taksar, and Heyman introduced a variant of Gaussian elimination for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem itself is well-conditioned, in the sense of entrywise relative error. Thus the algorithm computes each entry of the steady-state vector with low relative error. Even the small steady-state probabilities are computed accurately. The key to our analysis is to focus on entrywise relative error in both the data and the computed solution, rather than making the standard assessments of error based on norms. Our conclusions do not depend on any condition numbers for the problem.