Generalized partitioning algorithm for computing steady-state probability vectors of finite Markov chains with comparison to the CFTP algorithm

Abstract

In this paper we propose a generalization of the basic partitioning algorithm proposed by T.J. Sheskin for computing steady state probability vector of a finite Markov chain. This algorithm generates an exact solution for steady state probabilities for any finite, irreducible Markov chain. Theoretically there is no imposed limit on the size of the Markov chain for which steady state probabilities can be obtained, but in practice, the method will produce round off errors. we propose to generalize the partitioning technique to cover all possible variants of the Sheskin algorithm. Our proposal, besides being a mathematical curiosity, it gives answer to several possible modifications (variations) suggested, by the author of this algorithm. In the numerical part we compared our generalization with standard CFTP algorithm.