Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-22T08:09:38.505Z Has data issue: false hasContentIssue false
  • English
  • Français

Perturbation bounds for the stationary probabilities of a finite Markov chain

Published online by Cambridge University Press:  01 July 2016

Moshe Haviv  and
Ludo Van Der Heyden
Moshe Haviv*
Affiliation:
Hebrew University, Jerusalem
Ludo Van Der Heyden*
Affiliation:
Yale University
*
∗Postal address: Department of Statistics, Hebrew University, Jerusalem 91905, Israel.
∗∗ Postal address: School of Organization and Management, Yale University, New Haven, CT 06520, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper discusses perturbation bounds for the stationary distribution of a finite indecomposable Markov chain. Existing bounds are reviewed. New bounds are presented which more completely exploit the stochastic features of the perturbation and which also are easily computable. Examples illustrate the tightness of the bounds and their application to bounding the error in the Simon–Ando aggregation technique for approximating the stationary distribution of a nearly completely decomposable Markov chain.

Keywords

NEARLY COMPLETELY DECOMPOSABLE SYSTEMSSTOCHASTIC MATRICES
Type
Research Article
Information
Advances in Applied Probability , Volume 16 , Issue 4 , December 1984 , pp. 804 - 818
Copyright
Copyright © Applied Probability Trust 1984 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Courtois, P. J. (1977a) Decomposability. Academic Press, New York.Google Scholar
Courtois, P. J. (1977b) The error of aggregation: comments on Zarling's analysis. MBLE Research Laboratory Report R345, Brussels.Google Scholar
Denardo, E. V. (1973) A Markov decision problem. In Mathematical Programming, ed. Hu, T. C. and Robinson, S. M. Academic Press, New York.Google Scholar
Hajnal, J. (1958) Weak ergodicity in non-homogeneous Markov chains. Proc. Camb. Phil. Soc. 54, 233–246.CrossRefGoogle Scholar
Haviv, M. (1983) Approximation in Markov Chains and Markov Decision Models. Ph.D. Dissertation, Yale University.Google Scholar
Kemeny, J. G. and Snell, J. L. (1960) Finite Markov Chains. Van Nostrand, New York.Google Scholar
Meyer, C. D. (1980) The solution of a finite Markov chain and perturbation bounds for the limiting probabilities. SIAM J. Algebraic and Discrete Methods 1, 273–283.CrossRefGoogle Scholar
Rothblum, U. G. and Schneider, H. (1980) Characterization of optimal scalings of matrices. Math. Programming 19, 121–136.CrossRefGoogle Scholar
Schweitzer, P. J. (1968) Perturbation and finite Markov chains. J. Appl. Prob. 5, 401–413.CrossRefGoogle Scholar
Simon, H. A. and Ando, A. (1961) Aggregation of variables in dynamic systems. Econometrica 29, 111–138.CrossRefGoogle Scholar
Stewart, G. W. (1980) Computable error bounds for aggregated Markov chains. Computer Science Center Technical Report 901, University of Maryland, College Park.Google Scholar
Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford.Google Scholar
Zarling, R. L. (1976) Numerical Solution of Nearly Completely Decomposable Queuing Networks, Ph.D. Dissertation, University of North Carolina, Chapel Hill.Google Scholar