论文部分内容阅读
Based upon the Grassman, Taksar and Heyman algorithm [1] and the equivalent Sheskin State Reduction algorithm [2] for finding the stationary distribution of a finite irreducible Markov chain, Kohlas [3] developed a procedure for finding the mean first passage times (MFPTs) (or absorption probabilities) in Markov renewal processes. The method is numerically stable as it doesnt involve subtraction. It works well for focusing on the MFPTs from any state to a fixed state but it is not ideally suited for a global expression for the MFPT matrix. We present some refinements to the Kohlas algorithm that we specialize to the case of Markov chains. We utilise MatLab to find expressions for the MFPT matrix. A consequence of our procedure is that the stationary distribution does not need to be derived in advance but is found from the MFPTs. This also leads to an expression for the group inverse of I-P where P is the transition matrix of the embedded Markov chain. Some comparisons, using some test problems from the literature, with other techniques using generalized matrix inverses and perturbation techniques are also presented. References: [1] Grassman W.K., Taksar M.I., and Heyman D.P., Regenerative analysis and steady state distributions for Markov chains, Oper. Res. 33, (1985), 1107-1116. [2] Sheskin T.J., AMarkov partitioning algorithm for computing steady state probabilities, Oper. Res. 33 (1985), 228-235. [3] Kohlas J. Numerical computation of mean first passage times and absorption probabilities in Markov and semi-Markov models, Zeit fur Oper Res, 30, (1986), 197-207.