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

Abstract

The aggregation-disaggregation algorithm of Takahashi (1975) is a rank-reduction method for efficiently computing ergodic probabilities of large Markov chains. It has been shown by Schweitzer (1984) that if a Markov chain is “exactly lumpable”, then the aggregation-disaggregation algorithm converges in one step. In this paper, we 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.