5 An Introduction to Imprecise Markov Chains
151
Having discussed how to interpret probability trees and how to use them to reason
about the computation of expected values, we now move on to a discussion of their
structural properties. Note that the specification of a probability tree is still relatively
complicated. This is not really due to the structure of the tree; the situations X ∗
and
prefix order ≺ carry enough information to construct the tree up to any desired level,
and their mathematical specification is straightforward. However, in order to specify
all the local models p (·) , we need to provide an infinite number of probability mass
functions on X —one for each situation w ∈ X ∗
. This is why one often restricts
attention to simpler models, where one needs fewer, and often only finitely many,
local models.
These simplifications can be seen as a matter of degree. At the one extreme, we
have the general definition that we used above, where each situation w ∈ X ∗
has
a local model p w . This leads to a lot of possible structure but is hard to specify. At
the other extreme is the independent and identically distributed (i.i.d.) process; this
is when we only have a single probability mass function p, and we set p w := p for
all w ∈ X ∗
. For such a process, no matter what situation we are in, the next branch
will always be chosen according to p. This process is easy to specify, but it does not
yield a lot of structure that can capture the dynamics of the underlying system that
we are trying to model.
A useful step up from the i.i.d. process is reached by the popular class of models
known as homogeneous Markov chains. For a homogeneous Markov chain, the local
model only depends on the last step of the corresponding situation, and not on what
happened before that:
Definition 5.3 (Homogeneous Markov chain as probability tree) A probability
tree (X ∗
, ≺, p (·) ) is called a homogeneous Markov chain if p v = p w for all
situations v, w ∈ X ∗ such that v = w .
Corollary 5.2 Let (X ∗
, ≺, p (·) ) be a homogeneous Markov chain. Then p w = p x
for all x ∈ X and all w ∈ X ∗ such that w = x.
Proof Trivial from Definition 5.3 and the fact that all x ∈ X are also situations.
An example for the binary state-space X = {a, b} is shown in Fig. 5.3.
Additional degrees of freedom can be introduced back into this model by also letting
the local models depend on the corresponding depth of the tree. The dynamics can
then depend on the point in time, but not on the specific history up to that time. This
yields the more general definition of a (non-homogeneous) Markov chain:
Definition 5.4 (Markov chain as probability tree) A probability tree (X ∗
, ≺
, p (·) ) is called a Markov chain if p v = p w for all situations v, w ∈ X ∗ for which
|v| = |w| and v = w .
An example for the binary state-space X = {a, b} is shown in Fig. 5.4. It can be
verified that a homogeneous Markov chain is a Markov chain, but not—in general—
the other way around. Note that, in contrast to homogeneous Markov chains where
we only needed to specify local models p x for all x ∈ X , we now need different
151
Having discussed how to interpret probability trees and how to use them to reason
about the computation of expected values, we now move on to a discussion of their
structural properties. Note that the specification of a probability tree is still relatively
complicated. This is not really due to the structure of the tree; the situations X ∗
and
prefix order ≺ carry enough information to construct the tree up to any desired level,
and their mathematical specification is straightforward. However, in order to specify
all the local models p (·) , we need to provide an infinite number of probability mass
functions on X —one for each situation w ∈ X ∗
. This is why one often restricts
attention to simpler models, where one needs fewer, and often only finitely many,
local models.
These simplifications can be seen as a matter of degree. At the one extreme, we
have the general definition that we used above, where each situation w ∈ X ∗
has
a local model p w . This leads to a lot of possible structure but is hard to specify. At
the other extreme is the independent and identically distributed (i.i.d.) process; this
is when we only have a single probability mass function p, and we set p w := p for
all w ∈ X ∗
. For such a process, no matter what situation we are in, the next branch
will always be chosen according to p. This process is easy to specify, but it does not
yield a lot of structure that can capture the dynamics of the underlying system that
we are trying to model.
A useful step up from the i.i.d. process is reached by the popular class of models
known as homogeneous Markov chains. For a homogeneous Markov chain, the local
model only depends on the last step of the corresponding situation, and not on what
happened before that:
Definition 5.3 (Homogeneous Markov chain as probability tree) A probability
tree (X ∗
, ≺, p (·) ) is called a homogeneous Markov chain if p v = p w for all
situations v, w ∈ X ∗ such that v = w .
Corollary 5.2 Let (X ∗
, ≺, p (·) ) be a homogeneous Markov chain. Then p w = p x
for all x ∈ X and all w ∈ X ∗ such that w = x.
Proof Trivial from Definition 5.3 and the fact that all x ∈ X are also situations.
An example for the binary state-space X = {a, b} is shown in Fig. 5.3.
Additional degrees of freedom can be introduced back into this model by also letting
the local models depend on the corresponding depth of the tree. The dynamics can
then depend on the point in time, but not on the specific history up to that time. This
yields the more general definition of a (non-homogeneous) Markov chain:
Definition 5.4 (Markov chain as probability tree) A probability tree (X ∗
, ≺
, p (·) ) is called a Markov chain if p v = p w for all situations v, w ∈ X ∗ for which
|v| = |w| and v = w .
An example for the binary state-space X = {a, b} is shown in Fig. 5.4. It can be
verified that a homogeneous Markov chain is a Markov chain, but not—in general—
the other way around. Note that, in contrast to homogeneous Markov chains where
we only needed to specify local models p x for all x ∈ X , we now need different