The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Aggregation/Disaggregation Methods for Computing the Stationary Distribution of a Markov Chain
Abstract
We implement and analyse aggregation/disaggregation procedures constructed to accelerate the convergence of successive approximation methods suitable for computing the stationary distribution of a finite Markov chain. We define six of these methods and analyse them in detail. In particular, we show that some existing procedures lie in the aggregation/disaggregation framework we set, and hence can be considered as special cases. Also, for all described methods, we identify cases where they are promising. Numerical examples for the applications of some of the methods for nearly completely decomposable stochastic matrices are given as well.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Generalized Inverses of Linear Transformations
Campbell, S. L., & Meyer, C. D. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719048 · Cited by 1,897
Aggregation of Variables in Dynamic Systems
Simon, H. A., & Ando, A. (1961) · Econometrica · doi:10.2307/1909285 · Cited by 562
Iterative aggregation/disaggregation techniques for nearly uncoupled markov chains
Cao, W.-L., & Stewart, W. J. (1985) · Journal of the ACM · doi:10.1145/3828.214137 · Cited by 120
Acceleration by aggregation of successive approximation methods
Chatelin, F., & Miranker, W. L. (1982) · Linear Algebra and its Applications · doi:10.1016/0024-3795(82)90242-7 · Cited by 82
Perturbation bounds for the stationary probabilities of a finite Markov chain
Haviv, M., & der Heyden, L. V. (1984) · Advances in Applied Probability · doi:10.1017/s0001867800022941 · Cited by 79
Self-citationComputable Error Bounds for Aggregated Markov Chains
Stewart, G. W. (1983) · Journal of the ACM · doi:10.1145/322374.322377 · Cited by 61
Perturbation bounds for the stationary probabilities of a finite Markov chain
Haviv, M., & der Heyden, L. V. (1984) · Advances in Applied Probability · doi:10.2307/1427341 · Cited by 59
Self-citationIterative Aggregation-Disaggregation Procedures for Discounted Semi-Markov Reward Processes
Schweitzer, P. J., Puterman, M. L., & Kindle, K. W. (1985) · Operations Research · doi:10.1287/opre.33.3.589 · Cited by 48
Aggregation with an error of O (ε 2 )
Vantilborgh, H. T. (1985) · Journal of the ACM · doi:10.1145/2455.214107 · Cited by 44
On a Rayleigh-Ritz refinement technique for nearly uncoupled stochastic matrices
McAllister, D. F., Stewart, G. W., & Stewart, W. J. (1984) · Linear Algebra and its Applications · doi:10.1016/0024-3795(84)90067-3 · Cited by 29
Research works printed but not linked: 1
- Chatelin F., 1984, Mathematical computer performance and reliability (Pisa, 1983), 199
Cited by
Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
Meyer, C. D. (1989) · SIAM Review · doi:10.1137/1031050 · Cited by 316
A solver for the stochastic master equation applied to gene regulatory networks
Hegland, M., Burden, C. J., Santoso, L. M., MacNamara, S., & Booth, H. S. (2006) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2006.02.053 · Cited by 133
“For a discussion of aggregation in general, see [18,7,19,12].”
BackgroundSensitivity of the Stationary Distribution of a Markov Chain
Meyer, C. D. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479892228900 · Cited by 104
“…which are nearly uncoupled, direct methods are usually involved—they can be the basis of the main algorithm [Stewart and Zhang (1991)], or they can be used to solve the aggregated and coupling chains in iterative aggregation/disaggregation algorithms [Chatelin and Miranker (1982), Haviv (1987)].”
BackgroundMethodInfluentialModeling and analysis of communication systems based on computational methods for Markov chains
Krieger, U. R., Müller‐Clostermann, B., & Sczittnick, M. (1990) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.62851 · Cited by 73
Singular Perturbations of Markov Chains and Decision Processes
Avrachenkov, K. E., Filar, J. A., & Haviv, M. (2002) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4615-0805-2_4 · Cited by 46
Self-citationNumerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains
Stewart, W. J. (2000) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4757-4828-4_4 · Cited by 46
Marek, I., & Mayer, P. (1998) · Numerical Linear Algebra with Applications · doi:10.1002/(sici)1099-1506(199807/08)5:4 · Cited by 44
Numerical Solution of Large Finite Markov Chains by Algebraic Multigrid Techniques
Krieger, U. R. (1995) · Springer eBooks · doi:10.1007/978-1-4615-2241-6_23 · Cited by 34
Bounds and error bounds for queueing networks
DIJK, N. M. V. (1998) · Annals of Operations Research · doi:10.1023/a:1018978823209 · Cited by 34
Application of threshold partitioning of sparse matrices to Markov chains
Choi, H., & Szyld, D. B. (2002) · doi:10.1109/ipds.1996.540217 · Cited by 33
“Stewart [24], or Varga [28] for description of the block iterative methods, to the survey by Philippe, Saad and Stewart [17] for the use of Krylov-based methods, and to the surveys by Schweitzer [19], [20] for the aggregation methods; see also [4], [5], [10], [14], [25], [26].”
MethodAn Aggregation/Disaggregation Algorithm for Stochastic Automata Networks
Buchholz, P. (1997) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964800004782 · Cited by 27
“For aggregation according to a single automaton, the known but limited results for local convergence of the standard approach apply (Haviv [9], Schweitzer and Kindle [17]).”
MethodNearly reducible finite Markov chains: Theory and algorithms
Sharpe, D., & Wales, D. J. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0060978 · Cited by 28
On a two-level multigrid solution method for finite Markov chains
Krieger, U. R. (1995) · Linear Algebra and its Applications · doi:10.1016/0024-3795(95)00166-o · Cited by 21
Models of Perishable Queueing-Inventory Systems with Server Vacations
Королюк, В. С., Melikov, A. Z., Ponomarenko, L. A., et al. (2018) · Cybernetics and Systems Analysis · doi:10.1007/s10559-018-0005-4 · Cited by 19
Silvestrov, D. S., & Silvestrov, S. D. (2017) · AIP conference proceedings · doi:10.1063/1.4972739 · Cited by 19
“…(1984), McAllister, Stewart and Stewart, W. (1984), Cao and Stewart (1985), Kartashov (1986, 1987, 1996b), Burnley (1987), Gibson and Seneta (1987), Haviv (1987), Haviv, Ritov and Rothblum (1987), Rohlichek (1987), Rohlicek and Willsky (1988a, b), Silvestrov and Velikii (1988), Hunter…”
BackgroundMethodInfluentialFast multilevel methods for Markov chains
Sterck, H. D., Miller, K., Treister, E., et al. (2011) · Numerical Linear Algebra with Applications · doi:10.1002/nla.800 · Cited by 17
A discrete spectral method for the chemical master equation
Engblom, S. (2008) · Cited by 17
Haviv, M. (1992) · Stochastic Models · doi:10.1080/15326349208807239 · Cited by 15
Self-citationA New Algorithm for Computing the Ergodic Probability Vector for Large Markov Chains
Sumita, U., & Rieders, M. (1990) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964800001479 · Cited by 16
“The Markov chain J(k) has been discussed in Haviv [9].”
BackgroundMethodInfluentialA Bootstrap Algebraic Multilevel Method for Markov Chains
Bolten, M., Brandt, A., Brannick, J. J., et al. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/100791816 · Cited by 16
“…[13] which gives a thorough introduction into the concept of aggregation in Markov chains with a discussion of multiplicative vs. additive methods and the paper [20] which gives a survey on different a/d methods together with a unifying approach which comprises many a/d methods published so far.”
MethodAn exact aggregation/disaggregation algorithm for large scale markov chains
Kim, D. S., & Smith, R. L. (1995) · Naval Research Logistics (NRL) · doi:10.1002/1520-6750(199510)42:7 · Cited by 15
Asymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2016) · International Symposium on Stochastic Models in Reliability Engineering, Life Science and Operations Management · doi:10.1109/smrlo.2016.18 · Cited by 14
Iterative Methods for Finding the Stationary Vector for Markov Chains
O’Leary, D. P. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8351-2_9 · Cited by 15
Optimal dimensionality reduction of Markov chains using graph transformation
Kannan, D., Sharpe, D., Swinburne, T. D., & Wales, D. J. (2020) · The Journal of Chemical Physics · doi:10.1063/5.0025174 · Cited by 14
Marek, I., & Szyld, D. B. (1994) · Numerische Mathematik · doi:10.1007/s002110050080 · Cited by 14
“Iterative aggregation refers to a class of methods, sometimes called aggregation/disaggregation, which has been an effective tool for the solution of linear systems and certain eigenvalue problems; see Cao and Stewart [2], Chatelin and Miranker [4], [5], Haviv [ 15 ], Mandel and Sekerka [22], Miranker and Pan [30], an…”
MethodOn the Sensitivity of the Solution of Nearly Uncoupled Markov Chains
Zhang, G. D. (1993) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0614075 · Cited by 11
Blockwise perturbation theory for nearly uncoupled Markov chains and its application
Xue, J. (2001) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00280-9 · Cited by 10
Analytical perturbations in Markov chains
Baruh, H., & Altiok, T. M. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90251-p · Cited by 10
Numerical analysis of first-passage processes in finite Markov chains exhibiting metastability
Sharpe, D., & Wales, D. J. (2021) · Physical review. E · doi:10.1103/physreve.104.015301 · Cited by 10
Asymptotic Expansions for Stationary Distributions of Nonlinearly Perturbed Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_4 · Cited by 8
The Character of a Finite Markov Chain
Meyer, C. D. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8351-2_4 · Cited by 8
Rogers, D. F., & PLANTE, R. D. (1993) · Computers & Operations Research · doi:10.1016/0305-0548(93)90107-t · Cited by 7
More on Rayleigh–Ritz Refinement Technique for Nearly Uncoupled Stochastic Matrices
Haviv, M. (1989) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0610022 · Cited by 7
Self-citationAsymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2016) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-319-42105-6_10 · Cited by 6
Influence of Preconditioning and Blocking on Accuracy in Solving Markovian Models
Bylina, B., & Bylina, J. (2009) · International Journal of Applied Mathematics and Computer Science · doi:10.2478/v10006-009-0017-3 · Cited by 6
“Iterative methods are described, for example, in (Jennings and Stewart, 1975; Stewart and Jennings, 1981), and projection methods are discussed in (Saad and Schultz, 1986; Bylina, 2003), while decomposition methods are described in (Schweitzer and Kindle, 1986; Haviv, 1987 ).”
MethodAnalytic comparison results for communication networks
DIJK, N. M. V. (1998) · Computer Communications · doi:10.1016/s0140-3664(98)00218-7 · Cited by 5
Graph transformation and shortest paths algorithms for finite Markov chains
Sharpe, D., & Wales, D. J. (2021) · Physical review. E · doi:10.1103/physreve.103.063306 · Cited by 6
Klas, G., & Matuschka, R. (2002) · doi:10.1109/pnpm.1991.238783 · Cited by 5
Asymptotic Expansions for Moments of Hitting Times for Nonlinearly Perturbed Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_3 · Cited by 4
Triangular and skew-symmetric splitting method for numerical solutions of Markov chains
Wen, C., Huang, T., & Wang, C. (2011) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2011.09.041 · Cited by 4
Stewart, D. E., & Bebbington, M. (1996) · Journal of Statistical Computation and Simulation · doi:10.1080/00949659608811781 · Cited by 4
Local Convergence of (Exact and Inexact) Iterative Aggregation
Szyld, D. B. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8351-2_10 · Cited by 4
State Space Decomposition for Large Markov Chains
Rieders, M. (1995) · Springer eBooks · doi:10.1007/978-1-4615-2241-6_33 · Cited by 4
Accelerating Successive Approximation Algorithm Via Action Elimination
Jaber, N., & Lee, C.-G. J. (2009) · TSpace (University of Toronto) · Cited by 3
Krieger, U. R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-02742-0_23 · Cited by 2
“[4], [10]), we determine the following entities.”
A successive censoring algorithm for a system of connected LDQBD-processes
Baër, N., Hanbali, A. A., Boucherie, R. J., et al. (2021) · Annals of Operations Research · doi:10.1007/s10479-020-03903-2 · Cited by 2
“For a thorough overview and comparison of several aggregation/disaggregation algorithms see Cao and Stewart (1985), Haviv (1987), Kafeety et al. (1992) and Rogers and Plante (1993).”
MethodA multi-cluster time aggregation approach for Markov chains
Arruda, E. F., Fragoso, M. D., & Ourique, F. D. O. (2018) · Automatica · doi:10.1016/j.automatica.2018.10.027 · Cited by 2
An Adaptively Constructed Algebraic Multigrid Preconditioner for Irreducible Markov ChainsPreprint
Brannick, J. J., Kahl, K., & Sokolović, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4005 · Cited by 2
“hat they use a series of increasingly smaller Markov chains which are generated by aggregating groups of states into a single state. Most aggregation/disaggregation methods are two-level methods (cf. [14, 15, 16]) as they are based on the original approach in [17, 18], and it took approximately twenty years until mult…”
MethodDu, C., & Wong, W. H. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1610.07213 · Cited by 5
Silvestrov, D. S., & Silvestrov, S. D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.04743 · Cited by 2
“…Chatelin and Miranker (1984), Courtois and Semal (1984), Seneta (1984, 1991), Cao and Stewart (1985), Vantilborgh (1985), Feinberg and Chiu (1987), Haviv (1987, 1992, 1999), Rohlichek (1987), Rohlicek and Willsky (1988), Sumita and Reiders (1988), Meyer (1989), Schweitzer (1991), Stewart and…”
BackgroundSterck, H. D., Miller, K., & Sanders, G. D. (2011) · Computing and Visualization in Science · doi:10.1007/s00791-011-0163-7 · Cited by 1
Solving the Chemical Master Equation with the Aggregation-Disaggregation Method
Hegland, M. (2009) · Cited by 1
Nonlinearly Perturbed Birth-Death-Type Semi-Markov Processes
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_5 · Cited by 1
Examples and Survey of Applied Perturbed Stochastic Models
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_6 · Cited by 1
Aggregation Methods for Computing Steady States in Statistical Physics
Earle, G., & Koten, B. V. (2023) · Multiscale Modeling and Simulation · doi:10.1137/22m1530628 · Cited by 1
Dayar, T. (2018) · Springer series in operations research/Springer series in operations research and financial engineering · doi:10.1007/978-3-319-97129-2_6 · Cited by 1
Baër, N. (2014) · doi:10.3990/1.9789036538121 · Cited by 1
“For a thorough overview and comparison of several aggregation/disaggregation algorithms see Cao and Stewart [18], Haviv [39], Kafeety, Meyer and Stewart [51] and Rogers and Plante [91].”
MethodA graph-theoretic approach to queueing analysis part ii: applications
Chi-nang, T., & Yeung Raymond, W. (1999) · Stochastic Models · doi:10.1080/15326349908807565 · Cited by 1
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_2
Random Surfing Revisited: Generalizing PageRank's Teleportation ModelPreprint
Νικολακόπουλος, Α. Ν. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.12916
“The earliest work along these lines can be traced back to Takahashi [89] and the standard two-level IAD have been studied extensively ever since [63, 64, 88, 90, 91].”
BackgroundBuchholz, P. (1991) · Informatik-Fachberichte · doi:10.1007/978-3-642-76923-8_7
Silvestrov, D. S., & Silvestrov, S. D. (2017) · SpringerBriefs in probability and mathematical statistics · doi:10.1007/978-3-319-60988-1_1
Approximating Large Scale Queueing System: An Overview and Directions for Further Research
Alfa, A. S., & Ghazaleh, H. A. (2026) · Mathematics · doi:10.3390/math14183321
Metadata
- Authors
- Haviv, M.
- Affiliations
- Hebrew University of Jerusalem (IL)
- Corresponding author
- Haviv, Moshe
- ORCID
- Haviv, Moshe
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 1987-08
- Volume
- 24
- Issue
- 4
- Pages
- 952-966
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W2034727050
- Semantic Scholar
- fd026dc377de5e55346c23b9057bf09784b25d42
- Cited by
- 64
- References
- 12
- Citations by year
- 2026: 1 · 2023: 1 · 2021: 4 · 2020: 2 · 2018: 3 · 2017: 7 · 2016: 4 · 2014: 2
- FWCI
- 1.86
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Numerical Analysis (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Keywords
- aggregation and disaggregation, stationary distribution, finite Markov chains, successive approximations, convergence acceleration, stochastic matrices
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.