Reduced System Algorithms for Markov Chains

A reduced system is a smaller system derived in the process of analyzing a larger system. In solving for steady state probabilities of a Markov chain, generally the solution can be found by first solving a reduced system of equations which is obtained by appropriately partitioning the transition probability (or rate) matrix. Following Lal (Lal, R. 1981. A unified study of algorithms for steady state probabilities in Makov chains. Ph.D. Dissertation, Department of Operations Research and Engineering Management, School of Engineering and Applied Sciences, Southern Methodist University, Dallas, TX 75275.), a Markov chain can be categorized as standard or nonstandard depending on the location of an invertible submatrix necessary for an efficient solution in a transition probability (or rate) matrix. In this paper, algorithms for the determination of steady state probabilities are developed by using (i) a backward recursion which is efficient for standard systems and (ii) a forward recursion which is efficient for nonstandard systems. It is also shown that the backward recursion can be used for finding the first passage time distribution and its mean and variance.