An aggregation/disaggregation algorithm for computing the stationary distribution of a large Markov chain

A new aggregation/disaggregation iterative procedure for computing the stationary distribution of a large Markov chain is proposed. In each iteration two steps are performed. In the first, one updates approximations to the limit of the conditional probabilities of states given the subset which the chain visits. This is done by rank-one modifications of stochastic matrices each of which approximates the transition probabilities of the Markov chain resulting from observing the original chain only while in the subset under consideration. This results in a computational improvement upon existing methods in which the modification is not rank-one. In the second step, one approximates the aggregate probabilities of the subsets themselves. The paper analyses the performance of the procedure when applied to nearly uncoupled stochastic matrices. In particular, it shows that if the matrix has the degree of coupling • between subsets, then there is a reduction of O(•) in the error of the approximation at each iteration.