Numerical Comparison of the Replacement Process Approach with the Aggregation-Disaggregation Algorithm for Row-Continuous Markov Chains*
Ushio Sumita, Maria Rieders · 2021
In a recent paper by Sumita and Rieders (1990) , a new algorithm has been developed for computing the ergodic probability vector for large Markov chains. Decomposing the state space into M lumps, the algorithm generates a sequence of replacement processes on individual lumps in such a way that in the limit the ergodic probability vector for a replacement process on one lump will be proportional to the ergodic probability vector of the original Markov chain restricted to that lump. In a sequel to the original paper by the same authors, this idea is applied to row-continuous Markov chains, where the underlying skip-free structure enables one to construct the replacement distributions explicitly without involving any inverse matrices. This paper discusses the numerical study of the replacement process approach for such 288 chains in comparison with Takahashi’s modified aggregation-disaggregation algorithm and a modification of Van der Heyden’s algorithm. When successive substitution is employed as a means to solve systems of linear equations involved in either algorithm, the extensive numerical experiments suggest that the replacement process approach is more efficient than Takahashi’s modified algorithm by a factor of three to five. Furthermore, the efficiency gap increases as the size of the Markov chain increases.