158
T. Krak
Fig. 5.8 Transition graph of
a Markov chain that is not
irreducible. It has two
communication classes, {a, b}
and {c, d}. The set {c, d}
dominates {a, b} and is the
top (communication) class of
the Markov chain. This
Markov chain is top class
regular
in the associated transition graph. Furthermore, x and y communicate if and only
if there is a cycle in the associated transition graph that contains both x and y.
Proof Trivial from Definitions 5.7 and 5.8.
Inspection of the transition graph in Fig. 5.7 shows that, in that example, all
states communicate with each other. When this is the case, i.e. when all states
communicate, the Markov chain is said to be irreducible. A maximal set of states
that all communicate with each other is called a communication class. Hence, an
irreducible Markov chain has only a single communication class, which is equal to
X .
Note that not every Markov chain is irreducible; in general there may be
more than one communication class. An example is given in Fig. 5.8. When a
communication class A ⊂ X is accessible from a different communication class
B ⊂ X , then A is said to dominate B. A communication class which is not
dominated is called maximal. When a Markov chain has only a single maximal
communication class, this is called the top (communication) class.
Investigation of the communicating states in a Markov chain is often useful when
one is interested in the long-term behaviour of the system. After all, while a system
might begin in one state, it need not necessarily always eventually return to that
state; this is the property that is illustrated in Fig. 5.8.
An important concept is that of the regularity of the communication classes of a
Markov chain. A communication class is regular if there is a number n ∈ N such
that it is possible to go from any state in the class to any other state in the class, in
exactly n steps. Of particular importance is the notion of top class regularity:
Definition 5.9 (Top class regularity) Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain, and let T be its associated transition matrix. Then the Markov
chain is said to be top class regular if
y ∈ X : (∃n ∈ N)(∀x ∈ X ) T
n (x, y) > 0
= ∅ ,
and in that case the top class X top of the Markov chain exists and is equal to this
set. When furthermore X top = X , the Markov chain itself is said to be regular.
T. Krak
Fig. 5.8 Transition graph of
a Markov chain that is not
irreducible. It has two
communication classes, {a, b}
and {c, d}. The set {c, d}
dominates {a, b} and is the
top (communication) class of
the Markov chain. This
Markov chain is top class
regular
in the associated transition graph. Furthermore, x and y communicate if and only
if there is a cycle in the associated transition graph that contains both x and y.
Proof Trivial from Definitions 5.7 and 5.8.
Inspection of the transition graph in Fig. 5.7 shows that, in that example, all
states communicate with each other. When this is the case, i.e. when all states
communicate, the Markov chain is said to be irreducible. A maximal set of states
that all communicate with each other is called a communication class. Hence, an
irreducible Markov chain has only a single communication class, which is equal to
X .
Note that not every Markov chain is irreducible; in general there may be
more than one communication class. An example is given in Fig. 5.8. When a
communication class A ⊂ X is accessible from a different communication class
B ⊂ X , then A is said to dominate B. A communication class which is not
dominated is called maximal. When a Markov chain has only a single maximal
communication class, this is called the top (communication) class.
Investigation of the communicating states in a Markov chain is often useful when
one is interested in the long-term behaviour of the system. After all, while a system
might begin in one state, it need not necessarily always eventually return to that
state; this is the property that is illustrated in Fig. 5.8.
An important concept is that of the regularity of the communication classes of a
Markov chain. A communication class is regular if there is a number n ∈ N such
that it is possible to go from any state in the class to any other state in the class, in
exactly n steps. Of particular importance is the notion of top class regularity:
Definition 5.9 (Top class regularity) Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain, and let T be its associated transition matrix. Then the Markov
chain is said to be top class regular if
y ∈ X : (∃n ∈ N)(∀x ∈ X ) T
n (x, y) > 0
= ∅ ,
and in that case the top class X top of the Markov chain exists and is equal to this
set. When furthermore X top = X , the Markov chain itself is said to be regular.