@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.}
}