5 An Introduction to Imprecise Markov Chains
155
Proposition 5.2 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices, as defined above. Then for all s, t ∈ N 0
such that s ≤ t, and all x, y ∈ X , it holds that P (X t+1 = y | X s = x) =
[T s · · · T t ] (x, y).
Proof We give a proof by induction. For t = s the result is immediate from the
definition of the transition matrix T s . Now suppose the result is true for t − 1; we
show that it is also true for t:
P (X t+1 = y | X s = x) =
z∈X
P (X t+1 = y, X t = z | X s = x)
=
z∈X
P (X t = z | X s = x)P (X t+1 = y | X t = z, X s = x)
=
z∈X
[T s · · · T t−1 ] (x, z)P (X t+1 = y | X t = z)
=
z∈X
[T s · · · T t−1 ] (x, z)T t (z, y) =
T s · · · T t−1 T t
(x, y) ,
where the first and second equalities are basic properties of probabilities, the
third equality is due to the induction hypothesis and the Markov property (c.f.
Definition 5.5), the fourth equality uses the definition of the transition matrix T t
and the final equality uses the definition of a matrix product.
Another useful property of this representation is that it allows us to write
conditional expectations of functions f ∈ L (X ) using matrix-vector products.
In particular, again because X is finite, any f ∈ L (X ) can be interpreted as a
vector in R |X | ; the coordinates are simply the values f (x), x ∈ X . Hence:
Proposition 5.3 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices. Then, for all f ∈ L (X ), all t ∈ N 0 and
all x ∈ X , it holds that E
f (X t+1 ) | X t = x
= [T t f ] (x).
Proof Simply use the definition of the matrix-vector product:
[T t f ] (x)=
y∈X
T t (x, y)f (y)=
y∈X
P (X t+1 =y | X t =x)f (y)=E
f (X t+1 ) | X t =x
.
The above properties can be combined to give a simplified version of the law of
iterated expectation (Theorem 5.1) that we encountered in Sect. 5.2.1:
Corollary 5.3 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices. Then, for all f ∈ L (X ), all s, t ∈ N 0
such that s ≤ t and all x ∈ X , it holds that E
f (X t+1 ) | X s = x
=
[T s · · · T t f ] (x).
155
Proposition 5.2 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices, as defined above. Then for all s, t ∈ N 0
such that s ≤ t, and all x, y ∈ X , it holds that P (X t+1 = y | X s = x) =
[T s · · · T t ] (x, y).
Proof We give a proof by induction. For t = s the result is immediate from the
definition of the transition matrix T s . Now suppose the result is true for t − 1; we
show that it is also true for t:
P (X t+1 = y | X s = x) =
z∈X
P (X t+1 = y, X t = z | X s = x)
=
z∈X
P (X t = z | X s = x)P (X t+1 = y | X t = z, X s = x)
=
z∈X
[T s · · · T t−1 ] (x, z)P (X t+1 = y | X t = z)
=
z∈X
[T s · · · T t−1 ] (x, z)T t (z, y) =
T s · · · T t−1 T t
(x, y) ,
where the first and second equalities are basic properties of probabilities, the
third equality is due to the induction hypothesis and the Markov property (c.f.
Definition 5.5), the fourth equality uses the definition of the transition matrix T t
and the final equality uses the definition of a matrix product.
Another useful property of this representation is that it allows us to write
conditional expectations of functions f ∈ L (X ) using matrix-vector products.
In particular, again because X is finite, any f ∈ L (X ) can be interpreted as a
vector in R |X | ; the coordinates are simply the values f (x), x ∈ X . Hence:
Proposition 5.3 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices. Then, for all f ∈ L (X ), all t ∈ N 0 and
all x ∈ X , it holds that E
f (X t+1 ) | X t = x
= [T t f ] (x).
Proof Simply use the definition of the matrix-vector product:
[T t f ] (x)=
y∈X
T t (x, y)f (y)=
y∈X
P (X t+1 =y | X t =x)f (y)=E
f (X t+1 ) | X t =x
.
The above properties can be combined to give a simplified version of the law of
iterated expectation (Theorem 5.1) that we encountered in Sect. 5.2.1:
Corollary 5.3 Let {X t } t∈N 0 be a discrete-time Markov chain, and let T t be the
associated family of transition matrices. Then, for all f ∈ L (X ), all s, t ∈ N 0
such that s ≤ t and all x ∈ X , it holds that E
f (X t+1 ) | X s = x
=
[T s · · · T t f ] (x).