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

BRÁZDIL, Tomáš and Antonín KUČERA. Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains. In 25th International Conference on Foundations of Software Technology and Theoretical Computer Science. Berlin Heidelberg New York: Springer, 2005, p. 372-383. ISBN 3-540-30495-9.

Basic information

Original name

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

Name in Czech

Výpočet středních hodnot vybraných náhodných proměnných pro Markovovy řetězce s nekonečně mnoha stavy

Authors

BRÁZDIL, Tomáš (203 Czech Republic) and Antonín KUČERA (203 Czech Republic, guarantor)

Edition

Berlin Heidelberg New York, 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, p. 372-383, 12 pp. 2005

Publisher

Springer

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.402

RIV identification code

RIV/00216224:14330/05:00012779

Organization unit

Faculty of Informatics

ISBN

3-540-30495-9

ISSN

UT WoS

000234885800030

Keywords in English

Infinite Markov Chains; Expected Reward

Tags

Expected Reward, Infinite Markov Chains

---

Abstract

V originále

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.

In Czech

Článek se zabývá problematikou výpočtu středních hodnot pro vybrané náhodné proměnné definované na bězích nekonečně-stavových Markovových řetězců. Jsou definovány abstraktní podmínky, za kterých je možno uvedené hodnoty vypočítat s libovolnou přesností. Je také ukázáno, že navržená technika je aplikovatelná na pravděpodobnostní systémy s nespolehlivými komunikačnímy kanály.

---

Links

GA201/03/1161, research and development project	Name: Verifikace nekonečně stavových systémů Investor: Czech Science Foundation, Verification of infinite-state systems
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science