Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš KUČERA Antonín

Year of publication 2005
Type Article in Proceedings
Conference 25th International Conference on Foundations of Software Technology and Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords Infinite Markov Chains; Expected Reward
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.