article

Free access

Computable Error Bounds for Aggregated Markov Chains

Author:

G. W. StewartAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 2

Pages 271 - 285

https://doi.org/10.1145/322374.322377

Published: 01 April 1983 Publication History

PDF eReader

References

[1]

CLINE, A.K., MOLER, C.B., STEWART, G.W., AND WILKINSON, J.H.An esttmate for the ~ondiuon number. SlAM J. Numer. Anal. 16 (1979), 368-375.

Google Scholar

[2]

COURTOIS, P.J. Error analysis in nearly-completely decomposable stochastic systems. Econ. 43 (1975), 691-709.

Google Scholar

[3]

COURTOIS, P J Decomposability: Queueing and Computer System Applications. Academic Press, New York, 1977.

Google Scholar

[4]

DuFF I. ANO STEWART, G.W, Eos.Sparse Matrix Proc. 1978. SIAM, Phdadelptua, Pa. 1979.

Google Scholar

[5]

JENNINOS, A. AND STEWART, W.J. Simultaneous iteration for parual elgensolution of real matrices. ~ Inst. Math. Appl. 15 (1975), 351-362.

Google Scholar

[6]

O'LEARY, D.P., STEWART, G W., VAINDERGRAFT, J.S. Estimating the largest eigenvalue of a posluve definite matrix. Math. Comput. 33 (1979), 1289-1292.

Google Scholar

[7]

SIMON, H.A, AND ANDo, A. Aggregation of variables in dynamic systems. Econ. 29 ( 1961), I 11-138.

Google Scholar

[8]

STEWART, G.W. Error and perturbation bounds for subspaces associated wxth certain eigenvalue problems. SlAM Rev. 15 (1973), 727-764.

Google Scholar

[9]

STEWART, G.W.Introduction to Matrix Computaoons. Academic Press, New York, 1974.

Google Scholar

[10]

STEWART~ G.W. Stmultaneous iteratton for computing mvanant subspaces of non-Hermitian matrices. Numer. Math. 25 (1976), 123-136.

Google Scholar

[11]

STEW~aZT, G.W. HQR3 and EXCHNG: Fortran subroutines for calculating and ordering the eigenvalues of a real upper Hessenberg matrix. ACM Trans. Math. Soflw. 2, 3 (Sept. 1976), 275-280.

Crossref

Google Scholar

[12]

STEWART, G.W.On the Jmphcit deflation of nearly singular systems of linear eq'aatioas, SlAM j. Scmnt Stat Comput 2 (1981), 136-140

Google Scholar

[13]

VANTILBORGH, H Exact aggregation in exponential queueing networks. J. ACM. 25, 4 (Oct. 1978), 620-629.

Crossref

Google Scholar

[14]

VARGA, R S Matrix Iteranve Analys~s Pterttlce-Hall, Englewood Cliffs, lq.L, 1962.

Google Scholar

[15]

ZARLING, R Numerical solution of nearly decomposable queueing networks. Ph.D. Dissertation, Umv of North Carohna, 1976. Available from Un,versay Microfilms, Ann Arbor, Mlch.

Crossref

Google Scholar

Cited By

View all

Piazza CRossi SSmuseva D(2024)Efficient Algorithm for Proportional Lumpability and Its Application to Selfish Mining in Public BlockchainsAlgorithms10.3390/a1704015917:4(159)Online publication date: 15-Apr-2024
https://doi.org/10.3390/a17040159
Silvestrov DSilvestrov S(2017)Asymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov ProcessesEngineering Mathematics II10.1007/978-3-319-42105-6_10(151-222)Online publication date: 11-Feb-2017
https://doi.org/10.1007/978-3-319-42105-6_10
Louchard GLatouche G(2016)Geometric bounds on iterative approximations for nearly completely decomposable Markov chainsJournal of Applied Probability10.2307/321453827:03(521-529)Online publication date: 14-Jul-2016
https://doi.org/10.2307/3214538
Show More Cited By

Index Terms

Computable Error Bounds for Aggregated Markov Chains

Recommendations

Refinable Bounds for Large Markov Chains

A method to bound the steady-state solution of large Markov chains is presented. It integrates the concepts of eigenvector polyhedron and of aggregation and is iterative in nature.The bounds are obtained by considering a subset only of the system state ...
Markov Chain Aggregation with Error Bounds on Transient Distributions
Analytical and Stochastic Modelling Techniques and Applications
Abstract
We extend the existing theory of formal error bounds for the transient distribution of an aggregated (or lumped) Markov chain when compared to the transient distribution of the original chain, for both discrete- and continuous-time Markov chains. ...
Error bounds for augmented truncation approximations of continuous-time Markov chains
Abstract
This paper considers the augmented truncation approximation of the generator of an ergodic continuous-time Markov chain with a countably infinite state space. The main purpose of this paper is to present bounds for the absolute ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 2

April 1983

157 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322374

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1983

Published in JACM Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Piazza CRossi SSmuseva D(2024)Efficient Algorithm for Proportional Lumpability and Its Application to Selfish Mining in Public BlockchainsAlgorithms10.3390/a1704015917:4(159)Online publication date: 15-Apr-2024
https://doi.org/10.3390/a17040159
Silvestrov DSilvestrov S(2017)Asymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov ProcessesEngineering Mathematics II10.1007/978-3-319-42105-6_10(151-222)Online publication date: 11-Feb-2017
https://doi.org/10.1007/978-3-319-42105-6_10
Louchard GLatouche G(2016)Geometric bounds on iterative approximations for nearly completely decomposable Markov chainsJournal of Applied Probability10.2307/321453827:03(521-529)Online publication date: 14-Jul-2016
https://doi.org/10.2307/3214538
Truffet L(2016)Near Complete Decomposability: Bounding the Error by a Stochastic Comparison MethodAdvances in Applied Probability10.2307/142808729:03(830-855)Online publication date: 1-Jul-2016
https://doi.org/10.2307/1428087
Louchard GLatouche G(2016)Geometric bounds on iterative approximations for nearly completely decomposable Markov chainsJournal of Applied Probability10.1017/S002190020003908527:03(521-529)Online publication date: 14-Jul-2016
https://doi.org/10.1017/S0021900200039085
Balsamo SDei Rossi GMarin A(2014)Lumping and reversed processes in cooperating automataAnnals of Operations Research10.1007/s10479-014-1694-3239:2(695-722)Online publication date: 22-Aug-2014
https://doi.org/10.1007/s10479-014-1694-3
Balsamo SDei Rossi GMarin A(2012)Lumping and reversed processes in cooperating automataProceedings of the 19th international conference on Analytical and Stochastic Modeling Techniques and Applications10.1007/978-3-642-30782-9_15(212-226)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30782-9_15
Li QLi Q(2010)Transient SolutionConstructive Computation in Stochastic Models with Applications10.1007/978-3-642-11492-2_8(389-431)Online publication date: 2010
https://doi.org/10.1007/978-3-642-11492-2_8
Stewart W(2000)Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov ChainsComputational Probability10.1007/978-1-4757-4828-4_4(81-111)Online publication date: 2000
https://doi.org/10.1007/978-1-4757-4828-4_4
Van Dijk N(1998)Invited Analytic comparison results for communication networksComputer Communications10.1016/S0140-3664(98)00218-721:17(1495-1508)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1016/S0140-3664%2898%2900218-7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Refinable Bounds for Large Markov Chains

Markov Chain Aggregation with Error Bounds on Transient Distributions

Error bounds for augmented truncation approximations of continuous-time Markov chains

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations