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.