%0 Journal Article 
%F BBS-ipl06
%A Baier, C.
%A Bertrand, N.
%A Schnoebelen, Ph.
%T A note on the attractor-property of infinite-state {M}arkov chains
%J Information Processing Letters
%V 97
%N 2
%P 58-63
%I Elsevier Science Publishers
%X 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
%U http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/IPL-BBS.pdf
%U http://dx.doi.org/10.1016/j.ipl.2005.09.011
%8 January
%D 2006