5 An Introduction to Imprecise Markov Chains
149
deep down in the tree back to the root. We will see that this allows one to intuitively
derive computational methods for working with stochastic processes.
So, fix n ∈ N 0 , and let f ∈ L (X n+1 ) be a real-valued function for which
we aim to compute the expected value with respect to the random variables X 0:n
at the time points 0, . . . , n ∈ N 0 . Note that it suffices to consider this case, in the
sense that any function defined on a subset of the variables X 0:n , can always be
trivially extended to a function on all of them. Now first notice the following. For
any situation w ∈ X ∗ with length |w| = n + 1, the value of f in w is easy to
compute; it is simply f (w). Hence in particular, the expected value of f , in w, is
simply
E
f (X 0:n )
X 0:n = w
= f (w) .
Recall that the situation w represents a node in the event tree. We will now ‘pull
back’ the above expected value, to the time point n − 1. Consider therefore the
parent situation of w in the probability tree; we will compute the expected value of
f in this parent situation.
This parent is a situation v of length |v|= |w|−1 = n, which entirely coincides
with w: v i = w i for all i = 0, . . . , n − 1. Associated to v is the local probability
model p v which, as we have discussed above, represents the probability with
which a random walk along the tree travels through the various children of v.
In particular, such a random walk goes through the situation w, with probability
p v (w ). Therefore, the contribution of the expected value in w, to the expected
value in v, is the expected value in w weighted by p v (w ). Since this holds for all
children of v, we can write
E
f (X 0:n )
X 0:(n−1) = v
=
x∈X
p v (x)E
f (X 0:n )
X 0:(n−1) = v, X n = x
.
This ‘pullback’ operation is graphically illustrated in Fig. 5.2.
Now, observe that the above conditional expectation of f in v is itself a realvalued function in L (X n ). Its value is determined by the states at times 0, . . . , n −
1. We can therefore repeat the above argument; we pull back to the parent of v,
then to the parent of that situation and so on. Eventually, the parent that we are
considering is the empty situation ; we then finish by computing
E
f (X 0:n )
=
x∈X
p (x)E
f (X 0:n )
X 0 = x
,
which is exactly the expected value of f that we started out wanting to compute.
This method to compute the expected value of a function by ‘pulling back’
the ‘local’, or conditional, expected values, uses the interpretation of a stochastic
process as a probability tree. The method relies on a property that is called the
law of iterated expectation, or alternatively the law of total probability. It can be
149
deep down in the tree back to the root. We will see that this allows one to intuitively
derive computational methods for working with stochastic processes.
So, fix n ∈ N 0 , and let f ∈ L (X n+1 ) be a real-valued function for which
we aim to compute the expected value with respect to the random variables X 0:n
at the time points 0, . . . , n ∈ N 0 . Note that it suffices to consider this case, in the
sense that any function defined on a subset of the variables X 0:n , can always be
trivially extended to a function on all of them. Now first notice the following. For
any situation w ∈ X ∗ with length |w| = n + 1, the value of f in w is easy to
compute; it is simply f (w). Hence in particular, the expected value of f , in w, is
simply
E
f (X 0:n )
X 0:n = w
= f (w) .
Recall that the situation w represents a node in the event tree. We will now ‘pull
back’ the above expected value, to the time point n − 1. Consider therefore the
parent situation of w in the probability tree; we will compute the expected value of
f in this parent situation.
This parent is a situation v of length |v|= |w|−1 = n, which entirely coincides
with w: v i = w i for all i = 0, . . . , n − 1. Associated to v is the local probability
model p v which, as we have discussed above, represents the probability with
which a random walk along the tree travels through the various children of v.
In particular, such a random walk goes through the situation w, with probability
p v (w ). Therefore, the contribution of the expected value in w, to the expected
value in v, is the expected value in w weighted by p v (w ). Since this holds for all
children of v, we can write
E
f (X 0:n )
X 0:(n−1) = v
=
x∈X
p v (x)E
f (X 0:n )
X 0:(n−1) = v, X n = x
.
This ‘pullback’ operation is graphically illustrated in Fig. 5.2.
Now, observe that the above conditional expectation of f in v is itself a realvalued function in L (X n ). Its value is determined by the states at times 0, . . . , n −
1. We can therefore repeat the above argument; we pull back to the parent of v,
then to the parent of that situation and so on. Eventually, the parent that we are
considering is the empty situation ; we then finish by computing
E
f (X 0:n )
=
x∈X
p (x)E
f (X 0:n )
X 0 = x
,
which is exactly the expected value of f that we started out wanting to compute.
This method to compute the expected value of a function by ‘pulling back’
the ‘local’, or conditional, expected values, uses the interpretation of a stochastic
process as a probability tree. The method relies on a property that is called the
law of iterated expectation, or alternatively the law of total probability. It can be