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.