×

Accurate calculations of stationary distributions and mean first passage times in Markov renewal processes and Markov chains. (English) Zbl 1334.60144

Summary: This article describes an accurate procedure for computing the mean first passage times of a finite irreducible Markov chain and a Markov renewal process. The method is a refinement to the procedure of J. Kohlas [Z. Oper. Res., Ser. A 30, 197–207 (1986; Zbl 0618.90094)]. The technique is numerically stable in that it doesn’t involve subtractions. Algebraic expressions for the special cases of one, two, three and four states are derived. A consequence of the procedure is that the stationary distribution of the embedded Markov chain does not need to be derived in advance but can be found accurately from the derived mean first passage times. MatLab is utilized to carry out the computations, using some test problems from the literature.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60K15 Markov renewal processes, semi-Markov processes
60J22 Computational methods in Markov chains
65C40 Numerical analysis or methods applied to Markov chains

Citations:

Zbl 0618.90094

Software:

LDQBD; Matlab
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [1] Benzi, M. A direct projection method for Markov chains. Linear Algebra Appl, 386, (2004), 27-49.; · Zbl 1062.65011
[2] Bini, D. A., Latouche, G. and Meini B. Numerical Methods for Structured Markov Chains, Oxford University Press, New York. (2005).; · Zbl 1076.60002
[3] Dayar, T. and Akar, N. Computing the moments of first passage times to a subset of states in Markov chains. SIAM J Matrix Anal Appl, 27, (2005), 396-412.; · Zbl 1094.60051
[4] Grassman,W.K., Taksar, M.I., and Heyman, D.P. Regenerative analysis and steady state distributions forMarkov chains. Oper Res, 33, (1985), 1107-1116.; · Zbl 0576.60083
[5] Harrod,W.J. and Plemmons, R.J. Comparison of some direct methods for computing stationary distributions ofMarkov chains. SIAM J Sci Stat Comput, 5, (1984), 463-479.; · Zbl 0574.65147
[6] Heyman, D.P. Further comparisons of direct methods for computing stationary distributions ofMarkov chains. SIAM J Algebra Discr, 8, (1987), 226-232.; · Zbl 0625.65150
[7] Heyman, D.P. and O’Leary, D.P.What is fundamental forMarkov chains: First Passage Times, Fundamentalmatrices, and Group Generalized Inverses, Computations with Markov Chains, Chap 10, 151-161, Ed W.J. Stewart, Springer. New York, (1995).;
[8] Heyman, D.P. and Reeves, A. Numerical solutions of linear equations arising inMarkov chain models. ORSA J Comp, 1, (1989), 52-60.; · Zbl 0757.65156
[9] Hunter, J.J. Generalized inverses and their application to applied probability problems. Linear Algebra Appl, 46, (1982), 157- 198.; · Zbl 0493.15003
[10] Hunter, J.J. Mathematical Techniques of Applied Probability, Volume 2, Discrete Time Models: Techniques and Applications, Academic, New York. (1983).; · Zbl 0539.60065
[11] Hunter, J.J. Mixing times with applications to Markov chains, Linear Algebra Appl, 417, (2006), 108-123.; · Zbl 1099.60048
[12] Kemeny, J. G. and Snell, J. L. Finite Markov chains, Springer- Verlag, New York (1983), (Original version, Princeton University Press, Princeton (1960).); · Zbl 0089.13704
[13] Kohlas, J. Numerical computation of mean passage times and absorption probabilities in Markov and semi-Markov models. Zeit Oper Res, 30, (1986), 197-207.; · Zbl 0618.90094
[14] Meyer. C. D. Jr. The role of the group generalized inverse in the theory of Markov chains. SIAM Rev, 17, (1975), 443-464.; · Zbl 0313.60044
[15] Sheskin, T.J. A Markov partitioning algorithm for computing steady state probabilities. Oper Res, 33, (1985), 228-235.; · Zbl 0569.90092
[16] Stewart, W. J. Introduction to the Numerical Solution of Markov chains. Princeton University Press, Princeton. (1994).; · Zbl 0821.65099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.