Reduction of absorbing Markov chain

Mariusz Górajski

Annales UMCS, Mathematica (2009)

  • Volume: 63, Issue: 1, page 91-107
  • ISSN: 2083-7402

Abstract

top
In this paper we consider an absorbing Markov chain with finite number of states. We focus especially on random walk on transient states. We present a graph reduction method and prove its validity. Using this method we build algorithms which allow us to determine the distribution of time to absorption, in particular we compute its moments and the probability of absorption. The main idea used in the proofs consists in observing a nondecreasing sequence of stopping times. Random walk on the initial Markov chain observed exclusively in the stopping times τ1, τ2, … is equivalent to some new Markov chain.

How to cite

top

Mariusz Górajski. "Reduction of absorbing Markov chain." Annales UMCS, Mathematica 63.1 (2009): 91-107. <http://eudml.org/doc/267705>.

@article{MariuszGórajski2009,
abstract = {In this paper we consider an absorbing Markov chain with finite number of states. We focus especially on random walk on transient states. We present a graph reduction method and prove its validity. Using this method we build algorithms which allow us to determine the distribution of time to absorption, in particular we compute its moments and the probability of absorption. The main idea used in the proofs consists in observing a nondecreasing sequence of stopping times. Random walk on the initial Markov chain observed exclusively in the stopping times τ1, τ2, … is equivalent to some new Markov chain.},
author = {Mariusz Górajski},
journal = {Annales UMCS, Mathematica},
keywords = {Absorbing Markov chain; distribution of time to absorption; absorbing Markov chain},
language = {eng},
number = {1},
pages = {91-107},
title = {Reduction of absorbing Markov chain},
url = {http://eudml.org/doc/267705},
volume = {63},
year = {2009},
}

TY - JOUR
AU - Mariusz Górajski
TI - Reduction of absorbing Markov chain
JO - Annales UMCS, Mathematica
PY - 2009
VL - 63
IS - 1
SP - 91
EP - 107
AB - In this paper we consider an absorbing Markov chain with finite number of states. We focus especially on random walk on transient states. We present a graph reduction method and prove its validity. Using this method we build algorithms which allow us to determine the distribution of time to absorption, in particular we compute its moments and the probability of absorption. The main idea used in the proofs consists in observing a nondecreasing sequence of stopping times. Random walk on the initial Markov chain observed exclusively in the stopping times τ1, τ2, … is equivalent to some new Markov chain.
LA - eng
KW - Absorbing Markov chain; distribution of time to absorption; absorbing Markov chain
UR - http://eudml.org/doc/267705
ER -

References

top
  1. Billingsley, P., Probability and Measure, John Wiley & Sons, New York, 1979. Zbl0411.60001
  2. Chandrasekharan, M. P., Madhusudanan Pillai, V., An absorbing Markov chain model for production systems with rework and scrapping, Computers and Industrial Engineering 55, Issue 3 (2008), 695-706. 
  3. Engel, A., The probabilistic abacus, Educational Studies in Mathematics 6 (1975), 1-22. Zbl0303.60056
  4. Engel, A., Why does the probabilistic abacus work?, Educational Studies in Mathematics 7 (1976), 59-56. Zbl0338.60041
  5. Feller, W., An Introduction to Probability Theory and Its Applications, John Wiley & Sons, New York, 1968. Zbl0155.23101
  6. Gosselin, F., Asymptotic behavior of absorbing Markov chains conditional on nonabsorption for application in conservation biology, Ann. Appl. Probab. 11, no. 1 (2001), 261-284. Zbl1019.60082
  7. Iosifescu, M., Finite Markov Processes and Their Applications, John Wiley & Sons, Chichester, 1980. Zbl0436.60001
  8. Kemeny, J. G., Snell, J. L., Finite Markov Chain, D. Van Nostrand, Princeton, 1960. 
  9. Keming Gu, Sadiku, M. N. O., Absorbing Markov chain solution for Possion's equation, Southeastcon 2000. Proceedings of the IEEE (2000), 297-300. 
  10. Norris, J. R., Markov Chain, Cambridge University Press, Cambridge, 1997. 
  11. Płocki, A., Introduction to probability calculus and mathematical statistics for teachers, Propedeutyka rachunku prawdopodobieństwa i statystyki matematycznej dla nauczycieli, PWN, Warszawa 1992 (Polish). 
  12. Swan, Y. C., Bruss, F. T., A matrix-analytic approach to the N-player ruin problem, J. Appl. Probab. 43, no. 3 (2006), 755-766. Zbl1137.60035

NotesEmbed ?

top

You must be logged in to post comments.