A general framework for aggregation/disaggregation methods for large Markov chains
Halim Daoud Kafeety · 1992
Aggregation/disaggregation methods are an important class of algorithm which is used to compute the stationary probabilities of large-scale Markov chains. For Markov chains which are nearly uncoupled, iterative aggregation/disaggregation techniques can often result in sequences which converge at surprisingly rapid rates. But due to the variety of ways in which iterative aggregation/disaggregation methods are designed and implemented, it is generally necessary to analyze each algorithm in isolation, and it can be difficult to compare similarities and differences. The purpose of this study is to help overcome this situation by presenting a general framework for iterative aggregation/disaggregation algorithms which can be used to analyze and compare different and rather general algorithms from the class. We will demonstrate how several of the important well-known algorithms fit within this general framework. Several examples are given in order to compare the relative effectiveness of these algorithms.