Accurate calculations of Stationary Distributions and Mean First Passage Times in Markov Renewal Processes and Markov Chains

Jeffrey J. Hunter

Special Matrices (2016)

  • Volume: 4, Issue: 1, page 151-175
  • ISSN: 2300-7451

Abstract

top
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 Kohlas, Zeit fur Oper Res, 30, 197–207, (1986) procedure. 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.Aconsequence 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.

How to cite

top

Jeffrey J. Hunter. "Accurate calculations of Stationary Distributions and Mean First Passage Times in Markov Renewal Processes and Markov Chains." Special Matrices 4.1 (2016): 151-175. <http://eudml.org/doc/276438>.

@article{JeffreyJ2016,
abstract = {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 Kohlas, Zeit fur Oper Res, 30, 197–207, (1986) procedure. 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.Aconsequence 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.},
author = {Jeffrey J. Hunter},
journal = {Special Matrices},
keywords = {Markov chain; Markov renewal process; stationary distribution; mean first passage times; Markov chains},
language = {eng},
number = {1},
pages = {151-175},
title = {Accurate calculations of Stationary Distributions and Mean First Passage Times in Markov Renewal Processes and Markov Chains},
url = {http://eudml.org/doc/276438},
volume = {4},
year = {2016},
}

TY - JOUR
AU - Jeffrey J. Hunter
TI - Accurate calculations of Stationary Distributions and Mean First Passage Times in Markov Renewal Processes and Markov Chains
JO - Special Matrices
PY - 2016
VL - 4
IS - 1
SP - 151
EP - 175
AB - 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 Kohlas, Zeit fur Oper Res, 30, 197–207, (1986) procedure. 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.Aconsequence 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.
LA - eng
KW - Markov chain; Markov renewal process; stationary distribution; mean first passage times; Markov chains
UR - http://eudml.org/doc/276438
ER -

References

top
  1. [1] Benzi, M. A direct projection method for Markov chains. Linear Algebra Appl, 386, (2004), 27–49.  Zbl1062.65011
  2. [2] Bini, D. A., Latouche, G. and Meini B. Numerical Methods for Structured Markov Chains, Oxford University Press, New York. (2005).  Zbl1076.60002
  3. [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. [Crossref] Zbl1094.60051
  4. [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.  Zbl0576.60083
  5. [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.  Zbl0574.65147
  6. [6] Heyman, D.P. Further comparisons of direct methods for computing stationary distributions ofMarkov chains. SIAM J Algebra Discr, 8, (1987), 226–232. [Crossref] Zbl0625.65150
  7. [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. [8] Heyman, D.P. and Reeves, A. Numerical solutions of linear equations arising inMarkov chain models. ORSA J Comp, 1, (1989), 52–60.  Zbl0757.65156
  9. [9] Hunter, J.J. Generalized inverses and their application to applied probability problems. Linear Algebra Appl, 46, (1982), 157– 198. [Crossref] Zbl0493.15003
  10. [10] Hunter, J.J. Mathematical Techniques of Applied Probability, Volume 2, Discrete Time Models: Techniques and Applications, Academic, New York. (1983).  Zbl0539.60065
  11. [11] Hunter, J.J. Mixing times with applications to Markov chains, Linear Algebra Appl, 417, (2006), 108–123. [WoS] Zbl1099.60048
  12. [12] Kemeny, J. G. and Snell, J. L. Finite Markov chains, Springer- Verlag, New York (1983), (Original version, Princeton University Press, Princeton (1960).)  Zbl0089.13704
  13. [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.  Zbl0618.90094
  14. [14] Meyer. C. D. Jr. The role of the group generalized inverse in the theory of Markov chains. SIAM Rev, 17, (1975), 443–464. [Crossref] Zbl0313.60044
  15. [15] Sheskin, T.J. A Markov partitioning algorithm for computing steady state probabilities. Oper Res, 33, (1985), 228–235.  Zbl0569.90092
  16. [16] Stewart, W. J. Introduction to the Numerical Solution of Markov chains. Princeton University Press, Princeton. (1994).  Zbl0821.65099

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.