166
T. Krak
5.3.3 Limits of Homogeneous IDTMCs
We conclude the discussion of imprecise discrete-time Markov chains with some
results about their limit behaviour, in analogy to the results in Sect. 5.2.3. We start
again by restricting attention to homogeneous IDTMCs, and notice the following
(we omit the proof, which is straightforward):
Proposition 5.6 Let P be a homogeneous IDTMC, and let T t be the associated
family of lower transition operators. Then there is a unique lower transition
operator T : L (X ) → L (X ), such that, for all f ∈ L (X ), T t f = T f
for all t ∈ N 0 .
We take a moment here to remark on a property that was already encountered
in Chap. 2: the duality between lower expectation operators and closed and
convex sets of probability measures. Indeed, this correspondence was also used in
Definition 5.14 above, where we used the sets T t of transition matrices, to construct
the lower transition operator T t . Since, as we have just seen, the dynamics of a
homogeneous IDTMC can be completely described by a single T , it now makes
sense to think about the other direction.
Specifically, corresponding to T , there exists a closed and convex set T of
transition matrices, such that T f = inf T ∈T Tf for all f ∈ L (X ). This implies
that (up to the initial distribution at time zero) an IDTMC can also be characterised
by such a set T . So, whereas we noted in Sect. 5.2.2 that a (precise) discretetime Markov chain’s canonical parameter is a single transition matrix T , for a
homogeneous IDTMC, the parameter can be understood as a single closed and
convex set T of transition matrices. Moreover, if in this parametrisation we ensure
that T has separately specified rows—essentially, satisfies a property exactly
analogous to Eq. (5.4)—then the corresponding IDTMC will also be separately
specified.
Furthermore, in Sect. 5.2.2 we used a property of the associated transition matrix
T , to state a sufficient condition for the long-term behaviour of the Markov chain
to converge to a distribution over the states, independently of the state in which
it started. We here have a similar result, which starts by introducing the conjugate
upper transition operator T : L (X ) → L (X ) : f → −T (−f ).
Now, recall that in the precise case, a homogeneous discrete-time Markov chain
with transition matrix T was said to be regular, if there was some n ∈ N such that
T n (x, y) > 0 for all x, y ∈ X . The interpretation is clear: the Markov chain is
regular if and only if there is some finite number of steps n in which every state x
can reach every state y. This is now generalised to the imprecise case:
Definition 5.15 (Regularity for homogeneous IDTMC) Let P be a homogeneous
IDTMC with associated lower (and upper) transition operator T (and T ). Then the
IDTMC is regular if there is some n ∈ N such that
T
n I y
(x) > 0 for all x, y ∈ X .
Let us consider this definition. One difference with the precise case is the introduction of the indicator function I y on the state y ∈ X ; this was introduced because,
T. Krak
5.3.3 Limits of Homogeneous IDTMCs
We conclude the discussion of imprecise discrete-time Markov chains with some
results about their limit behaviour, in analogy to the results in Sect. 5.2.3. We start
again by restricting attention to homogeneous IDTMCs, and notice the following
(we omit the proof, which is straightforward):
Proposition 5.6 Let P be a homogeneous IDTMC, and let T t be the associated
family of lower transition operators. Then there is a unique lower transition
operator T : L (X ) → L (X ), such that, for all f ∈ L (X ), T t f = T f
for all t ∈ N 0 .
We take a moment here to remark on a property that was already encountered
in Chap. 2: the duality between lower expectation operators and closed and
convex sets of probability measures. Indeed, this correspondence was also used in
Definition 5.14 above, where we used the sets T t of transition matrices, to construct
the lower transition operator T t . Since, as we have just seen, the dynamics of a
homogeneous IDTMC can be completely described by a single T , it now makes
sense to think about the other direction.
Specifically, corresponding to T , there exists a closed and convex set T of
transition matrices, such that T f = inf T ∈T Tf for all f ∈ L (X ). This implies
that (up to the initial distribution at time zero) an IDTMC can also be characterised
by such a set T . So, whereas we noted in Sect. 5.2.2 that a (precise) discretetime Markov chain’s canonical parameter is a single transition matrix T , for a
homogeneous IDTMC, the parameter can be understood as a single closed and
convex set T of transition matrices. Moreover, if in this parametrisation we ensure
that T has separately specified rows—essentially, satisfies a property exactly
analogous to Eq. (5.4)—then the corresponding IDTMC will also be separately
specified.
Furthermore, in Sect. 5.2.2 we used a property of the associated transition matrix
T , to state a sufficient condition for the long-term behaviour of the Markov chain
to converge to a distribution over the states, independently of the state in which
it started. We here have a similar result, which starts by introducing the conjugate
upper transition operator T : L (X ) → L (X ) : f → −T (−f ).
Now, recall that in the precise case, a homogeneous discrete-time Markov chain
with transition matrix T was said to be regular, if there was some n ∈ N such that
T n (x, y) > 0 for all x, y ∈ X . The interpretation is clear: the Markov chain is
regular if and only if there is some finite number of steps n in which every state x
can reach every state y. This is now generalised to the imprecise case:
Definition 5.15 (Regularity for homogeneous IDTMC) Let P be a homogeneous
IDTMC with associated lower (and upper) transition operator T (and T ). Then the
IDTMC is regular if there is some n ∈ N such that
T
n I y
(x) > 0 for all x, y ∈ X .
Let us consider this definition. One difference with the precise case is the introduction of the indicator function I y on the state y ∈ X ; this was introduced because,