@TechReport{ it:2006-009,
author = {Parosh Aziz Abdulla and Noomene Ben Henda and Richard Mayr
and Sven Sandberg},
title = {Eager Markov Chains},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Computer Systems},
year = {2006},
number = {2006-009},
month = mar,
abstract = {We consider infinite-state discrete Markov chains which
are \emph{eager}: the probability of avoiding a defined set
of final states for more than $n$ steps decreases
exponentially in $n$. We study the problem of computing the
expected reward (or cost) of runs until reaching the final
states, where rewards are assigned to individual runs by
computable reward functions. We present a path exploration
scheme, based on forward reachability analysis, to
approximate the expected reward up-to an arbitrarily small
error, and show that the scheme is guaranteed to terminate
in the case of eager Markov chains. We show that eager
Markov chains include those induced by Probabilistic Vector
Addition Systems with States, Noisy Turing Machines, and
Probabilistic Lossy Channel Systems.}
}