Aggregation in large-scale Markov chains.
David Sungsup Kim · Deep Blue (University of Michigan) · 1990
Markov chains are frequently used to model complex stochastic systems. Unfortunately the state space for these models is often prohibitively large, making the computation of the stationary probabilities impractical in terms of storage and computation time. In this thesis certain probability transition matrix structures, encountered in the Markov chain aggregation/disaggregation literature, are identified. Efficient exact and iterative aggregation/disaggregation algorithms for computing the stationary probabilities of some of these specially structured Markov chains are developed. The exact algorithms are applicable to Markov chains for which it is possible to partition the states into sets such that when each set is entered, a transition must pass through a state contained in a fixed subset (the mandatory set) of the set. The conditional stationary probabilities of the states in the mandatory set, given that the system must be in some state in the mandatory set, are assumed to be known. The iterative algorithm is applicable to Markov chains with finite generalized birth-death or row continuous structure. The global convergence of this algorithm for most real Markov chain applications with generalized birth-death structure is proved. A key to the development of the algorithms, and to proving convergence of the iterative algorithm, is the identification of additional Markov chains associated with the original Markov chain. The information or convergence properties of these additional Markov chains is then used in the algorithms.