loading...
Limiting Behavior of Markov Chains with Eager Attractors
Riverside, California September 11-September 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/QEST.2006.24Third International Conference on the ...
 This Article 
 
PDF
HTML
IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Parosh Aziz Abdulla, Uppsala University, Sweden
Noomene Ben Henda, Uppsala University, Sweden
Richard Mayr, NC State University, USA.
Sven Sandberg, Uppsala University, Sweden
We consider discrete infinite-state Markov chains which contain an eager finite attractor. A finite attractor is a finite subset of states that is eventually reached with probability 1 from every other state, and the eagerness condition requires that the probability of avoiding the attractor in n or more steps after leaving it is exponentially bounded in n. Examples of such Markov chains are those induced by probabilistic lossy channel systems and similar systems. We show that the expected residence time (a generalization of the steady state distribution) exists for Markov chains with eager attractors and that it can be effectively approximated to arbitrary precision. Furthermore, arbitrarily close approximations of the limiting average expected reward, with respect to state-based bounded reward functions, are also computable.
Citation:
Parosh Aziz Abdulla, Noomene Ben Henda, Richard Mayr, Sven Sandberg, "Limiting Behavior of Markov Chains with Eager Attractors," qest, pp.253-264, Third International Conference on the Quantitative Evaluation of Systems - (QEST'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.