Lumpability and time reversibility in the aggregation-disaggregation method for large Markov chains

The aggregation-disaggregation algorithm of Takahashi is a rank-reduction method for efficiently computing ergodic probabilities of large Markov chains. It has been shown by Schweitzer that if a Markov chain is ‘exactly lumpable’, then the aggregation-disaggregation algorithm converges in one step. In this paper, the authors show that ordinary lumpability eliminates the aggregation procedure. Furthermore, a new algorithm is developed which produces the ergodic probability vector in one step for a class of Markov chains including the time reversible ones. The idea behind the new algorithm enables one to develop different algorithms for different classes of Markov chains. A preliminary study along this line of research is also discussed.