  This paper studies the influence of probabilism and non-determinism on some
quantitative aspect X of the execution of a system modeled as a Markov decision
process (MDP). To this end, the novel notion of demonic variance is introduced:
For a random variable X in an MDP M, it is defined as 1/2 times the maximal
expected squared distance of the values of X in two independent execution of M
in which also the non-deterministic choices are resolved independently by two
distinct schedulers. It is shown that the demonic variance is between 1 and 2
times as large as the maximal variance of X in M that can be achieved by a
single scheduler. This allows defining a non-determinism score for M and X
measuring how strongly the difference of X in two executions of M can be
influenced by the non-deterministic choices. Properties of MDPs M with extremal
values of the non-determinism score are established. Further, the algorithmic
problems of computing the maximal variance and the demonic variance are
investigated for two random variables, namely weighted reachability and
accumulated rewards. In the process, also the structure of schedulers
maximizing the variance and of scheduler pairs realizing the demonic variance
is analyzed.
