  We present the first study of non-deterministic weighted automata under
probabilistic semantics. In this semantics words are random events, generated
by a Markov chain, and functions computed by weighted automata are random
variables. We consider the probabilistic questions of computing the expected
value and the cumulative distribution for such random variables.
  The exact answers to the probabilistic questions for non-deterministic
automata can be irrational and are uncomputable in general. To overcome this
limitation, we propose approximation algorithms for the probabilistic
questions, which work in exponential time in the size of the automaton and
polynomial time in the size of the Markov chain and the given precision. We
apply this result to show that non-deterministic automata can be effectively
determinised with respect to the standard deviation metric.
