5 An Introduction to Imprecise Markov Chains
157
b
a
c
P(a | a)
P(b | a)
P(c | b)
P(a | c)
P(b | c)
Fig. 5.7 Example transition graph for a discrete-time homogeneous Markov chain with a ternary
state-space X = {a, b, c}. The transition graph is a directed graph, with a vertex for each state and
an arc from the vertex of x to that of y, with x, y ∈ X , whenever T (x, y) = P (X 1 = y | X 0 =
x) > 0. The arcs are labelled with the corresponding transition probabilities. The figure uses the
shorthand notation P (y|x) for the elements T (x, y) of T as before
relative ease of parameterisation—compared to say an arbitrary stochastic process,
which needs separate parameters for every possible history—is arguably one of the
reasons that make homogeneous Markov chains such convenient and widely used
models.
Moving on, the transition graph of a discrete-time homogeneous Markov chain
is a graphical representation of its associated transition matrix T . In this way,
this representation emphasises the interactions between the states, rather than the
random variables. An example transition graph is shown in Fig. 5.7. The formal
definition is as follows:
Definition 5.7 (Transition graph) Let {X t } t∈N 0 be a discrete-time homogeneous
Markov chain, and let T be its associated transition matrix. Then its associated
transition graph is a directed graph (V , E) with one vertex for each state, V = X ,
and, for all x, y ∈ X , an arc (x, y) ∈ E whenever T (x, y) > 0.
One of the reasons transition graphs are sometimes useful is that they allow one
to study which parts of a system can be reached from other parts of the system. The
simplest application is that of communicating states:
Definition 5.8 (Communicating states) Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain, and let T be its associated transition matrix. For any two states
x, y ∈ X , y is said to be accessible from x if there is some n ∈ N such that
T n (x, y) > 0. Furthermore, x and y are said to communicate if y is accessible from
x, and x is accessible from y.
Note that in the above, the term T n denotes the n-th matrix power of T (c.f.
Proposition 5.2). This has an intuitive graphical interpretation:
Corollary 5.4 Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain. Then
for any x, y ∈ X , y is accessible from x if and only if there is a path from x to y
157
b
a
c
P(a | a)
P(b | a)
P(c | b)
P(a | c)
P(b | c)
Fig. 5.7 Example transition graph for a discrete-time homogeneous Markov chain with a ternary
state-space X = {a, b, c}. The transition graph is a directed graph, with a vertex for each state and
an arc from the vertex of x to that of y, with x, y ∈ X , whenever T (x, y) = P (X 1 = y | X 0 =
x) > 0. The arcs are labelled with the corresponding transition probabilities. The figure uses the
shorthand notation P (y|x) for the elements T (x, y) of T as before
relative ease of parameterisation—compared to say an arbitrary stochastic process,
which needs separate parameters for every possible history—is arguably one of the
reasons that make homogeneous Markov chains such convenient and widely used
models.
Moving on, the transition graph of a discrete-time homogeneous Markov chain
is a graphical representation of its associated transition matrix T . In this way,
this representation emphasises the interactions between the states, rather than the
random variables. An example transition graph is shown in Fig. 5.7. The formal
definition is as follows:
Definition 5.7 (Transition graph) Let {X t } t∈N 0 be a discrete-time homogeneous
Markov chain, and let T be its associated transition matrix. Then its associated
transition graph is a directed graph (V , E) with one vertex for each state, V = X ,
and, for all x, y ∈ X , an arc (x, y) ∈ E whenever T (x, y) > 0.
One of the reasons transition graphs are sometimes useful is that they allow one
to study which parts of a system can be reached from other parts of the system. The
simplest application is that of communicating states:
Definition 5.8 (Communicating states) Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain, and let T be its associated transition matrix. For any two states
x, y ∈ X , y is said to be accessible from x if there is some n ∈ N such that
T n (x, y) > 0. Furthermore, x and y are said to communicate if y is accessible from
x, and x is accessible from y.
Note that in the above, the term T n denotes the n-th matrix power of T (c.f.
Proposition 5.2). This has an intuitive graphical interpretation:
Corollary 5.4 Let {X t } t∈N 0 be a discrete-time homogeneous Markov chain. Then
for any x, y ∈ X , y is accessible from x if and only if there is a path from x to y