Title | ||
---|---|---|
Computing the expected accumulated reward and gain for a subclass of infinite markov chains |
Abstract | ||
---|---|---|
We consider the problem of computing the expected accumulated reward and the average gain per transition in a subclass of Markov chains with countable state spaces where all states are assigned a non-negative reward. We state several abstract conditions that guarantee computability of the above properties up to an arbitrarily small (but non-zero) given error. Finally, we show that our results can be applied to probabilistic lossy channel systems, a well-known model of processes communicating through faulty channels. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11590156_30 | FSTTCS |
Keywords | Field | DocType |
faulty channel,non-negative reward,average gain,lossy channel system,infinite markov chain,well-known model,markov chain,guarantee computability,abstract condition,countable state space,state space | Discrete mathematics,Countable set,Lossy compression,Markov chain,Markov decision process,Communication channel,Computability,Probabilistic logic,State space,Mathematics | Conference |
Volume | ISSN | ISBN |
3821 | 0302-9743 | 3-540-30495-9 |
Citations | PageRank | References |
3 | 0.39 | 21 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomáš Brázdil | 1 | 194 | 13.11 |
Antonín Kučera | 2 | 262 | 18.04 |
A Kucera | 3 | 3 | 0.39 |