Aggregation/Disaggregation Methods for Computing the Stationary Distribution of a Markov Chain
The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
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 81
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-citation
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.