The accurate computation of key properties of Markov and semi-Markov Processes

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 fi nding the mean fi rst passage times (MFPTs) (or absorption probabilities) in semi-Markov processes. The method is numerically stable as it doesn't involve subtraction. It works well for focussing 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 a refinement of the Kohlas algorithm which we specialise to the case of Markov chains 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. A comparison, using some test problems from the literature, with other techniques using generalised matrix inverses is 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., A Markov partitioning algorithm for computing steady state probabilities, Oper. Res. 33 (1985), 228-235. [3] Kohlas J. Numerical computation of mean fi rst passage times and absorption probabilities in Markov and semi-Markov models, Zeit fur Oper Res, 30, (1986), 197-207