Summary
Grassmann, Taksar, and Heyman introduced a variant of Gaussian climination 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barlow, J.L. (1992): Error bounds for the computation of null-vectors with applications to Markov chains. Proceedings of the IMA Workshop on Linear Algebra, Markov Chains, and Queuing Models, University of Minnesota (to appear)
Blondia, C. (1991): Finite-capacity vacation models with non-renewal input. J. Appl. Probab.28, 174–197
Funderlic, R.E., Neumann, M., Plemmons, R.J. (1982): LU decompositions of generalized diagonally dominant matrices. Numer. Math.40, 57–69
Grassmann, W.K., Taksar, M.I., Heyman, D.P. (1985): Regenerative analysis and steadystate distributions for Markov chains. Oper. Res.33(5), 1107–1116
Harrod, W.J., Plemmons, R.J. (1984): Comparison of some direct methods for computing stationary distributions of Markov chains. SIAM J. Sci. Stat. Comput.5(2), 453–469
Heyman, D.P. (1987): Further comparisons of direct methods for computing stationary distributions of Markov chains. SIAM J. Alg. Disc. Meth.8(2), 226–232
Golub, G.H., Van Loan, C.F. (1989): Matrix computations. Johns Hopkins University Press, Baltimore
Meyer, C.D., Stewart, G.W. (1988): Derivatives and perturbations of eigenvectors. SIAM J. Numer. Anal.25(3), 679–691
Seneta, E. (1981): Nonnegative matrices and Markov chains. Springer, Berlin Heidelberg New York
Stewart, G.W. (1973): Introduction to matrix computations. Academic Press, New York
Stewart, G.W. (1973): Computable error bounds for aggregated Markov chains. J. Assoc. Comput. Mach.30(2), 271–285
Stewart, G.W. (1984): On the structure of nearly uncoupled Markov chains. In: Iazeolla, G.G., Courtois, P.J., Hordijk A. ed., Mathematical Computer Performance and Reliability, pp. 287–302. Elsevier; North-Holland
Stewart, G.W. (1990): On the sensitivity of nearly uncoupled Markov chains. In: Stewart, W.J. ed., Numerical Solution of Markov Chains. Marcel Dekker. New York
Stewart, G.W. (1992): Rounding error, perturbation theory, and Markov chains. To appear in Proceedings of the IMA Workshop on Linear Algebra, Markov Chains, and Queuing Models, University of Minnesota
Stewart, G.W. (1992): On the perturbation of Markov chains with nearly transient states. Technical Report. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland
Stewart, G.W., Zhang, G. (1991): On a direct method for the solution of nearly uncoupled Markov chains. Numer. Math.59, 1–11
Walrand, J. (1991): Communication networks: a first course. Irwin, Boston
Wilkinson, J.H. (1963): Rounding errors in algebraic processes. Prentice-Hall, Englewood Cliffs, NJ
Author information
Authors and Affiliations
Additional information
This work was supported by NSF under grants DMS-9106207 and DDM-9203134