Iterative Algorithms for Large Stochastic Matrices

Markov chains have always constituted an efficient tool to model discrete systems. Many performance criteria for discrete systems can be derived from the steady-state probability vector of the associated Markov chain. However, the large size of the state space of the Markov chain often allows this vector to be determined by iterative methods only. Various iterative methods exist, but none can be proved a priori to be the best. In this paper, we propose a practical measure which allows the convergence rate of the various existing methods to be compared. This measure is an approximation of the modulus of the second largest eigenvalue of the iteration matrix and can be determined a priori. The model of a queueing network is used as an example to compare the convergence of several iterative methods and to show the accuracy of the measure