162
T. Krak
The connection in the other direction is analogous but a bit more subtle. In
particular, if we start from an IDTMC P, then each P ∈ P induces a precise
probability tree. Using the local models of this tree, we can construct set-valued
local models by simply varying P over P. These set-valued local models can then
be used to construct an imprecise probability tree. Clearly, there are then precise
trees that are compatible with this imprecise tree, and each such precise tree induces
a precise measure P . However, and this is the crucial observation, it is in general
not guaranteed that such P are included in P!
As a simple example, suppose that X = {a, b} and we start with a set
P containing only two i.i.d. processes, whose local models are given by p, h,
respectively. Then, the induced imprecise probability tree has local models P w =
{p, h} for all w ∈ X ∗
. On the other hand, we can easily construct a non-i.i.d.
process such that, for all w ∈ X ∗
, its local model is p w = p if w = a and
p w = h, otherwise. Then clearly this process was not in the original set P, but it is
compatible with the imprecise probability tree.
To prevent this from happening, we will require that the set representation P of
the IDTMC is ‘large enough’. Specifically, what we need is that it is already closed
under such ‘recombination’ of local models at different points in time. Whenever
this property holds, we will say that the IDTMC is separately specified. Clearly,
when we start from an imprecise probability tree and construct its set of compatible
processes, this IDTMC will then satisfy this property. In the remainder of this
section, we will assume that a given set P is indeed separately specified. Further
on, when we consider the parametrisation of an IDTMC, we will consider an easy
condition that ensures this will hold.
With this connection between the two representations in place, we can again start
to consider computational methods for lower expectations. Analogous to what we
have seen before, in this context we have a law of iterated lower expectation that we
can use as a computational tool. The imprecise probability tree representation again
provides graphical intuition.
Similar to the exposition in Sect. 5.2.1, we start with a function f ∈ L (X n+1 )
of which we want to compute the lower expectation with respect to the states at the
time points 0, . . . , n. Then for any situation w ∈ X ∗ such that |w| = n + 1, the
lower expectation is trivial:
E P
f (X 0:n )
X 0:n = w
= f (w) .
We then again ‘pull back’ to the parent situation v of w; this is where the main
difference with Sect. 5.2.1 occurs. Notably, we here have an imprecise local model
P v associated to this node v. The point to the law of iterated lower expectation is
that it suffices to only compute the associated conditional lower expectation locally:
E P
f (X 0:n )
X 0:(n−1) =v
= inf
p v ∈P v
x∈X
p v (x)E P
f (X 0:n )
X 0:(n−1) =v, X n =x
.
T. Krak
The connection in the other direction is analogous but a bit more subtle. In
particular, if we start from an IDTMC P, then each P ∈ P induces a precise
probability tree. Using the local models of this tree, we can construct set-valued
local models by simply varying P over P. These set-valued local models can then
be used to construct an imprecise probability tree. Clearly, there are then precise
trees that are compatible with this imprecise tree, and each such precise tree induces
a precise measure P . However, and this is the crucial observation, it is in general
not guaranteed that such P are included in P!
As a simple example, suppose that X = {a, b} and we start with a set
P containing only two i.i.d. processes, whose local models are given by p, h,
respectively. Then, the induced imprecise probability tree has local models P w =
{p, h} for all w ∈ X ∗
. On the other hand, we can easily construct a non-i.i.d.
process such that, for all w ∈ X ∗
, its local model is p w = p if w = a and
p w = h, otherwise. Then clearly this process was not in the original set P, but it is
compatible with the imprecise probability tree.
To prevent this from happening, we will require that the set representation P of
the IDTMC is ‘large enough’. Specifically, what we need is that it is already closed
under such ‘recombination’ of local models at different points in time. Whenever
this property holds, we will say that the IDTMC is separately specified. Clearly,
when we start from an imprecise probability tree and construct its set of compatible
processes, this IDTMC will then satisfy this property. In the remainder of this
section, we will assume that a given set P is indeed separately specified. Further
on, when we consider the parametrisation of an IDTMC, we will consider an easy
condition that ensures this will hold.
With this connection between the two representations in place, we can again start
to consider computational methods for lower expectations. Analogous to what we
have seen before, in this context we have a law of iterated lower expectation that we
can use as a computational tool. The imprecise probability tree representation again
provides graphical intuition.
Similar to the exposition in Sect. 5.2.1, we start with a function f ∈ L (X n+1 )
of which we want to compute the lower expectation with respect to the states at the
time points 0, . . . , n. Then for any situation w ∈ X ∗ such that |w| = n + 1, the
lower expectation is trivial:
E P
f (X 0:n )
X 0:n = w
= f (w) .
We then again ‘pull back’ to the parent situation v of w; this is where the main
difference with Sect. 5.2.1 occurs. Notably, we here have an imprecise local model
P v associated to this node v. The point to the law of iterated lower expectation is
that it suffices to only compute the associated conditional lower expectation locally:
E P
f (X 0:n )
X 0:(n−1) =v
= inf
p v ∈P v
x∈X
p v (x)E P
f (X 0:n )
X 0:(n−1) =v, X n =x
.