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

Hunter, JJ
Item type
Conference Contribution
Degree name
Journal Title
Journal ISSN
Volume Title
The University of Melbourne

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.

8th Australia New Zealand Mathematics Convention held at University of Melbourne, Melbourne, Australia, 2014-12-08 to 2014-12-12
Rights statement
NOTICE: this is the author’s version of a work that was accepted for publication. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in (see Citation).