Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Abstract
A concept called stochastic complementation is an idea which occurs naturally, although not always explicitly, in the theory and application of finite Markov chains. This paper brings this idea to the forefront with an explicit definition and a development of some of its properties. Applications of stochastic complementation are explored with respect to problems involving uncoupling procedures in the theory of Markov chains. Furthermore, the role of stochastic complementation in the development of the classical Simon–Ando theory of nearly reducible system is presented
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Since (I − Pii) −1 ≥ 0 [24] and (L + U) ≥ 0, the split- ting above is weak regular.”
From Distributed PageRank computation based on iterative aggregation-disaggregation methods (2005) · cites this paper as [24]
Citations
Cites
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280 · cited 4×
“It is well known (see [19] or [11]) that for every square matrix A and each ǫ > 0, there exists a matrix norm ||| • ||| such that ρ(A) ≤ |||A||| ≤ ρ(A) + ǫ.”
BackgroundInfluentialNonnegative Matrices in the Mathematical Sciences
(1979) · Elsevier eBooks · doi:10.1016/c2013-0-10361-3 · Cited by 5,451
Kemeny, J. G., & Snell, J. L. (1976) · Medical Entomology and Zoology · Cited by 2,813
Introduction to matrix computations
Stewart, G. W. (1973) · International Linear Collider · Cited by 2,381
Bush, K. A., Kemeny, J. G., & Snell, J. L. (1960) · The American Mathematical Monthly · doi:10.2307/2309264 · Cited by 1,546
Aggregation of Variables in Dynamic Systems
Simon, H. A., & Ando, A. (1961) · Econometrica · doi:10.2307/1909285 · Cited by 562
Aggregation of Variables in Dynamic Systems
Simon, H. A. (1977) · Boston Studies in the Philosophy of Science · doi:10.1007/978-94-010-9521-1_12 · Cited by 550 · cited 6×
“The contribution of Simon and Ando [18] was to provide mathematical arguments for what had previously been a rather heuristic theory concerning nearly completely reducible systems.”
BackgroundMethodInfluentialDecomposability: Queueing and Computer System Applications
Courtois, P. (1977) · Cited by 471
Regenerative Analysis and Steady State Distributions for Markov Chains
Grassmann, W. K., Taksar, M. I., & Heyman, D. P. (1985) · Operations Research · doi:10.1287/opre.33.5.1107 · Cited by 364 · cited 1×
“Simple forms of stochastic complementation can be found either explicitly or implicitly in a variety of Markov chain applications such as those in [1], [3]–[6], [8]–[10], [12]–[16], [20], [21], in addition to several others.”
BackgroundTeletraffic analysis and computer performance evaluation
(1986) · Computer Networks and ISDN Systems · doi:10.1016/0169-7552(86)90083-8 · Cited by 189 · cited 1×
“If P = P 11 P 12 · · · P 1k P 21 P 22 · · · P 2k . . . . . . . . . . .”
Uncoupling the Perron eigenvector problem
Meyer, C. D. (1989) · Linear Algebra and its Applications · doi:10.1016/0024-3795(89)90452-7 · Cited by 87
Self-citationPerturbation 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
Aggregation/Disaggregation Methods for Computing the Stationary Distribution of a Markov Chain
Haviv, M. (1987) · SIAM Journal on Numerical Analysis · doi:10.1137/0724062 · Cited by 64
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
Aggregation with an error of O (ε 2 )
Vantilborgh, H. T. (1985) · Journal of the ACM · doi:10.1145/2455.214107 · Cited by 44 · cited 1×
“Simple forms of stochastic complementation can be found either explicitly or implicitly in a variety of Markov chain applications such as those in [1], [3]–[6], [8]–[10], [12]–[16], [20], [21], in addition to several others.”
BackgroundBlock iterative algorithms for stochastic matrices
Courtois, P. J., & Semal, P. (1986) · Linear Algebra and its Applications · doi:10.1016/0024-3795(86)90214-4 · Cited by 38
Reduced systems in Markov chains and their applications in queueing theory
Lal, R., & Bhat, U. N. (1987) · Queueing Systems · doi:10.1007/bf01158397 · Cited by 21
Numerical solution of nearly decomposable queueing networks
Zarling, R. L. (1976) · Cited by 12
Bounded Aggregation in Markovian Networks
Balsamo, S., & Pandolfi, B. (1987) · Cited by 7
Analysis of Large Markovian Models by Parts. Applications to Queueing Network Models
Courtois, P.-J. (1985) · Springer eBooks · doi:10.1007/978-3-642-87472-7_1 · Cited by 6
Mattingly, R. B., & Meyer, C. D. (1988) · Cited by 2
Self-citation
Research works printed but not linked: 3
- Balsamo S., 1988, Computer performance and reliability (Rome, 1987), 73
- Courtois P.-J., 1977, Decomposability
- Gantmacher F. R., 1960, Matrix Theory—Vol. II
Cited by
1Kron Reduction of Graphs with Applications to Electrical Networks
Bullo, F. (2015) · Cited by 821
Graph Clustering Via a Discrete Uncoupling Process
Van Dongen, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040608635 · Cited by 750
Robust Perron cluster analysis in conformation dynamics
Deuflhard, P., & Weber, M. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.10.026 · Cited by 506
Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification
Röblitz, S., & Weber, M. (2013) · Advances in Data Analysis and Classification · doi:10.1007/s11634-013-0134-6 · Cited by 371
“Such Markov chains are also known as nearly completely decomposable or nearly reducible Markov chains, see Courtois (1977), Stewart (1984), Meyer (1989).”
BackgroundIdentification of almost invariant aggregates in reversible nearly uncoupled Markov chains
Deuflhard, P., Huisinga, W., Fischer, A., & Schütte, C. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00095-1 · Cited by 319
Metadata
- Authors
- Meyer, C. D.
- Corresponding author
- Meyer, Carl D.
- Venue
- SIAM Review
- Published
- 1989-06
- Volume
- 31
- Issue
- 2
- Pages
- 240-272
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2042624802
- Cited by
- 316
- References
- 21
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 3 · 2023: 4 · 2022: 7 · 2021: 14 · 2020: 17 · 2019: 12 · 2018: 6 · 2017: 14 · 2016: 8 · 2015: 8 · 2014: 9 · 2013: 15 · 2012: 18
- FWCI
- 3.53
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Mathematics › Mathematical Physics › Mathematical Dynamics and Fractals
- Keywords
- finite Markov chains, Markov chain decomposition, 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.