APPLICATION OF THE REPLACEMENT PROCESS APPROACH FOR COMPUTING THE ERGODIC PROBABILITY VECTOR OF LARGE SCALE ROW-CONTINUOUS MARKOV CHAINS
Ushio Sumita, Maria Rieders · Journal of the Operations Research Society of Japan · 1990
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 general, the algorithm involves the computation of inverse matrices of size M - 1. Because of the skip free structure of row-continuous Markov chains, however, replacement distributions for these Markov chains can be constructed explicitly without involving any inverse matrices. The purpose of this paper is to develop an algorithm for computing the ergodic probability vector for row-continuous Markov chains based on the replacement process approach. Relevance to Takahashi's modified aggregation-disaggregation algorithm is also discussed. When successive substitution is employed for solving systems of linear equations, extensive numerical experiments suggest that both the replacement process algorithm and the ordinary aggregation-disaggregation algorithm dominate the modified aggregation-disaggregation algorithm. Furthermore, the replacement process algorithm outperforms the ordinary aggregation-disaggregation algorithm as both state space size and density of the underlying matrices increase.