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.”
Background
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
Items 101–200 of 310
Collaboration of discrete-time Markov chains: Tensor and product form
Fourneau, J. (2010) · Performance Evaluation · doi:10.1016/j.peva.2010.01.008 · Cited by 13
Block triangular preconditioners for M-matrices and Markov chains
Michele Benzi, A., & Uçar, B. (2007) · Cited by 13
Preemption rates for a parallel link loss network
Zhao, Z. W., Weber, S. P., & de Oliveira, J. C. (2008) · Performance Evaluation · doi:10.1016/j.peva.2008.07.002 · Cited by 13
USING MARKOV CHAIN AND GRAPH THEORY CONCEPTS TO ANALYZE BEHAVIOR IN COMPLEX DISTRIBUTED SYSTEMS
Dabrowski, C., & Hunt, F. Y. (2011) · Cited by 13
Computing mean first passage times for a Markov chain
Sheskin, T. J. (1995) · International Journal of Mathematical Education in Science and Technology · doi:10.1080/0020739950260510 · Cited by 13
On the Kemeny constant and stationary distribution vector for a Markov chain
Kirkland, S. (2014) · Electronic Journal of Linear Algebra · doi:10.13001/1081-3810.1624 · Cited by 13
A combined approach for evaluating papers, authors and scientific journals
Bini, D. A., Corso, G. M. D., & Romani, F. (2010) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2010.02.003 · Cited by 13
Simon?Ando decomposability and fitness landscapes
Shpak, M., Stadler, P., Wagner, G. P., & Altenberg, L. (2004) · Theory in Biosciences · doi:10.1016/j.thbio.2004.04.001 · Cited by 17
Krishnamurthy, V. (1994) · International Journal of Adaptive Control and Signal Processing · doi:10.1002/acs.4480080303 · Cited by 13
Performance Modelling and Markov Chains
Stewart, W. J. (2007) · Springer eBooks · doi:10.1007/978-3-540-72522-0_1 · Cited by 15
“Completely Decomposable, as the partitions are chosen based on how strongly the states of the Markov chain interact with one another, [18, 45 ].”
Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs
Epasto, A., Feldman, J., Lattanzi, S., Leonardi, S., & Mirrokni, V. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2568025 · Cited by 15
“So we cannot apply directly the results in the Markov chain state aggregation theory [26] as they rely on the disjointness of the sets of states aggregated.”
BackgroundMethodInfluentialA survey on distributed approaches to graph based reputation measures
Avrachenkov, K. E., Nemirovsky, D., & Pham, K. (2007) · Performance Evaluation Methodolgies and Tools · doi:10.5555/1345263.1345370 · Cited by 13
Optimal bulking threshold of batch service queues
Zeng, Y., & Xia, C. H. (2017) · Journal of Applied Probability · doi:10.1017/jpr.2017.8 · Cited by 12
A multiscale environment for learning by diffusion
Murphy, J. M., & Polk, S. L. (2021) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2021.11.004 · Cited by 12
Analysing ill-conditioned Markov chains
Woods, E. J., Kannan, D., Sharpe, D., Swinburne, T. D., & Wales, D. J. (2023) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2022.0245 · Cited by 12
“In this contribution, we employ GT [45] as the state reduction technique, using a recent implementation (block GT) that enables the removal of multiple states [27,34,45,58–61].”
MethodResultPassive Crowd Speed Estimation in Adjacent Regions With Minimal WiFi Sensing
Depatla, S., & Mostofi, Y. (2019) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2019.2924629 · Cited by 12
“stationary distribution of the partitioned transition matrix P is shown in [34] to be g 1⁄4 1⁄2k1g1 k2g2 , where k1 and k2 are constants, and g1 and g2 are the stationary distribution vectors corresponding to the probability transition”
BackgroundMulticlass Multiserver Threshold-Based Systems: A Study of Noninstantaneous Server Activation
Chou, C., Golubchik, L., & Lui, J. C. S. (2006) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2007.253284 · Cited by 11
Real-Time Automated Hazard Detection Framework for Health Information Technology Systems
Omitaomu, O. A., Özmen, Ö., Olama, M. M., Pullum, L., Kuruganti, T. P., Nutaro, J. J., Klasky, H. B., Zandi, H., Advani, A. A., Laurio, A., et al. (2019) · Health Systems · doi:10.1080/20476965.2019.1599701 · Cited by 12
“Perturbation analysis of DTMCs has been extensively studied in theoretical literature (e.g., Schweitzer, 1968; Delebecque, 1983; Hassin & Haviv, 1992) and computational literature (e.g., Meyer, 1989; Stewart & Dekker, 1994; Ho & Li, 1988; Suri, 1989; Cao & Zhang, 2008; Dabrowski & Hunt, 2009).”
BackgroundKirkland, S. J., Neumann, M., & Xu, J. (2001) · Numerical Linear Algebra with Applications · doi:10.1002/nla.242 · Cited by 11
“Meyer [5, 6] has addressed the problem of computing the stationary distribution vector for a Markov chain via a divide and conquer approach.”
BackgroundBounding stationary results of Tandem networks with MAP input and PH service time distributions
Buchholz, P. (2006) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/1140103.1140300 · Cited by 11
Pekergin, N., Dayar, T., & Alparslan, D. N. (2004) · European Journal of Operational Research · doi:10.1016/j.ejor.2001.09.001 · Cited by 11
“The conditional steady state probability vector of the ith NCD partition is pi=kpik1, and it may be computed by solving for the steady state vector of P i;i (see [12] for details).”
BackgroundInfluentialA survey on distributed approaches to graph based reputation measures
Avrachenkov, K. E., Nemirovsky, D., & Pham, K. S. (2007) · International ICST Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS) · doi:10.4108/smctools.2007.2027 · Cited by 11
Betz, V., & Roux, S. L. (2016) · Stochastic Processes and their Applications · doi:10.1016/j.spa.2016.05.003 · Cited by 19
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 12
Using Reference Groups to Assess Academic Productivity in Computer Science
Ribas, S., Ribeiro-Neto, B. A., Silva, E. D. S. E., Ueda, A., & Ziviani, N. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2740908.2741735 · Cited by 10
Random Walks on Complex Modular Networks
Djurdjevac, N., Bruckner, S., Conrad, T., & Schütte, C. (2012) · Cited by 13
Architecture-level reliability prediction of concurrent systems
Cheung, L., Krka, I., Golubchik, L., & Medvidović, N. (2012) · ACM/SPEC International Conference on Performance Engineering (ICPE) · doi:10.1145/2188286.2188305 · Cited by 10
“where pi(j, k) is the probability that Scenk executes after the execution of Scenj , and outj is defined in a similar manner to [18]:”
BackgroundMethodInfluentialTOPOLOGICAL VERSUS DYNAMICAL ROBUSTNESS IN A LEXICAL NETWORK
Borge‐Holthoefer, J., Moreno, Y., & Arenas, À. (2012) · International Journal of Bifurcation and Chaos · doi:10.1142/s021812741250157x · Cited by 14
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
On single and double Soules matrices
Chen, M. Q., Han, L., & Neumann, M. (2006) · Linear Algebra and its Applications · doi:10.1016/j.laa.2005.08.021 · Cited by 10
“is called the Perron complement of A1,1 in A. We comment that although Perron complements are closely related to Schur complements, the subject and utility of Perron complements, particularly in the context of Markov chains, seems to have originated from two papers of Meyer, see [18, 19 ].”
BackgroundMining Online Music Listening Trajectories.
Figueiredo, F., Ribeiro, B., Faloutsos, C., Andrade, N., & Almeida, J. M. (2016) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.1417274 · Cited by 9
Taxonomy-driven lumping for sequence mining
Bonchi, F., Castillo, C., Donato, D., & Gionis, A. (2009) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-009-0141-6 · Cited by 9
State Aggregations in Markov Chains and Block Models of Networks
Faccin, M., Schaub, M. T., & Delvenne, J. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.078301 · Cited by 11
“[4] Carl D Meyer.”
Spectral Early-Warning Signals for Sudden Changes in Time-Dependent Flow Patterns
Ndour, M., Padberg‐Gehle, K., & Rasmussen, M. (2021) · Fluids · doi:10.3390/fluids6020049 · Cited by 9
“Robustness can also be shown analytically by using results from the perturbation theory of reversible Markov chains [30,31] and has also been studied numerically in example systems [32].”
BackgroundA Non-homogeneous QBD Approach for the Admission and GoS Control in a Multiservice WCDMA System
Koukoutsidis, I., Altman, E., & Kélif, J.-M. (2005) · Lecture notes in computer science · doi:10.1007/11499169_26 · Cited by 9
“The algorithm is similar to later introduced stochastic complementation methods [ 18 ] and consists of the following steps:”
MethodEfficient solution for a class of Markov chain models of telecommunication systems
Meo, M., Silva, E. D. S. E., & Marsan, M. A. (1996) · Performance Evaluation · doi:10.1016/s0166-5316(96)90048-6 · Cited by 9
Effects of Reordering and Lumping in the Analysis of Discrete-Time SANs
Dayar, T. (2000) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8405-1_18 · Cited by 8
Sharma, M. K., Murthy, C. R., & Vaze, R. (2018) · IEEE Transactions on Communications · doi:10.1109/tcomm.2018.2879926 · Cited by 8
A Matrix Pattern Compliant Strong Stochastic Bound
Bušić, A., & Fourneau, J.-M. (2006) · Symposium on Applications and the Internet Workshops (SAINT Workshops) · doi:10.1109/saintw.2005.1620024 · Cited by 8
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
Complementation in Stochastic Matrices and the GTH Algorithm
Seneta, E. B. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896310172 · Cited by 8
Component-Driven Regime-Switching Volatility
Fleming, J., & Kirby, C. (2012) · Journal of Financial Econometrics · doi:10.1093/jjfinec/nbs023 · Cited by 8
Valuation of the effects of intersymbol interference in decision-feedback equalizers
Willink, T. J., Wittke, P. H., & Campbell, L. L. (2000) · IEEE Transactions on Communications · doi:10.1109/26.843130 · Cited by 8
Ranking Websites: A Probabilistic View
Bao, Y., Feng, G., Liu, T., Ma, Z.-M., & Wang, Y. (2006) · Internet Mathematics · doi:10.1080/15427951.2006.10129125 · Cited by 8
“The engineering aspects of the results of this section were reported in more detail at the 29th Annual International Conference on Research and Development on Information Retrieval [Feng et al. 06].”
BackgroundNeumann, M., & Xu, J. (2003) · Numerical Linear Algebra with Applications · doi:10.1002/nla.339 · Cited by 8
“Now from Reference [5] or [6] we know that”
BackgroundMethodExact Analysis of a Class of GI/G/1-Type Performability Models
Riska, A., Smirni, E., & Ciardo, G. (2004) · IEEE Transactions on Reliability · doi:10.1109/tr.2004.829134 · Cited by 8
“While [14] introduces the concept of stochastic complementation for discrete-time Markov chains with finite state spaces, we define it instead for the infinite case, a straightforward extension, and state the results in terms of CTMC.”
BackgroundMethodInfluentialBounding of performance measures for a threshold-based queueing system with hysteresis
Golubchik, L., & Lui, J. C. S. (1997) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/258623.258684 · Cited by 8
Improving the Efficiency of Markov Chain Analysis of Complex Distributed Systems
Dabrowski, C., Hunt, F., & Morrison, K. (n.d.) · Cited by 8
Random Walks on the Reputation Graph
Ribas, S., Ribeiro-Neto, B. A., Santos, R. L. T., Silva, E. D. S. E., Ueda, A., & Ziviani, N. (2015) · ACM SIGIR International Conference on Theory of Information Retrieval (ICTIR) · doi:10.1145/2808194.2809462 · Cited by 8
“In these cases, the transition matrix P is reduced to a periodic Markov chain with the following structure: From decomposition theory [23], we can obtain values for ranking the set of reputation sources by solving: where P (cid:48) = P ST × P TS is a stochastic matrix and γ S is a row matrix with |…”
BackgroundTotal nonnegativity of the extended Perron complement
Adm, M., & Garloff, J. (2016) · Linear Algebra and its Applications · doi:10.1016/j.laa.2016.07.002 · Cited by 7
“the Perron vector of a given irreducible nonnegative matrix by using Perron complementation and a divide-and-conquer procedure are presented in [8, 9].”
MethodProduct preconditioning for Markov chain problems
Michele Benzi, A., & Uçar, B. (2006) · Cited by 7
Rogers, D. F., & PLANTE, R. D. (1993) · Computers & Operations Research · doi:10.1016/0305-0548(93)90107-t · Cited by 7
A note on generalized Perron complements of Z-matrices
Ren, Z.-G., Huang, T., & Cheng, X. (2006) · Electronic Journal of Linear Algebra · doi:10.13001/1081-3810.1217 · Cited by 7
Maximum likelihood estimation for randomized shortest paths with trajectory data
Kivimäki, I., Moorter, B. F. A. V., Panzacchi, M., Saramäki, J., & Saerens, M. (2020) · Journal of Complex Networks · doi:10.1093/comnet/cnaa024 · Cited by 7
“Aggregated Markov chains bare similarities with the study of stochastic complementation in discrete-time Markov chains [49].”
BackgroundFibrosis Protein-Protein Interactions from Google Matrix Analysis of MetaCore Network
Kotelnikova, E. A., Frahm, K. M., Shepelyansky, D. L., & Kunduzova, O. (2021) · International Journal of Molecular Sciences · doi:10.3390/ijms23010067 · Cited by 7
“In the context of Markov chains, this approach was discussed in [33].”
BackgroundTopic distillation via sub-site retrieval
Qin, T., Liu, T., Zhang, X., Feng, G., Wang, D., & Ma, W. (2006) · Information Processing & Management · doi:10.1016/j.ipm.2006.07.004 · Cited by 7
Reduced spatio-temporal complexity mmpp and image-based tracking filters for maneuvering targets
Krishnamurthy, V., & Dey, S. (2003) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2003.1261128 · Cited by 7
“Under the natural assumption that the target’s dynamics are similar when the target’s modes are similar, the underlying Markov chain has a nearly completely decomposable structure [9, 10].”
BackgroundYu, F. R., Krishnamurthy, V., & Leung, V. C. M. (2005) · Globecom · doi:10.1109/glocom.2004.1378969 · Cited by 7
“The notion of NCD [22] Markov chains can be used to reduce this to a -dimensional problem.”
Use of second order Markov chains to model digital symbol synchroniser performance
Paranchych, D. W., & Beaulieu, N. C. (1996) · IEE Proceedings - Communications · doi:10.1049/ip-com:19960740 · Cited by 7
An algorithmic and numerical approach to bound the performance of high speed networks
Mamoun, M. B., Fourneau, J., Pekergin, N., & Troubnikoff, A. (2003) · Proceedings - International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems · doi:10.1109/mascot.2002.1167098 · Cited by 7
“Meyer in [ 15 ] to uncouple Markov chains and to provide a simple approximation for steady-state.”
BackgroundMethodInfluentialImproving efficiency of markov chain analysis of complex distributed systems
Dabrowski, C., Hunt, F. Y., & Morrison, K. M. (2010) · doi:10.6028/nist.ir.7744 · Cited by 7
Asymptotic 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
Steady-state simulation of metastable stochastic chemical systems
Milias‐Argeitis, A., & Lygeros, J. (2013) · The Journal of Chemical Physics · doi:10.1063/1.4804191 · Cited by 6
“15 We show how one can simulate the Markov chain on a given subset of the state space, by “masking out” transitions to states outside this set so that the true (conditional) invariant distribution over this subset is preserved.”
BackgroundAccurate Numerical Solution for Shifted M-Matrix Algebraic Riccati Equations
Liu, C., Xue, J., & Ren-cang Li, C. (2020) · Journal of Scientific Computing · doi:10.1007/s10915-020-01263-4 · Cited by 6
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
Versatile weighting strategies for a citation-based research evaluation model
Corso, G. M. D., & Romani, F. (2009) · Bulletin of the Belgian Mathematical Society - Simon Stevin · doi:10.36045/bbms/1257776244 · Cited by 6
Basic Soules matrices and their applications
Chen, M. Q., Neumann, M., & Shaked-Monderer, N. (2006) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.09.021 · Cited by 6
“We comment that although Perron complements are closely related to Schur complements, the subject and utility of Perron complements, particularly in the context of Markov chains, seem to have originated from two papers of Meyer, see [20, 21].”
BackgroundQuick aggregation of Markov chain functionals via stochastic complementation
Doğançay, K., & Krishnamurthy, V. (2002) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1997.599548 · Cited by 6
Estimating random walk centrality in networks
Johnson, B. C., & Kirkland, S. (2019) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2019.04.009 · Cited by 6
“A result in Meyer (1989) now shows that the subvector of w corresponding to the j –th subset of the partition as well as state N is a scalar multiple of y j .”
BackgroundInfluentialRobust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Peng, P. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.179 · Cited by 5
Cowen, L., Devkota, K., Hu, X., Murphy, J. M., & Wu, K. (2021) · SIAM Journal on Mathematics of Data Science · doi:10.1137/20m1324089 · Cited by 5
On Kemeny's constant and stochastic complement
Bini, D. A., Durastante, F., Kim, S., & Meini, B. (2024) · Linear Algebra and its Applications · doi:10.1016/j.laa.2024.09.001 · Cited by 5
“In this article, we furnish a formula for Kemeny’s constant of a Markov chain by utilizing two Markov chains induced from the original, known as censored (watched) Markov chains (see [31]).”
BackgroundMethodEfficient stochastic simulation of metastable Markov chains
Milias‐Argeitis, A., & Lygeros, J. (2011) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2011.6160818 · Cited by 5
“The next two very important facts about stochastic complements from [3] form the basis of our approach: Theorem 2.”
BackgroundMethodInfluentialOn symbolic RG factorization of quasi-birth-and-death processes
Avram, F., & Chedom, D. F. (2011) · Top · doi:10.1007/s11750-011-0195-7 · Cited by 5
Asymptotic Expansions for Stationary Distributions of Nonlinearly Perturbed Semi-Markov Processes. 2
Silvestrov, D. S., & Silvestrov, S. D. (2017) · Methodology And Computing In Applied Probability · doi:10.1007/s11009-017-9607-y · Cited by 5
State reduction in a Markov decision process
Sheskin, T. J. (1999) · International Journal of Mathematical Education in Science and Technology · doi:10.1080/002073999287969 · Cited by 5
Sumita, U., & Rieders, M. (1990) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.33.279 · Cited by 5
Complexity reduction in fixed-lag smoothing for hidden Markov models
Shue, L., & Dey, S. (2002) · IEEE Transactions on Signal Processing · doi:10.1109/78.995068 · Cited by 5
“Various approaches have been put forth to derive from an aggregate version of smaller dimension, resulting in schemes of [5] approximation or even the exact distribution using stochastic complementation methods [9].”
BackgroundAn Uncoupling-Coupling Technique for Markov Chain Monte Carlo Methods
Fischer, A. (2000) · Cited by 6
Golubchik, L., & Lui, J. C. S. (2000) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/339331.339416 · Cited by 5
“As is often done in these cases, we need to look for special structure that might exist in the Markov process; specifically, we take advantage of the stochastic complementation technique [17].”
BackgroundMethodDoğançay, K. (2009) · IEEE Region 10 Conference (TENCON) · doi:10.1109/tencon.2009.5396055 · Cited by 5
“The concept of stochastic complementation [3] has been successfully applied to the aggregation of finite-state DTMCs without direct calculation of π.”
MethodDu, C., & Wong, W. H. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1610.07213 · Cited by 5
“Similar schemes that focus on reducing the state space through aggregating similar states are firstly developed to study general stochastic dynamic system (Simon and Ando, 1961; Haviv, 1987; Meyer, 1989).”
BackgroundReinterpreting Economic Complexity: A co-clustering approachPreprint
Bottai, C., Iorio, J. D., & Iori, M. (2024) · RePEc: Research Papers in Economics · doi:10.48550/arxiv.2406.16199 · Cited by 5
“However, through stochastic complementation, 37,40 it is possible to show that each random walker’s one-step transition probability P 𝑐 → 𝑐 ′ ( P 𝑝 → 𝑝 ′ ) associated with the transition matrix (cid:101) M ( (cid:98) M )—defined on the monopartite projection (cid:102) M ( (cid:99) M ) of the…”
BackgroundAsymptotic 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
LN: A Flexible Algorithmic Framework for Layered Queueing Network Analysis
Casale, G., Gao, Y., Niu, Z., & Zhu, L. (2023) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/3633457 · Cited by 4
“The handling of the latter typically relies in our solver on the stochastic complement technique that allows hiding selected transitions in a Markov chain [37]; we point to Reference [12] for more details.”
Aggregation for Computing Multi-Modal Stationary Distributions in 1-D Gene Regulatory Networks
Avcu, N., Pekergin, N., Pekergin, F., & Guzelis, C. (2017) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2017.2699177 · Cited by 4
“As a particular case, the models with the ’single entry states’ to each aggregated subset of states can be analyzed in a numerically efficient way [6], [15].”
BackgroundMethodUsing Graphics Processors for High Performance SimRank Computation
He, G., Li, C., Chen, H., Du, X., & Feng, H. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2011.91 · Cited by 4
“Since [35] brought forward the concept of nearly completely reducible (NCR) Markov chain, the iterative aggregation method has been widely exploited to applications based on NCR Markov chains, e.”
MethodEfficient Steady State Analysis of Multimodal Markov Chains
Spieler, D., & Wolf, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39408-9_27 · Cited by 4
Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization
Samanta, S. K., & Nandi, R. (2019) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2019123 · Cited by 4
Shao, J., Chen, J., & Liu, B. (2021) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2021.3108168 · Cited by 5
“To ensure the DFG is stochastic and irreducible [44], [45], we perform the following stochastic complementation step [36]: Based on the DFG, the PageRank algorithm is performed as follows [24]: where the P ð t Þ denotes the ranking result after t time iterations.”
MethodDesign of biased random walks on a graph with application to collaborative recommendation
Leleux, P., Courtain, S., Françoisse, K., & Saerens, M. (2021) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2021.126752 · Cited by 7
Utilizing hitting times for finding metastable sets in non-reversible Markov chains
Rüdrich, S., Sarich, M., & Schütte, C. (2017) · Cited by 4
Compositional Approximate Markov Chain Aggregation for PEPA Models
Milios, D., & Gilmore, S. T. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36781-6_7 · Cited by 4
“However, it is relatively easy to further reduce PeerA[10] and PeerB [20] independently.”
BackgroundMethodStewart, D. E., & Bebbington, M. (1996) · Journal of Statistical Computation and Simulation · doi:10.1080/00949659608811781 · Cited by 4
Exact algorithms for singular tridiagonal systems with applications to Markov chains
Lu, L., Ching, W., & Ng, M. K. (2003) · Applied Mathematics and Computation · doi:10.1016/j.amc.2003.10.029 · Cited by 4
Coding for Computing Irreducible Markovian Functions of Sources with MemoryPreprint
Huang, S., & Skoglund, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.5960 · Cited by 4
“Apart from classic information theoretical techniques, the key mathematical tools involved are the uncouplingcoupling technique and the concept of stochastic complement of finite-state Markov processes (see [14] for more details).”
MethodReduced-Complexity Estimation for Large-Scale Hidden Markov Models
Dey, S., & Mareels, I. (2004) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2004.826171 · Cited by 4
Global Internet public peering capacity of interconnection: a complex network analysisPreprint
Loye, J., Mouysset, S., Bruyère, M., & Jaffrès‐Runser, K. (2022) · HAL · doi:10.48550/arxiv.2206.05146 · Cited by 4
“With a novel spectral graph theory approach based on stochastic complemen-2 tation from Markov chain theory [11], we leverage the graph to approximate AS-AS traffic exchanges at a global scale.”
InfluentialStochastic Bounds for Partially Generated Markov Chains: An Algebraic Approach
Bušić, A., & Fourneau, J.-M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87412-6_17 · Cited by 3
“They are also strongly related to the theory of stochastic complement [11].”
BackgroundNormalized Cuts Are Approximately Inverse Exit Times
Gavish, M., & Nadler, B. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/110826928 · Cited by 3
“This author was partly supported by a grant from the ISF.”
Background
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.