Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

BBS-ipl06

C. Baier, N. Bertrand, Ph. Schnoebelen. A note on the attractor-property of infinite-state Markov chains. Information Processing Letters, 97(2):58-63, January 2006.

Download [help]

Download paper: Doi page

Download paper: Adobe portable document (pdf) pdf

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n>0 is less than n-Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/

BibTex Reference

@article{BBS-ipl06,
   Author = {Baier, C. and Bertrand, N. and Schnoebelen, Ph.},
   Title = {A note on the attractor-property of infinite-state {M}arkov chains},
   Journal = {Information Processing Letters},
   Volume = {97},
   Number = {2},
   Pages = {58--63},
   Publisher = {Elsevier Science Publishers},
   Month = {January},
   Year = {2006}
}

EndNote Reference [help]

Get EndNote Reference (.ref)