A note on the attractor-property of infinite-state Markov chains

Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Philippe SchnoebelenPhilippe Schnoebelen

DOI Link

Christel Baier, Nathalie Bertrand, Philippe Schnoebelen
A note on the attractor-property of infinite-state Markov chains
Information Processing Letters, 97(2):58--63, 2006

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@article{BBS2006,
  author  = {Christel Baier and Nathalie Bertrand and Philippe Schnoebelen},
  title   = {A note on the attractor-property of infinite-state Markov chains},
  journal = {Information Processing Letters},
  volume  = {97},
  number  = {2},
  year    = {2006},
  pages   = {58--63},
  doi     = {10.1016/J.IPL.2005.09.011}
}