Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-15T17:09:25.315Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometric bounds on iterative approximations for nearly completely decomposable Markov chains

Published online by Cambridge University Press:  14 July 2016

Guy Louchard  and
Guy Latouche
Guy Louchard
Affiliation:
Université Libre de Bruxelles
Guy Latouche*
Affiliation:
Université Libre de Bruxelles
*
∗Postal address for both authors: Laboratoire d'Informatique Théorique, Faculté des Sciences, Université Libre de Bruxelles, Campus Plaine CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a finite Markov chain with nearly-completely decomposable stochastic matrix. We determine bounds for the error, when the stationary probability vector is approximated via a perturbation analysis.

Keywords

ERROR BOUNDSPERTURBATION ANALYSISAGGREGATION-DISAGGREGATION
Type
Research Papers
Information
Journal of Applied Probability , Volume 27 , Issue 3 , September 1990 , pp. 521 - 529
Copyright
Copyright © Applied Probability Trust 1990 

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

[1] Cao, W. L. and Stewart, W. J. (1985) Iterative aggregation-disaggregation techniques for nearly uncoupled Markov chains. J. ACM 32, 702–719.Google Scholar
[2] Campbell, S. L. and Meyer, C. D. (1979) Generalized Inverses of Linear Transformations. Pitman, London.Google Scholar
[3] Courtois, P. J. (1977) Decomposability, Queueing and Computer Systems Applications. Academic Press, New York.Google Scholar
[4] Courtois, P. J. and Louchard, G. (1976) Approximation of eigencharacteristics in nearly-completely decomposable stochastic systems. Stoch. Proc. Appl. 4, 283–296.Google Scholar
[5] Courtois, P. J. and Semal, P. (1984) Bounds for the positive eigenvectors of non-negative matrices and for their approximations by decomposition. J. ACM 31, 804–825.CrossRefGoogle Scholar
[6] Courtois, P. J. and Semal, P. (1986) Computable bounds for conditional steady-state probabilities in large Markov chains and queueing models. IEEE J. Sel. Areas Comm. 4, 926–937.Google Scholar
[7] Haviv, M. and Van Der Heyden, L. (1984) Perturbation bounds for the stationary probabilities of a finite Markov chain. Adv. Appl. Prob. 16, 804–818.Google Scholar
[8] Hunter, J. J. (1982) Generalized inverses and their application to applied probability problems. Linear Alg. Appl. 45, 157–198.CrossRefGoogle Scholar
[9] Kato, T. (1966) Peturbation Theory for Linear Operators. Springer-Verlag, New York.Google Scholar
[10] Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1966) Denumerable Markov Chains. Van Nostrand, Princeton, NJ.Google Scholar
[11] Koury, J. R., Mcallister, D. F. and Stewart, W. J. (1984) Iterative methods for computing stationary distributions of nearly completely decomposable Markov chains. SIAM J. Alg. Disc. Meth. 5, 164–185.Google Scholar
[12] Latouche, G. and Louchard, G. (1978) Return times in nearly completely decomposable stochastic processes. J. Appl. Prob. 15, 251–267.Google Scholar
[13] Louchard, G. and Latouche, G. (1988) Nearly completely decomposable Markov chains: bounds on iterative approximations for the stationary probability vector. Université Libre de Bruxelles, Laboratoire d'Informatique Théorique, Tech. Rept. 168.Google Scholar
[14] Schweitzer, P. J. (1986) Perturbation series expansions for nearly completely-decomposable Markov chains. Teletraffic Analysis and Computer Performance Evaluation, ed. Boxma, O. J., Cohen, J. W., and Tijms, H., 319–328.Google Scholar
[15] Simon, H. A. and Ando, A. (1961) Aggregation of variables in dynamic systems. Econometrica 29, 111–138.Google Scholar
[16] Stewart, G. W. (1983) Computable error bound for aggregated Markov chains. J. ACM 30, 271–285.Google Scholar
[17] Vantilborgh, H. (1985) Aggregation with an error O(e2). J. ACM 32, 162–190.CrossRefGoogle Scholar