LECTURE 6: Accessing the States of a Markov Chain

Somabha Mukherjee

National University of Singapore

1 / 16
Outline

1 Accessing One State from Another

2 Communicating Classes and Irreducibility

3 Essential and Inessential States

2 / 16
Accessible States
Let i and j be two states of a Markov chain. We say that j is accessible from
i or i leads to j, and write i → j, if there exists k ≥ 0 such that
(k)
P(Xk = j|X0 = i) > 0, i.e. pij > 0 .

(0)
Note that by definition, i→i, since pii = 1.

In words, state j is accessible from state i if and only if it is possible for the
chain to move from i to j in a finite number of steps.

Simple Random Walk

If Xn is the simple random walk, then any state j ∈ Z is accessible from any
other state i ∈ Z in |i − j| steps.

This is because, if j > i, then the random walk can take +1 steps to reach j
from i in j − i steps, and if j < i, then the random walk can take −1 steps to
reach j from i in i − j steps.
3 / 16
A Transitivity Property
If i → j and j → k, then i → k. Why?

Since i → j, (P m )i,j > 0 for some m ≥ 1, and since j → k, (P n )j,k > 0 for
some n ≥ 1. Note the use of the Chapman-Kolmogorov equation above.

Now, recall the formula for matrix multiplication:

X
(P m+n )i,k = (P m )i,ℓ (P n )ℓ,k ≥ (P m )i,j (P n )j,k > 0 .
ℓ∈S

This shows that (P m+n )i,k > 0, which indicates that i → k.

Quite often, we say that the states i and j communicate, and write i ↔ j, if
i → j and j→i.

Since i→i, the relation “↔” is reflexive. We already showed above that the
relation ↔ is transitive. Finally, it follows trivially from definition, that if
i↔j, then j↔i, which establishes symmetry.

↔ is thus an equivalence relation on the state space S.

4 / 16
Outline

1 Accessing One State from Another

2 Communicating Classes and Irreducibility

3 Essential and Inessential States

5 / 16
Communicating Classes

The communicating relation ↔ being an equivalence relation, splits the state

space into several equivalence classes, called communicating classes.

Any two states in the same communicating class communicate with each
other.

It is possible that a state j in a particular communicating class Sj is

accessible from another state i in a different communicating class Si (i.e.
i→j). In that case, however, you cannot return to Si from Sj . Why?

Because, if you could, i.e. if x→y for some x ∈ Sj and y ∈ Si , then we have
j→x, x→y and y →i, and so by transitivity, j→i, thereby implying that i↔j.
This contradicts that i and j belong to different communicating classes!

In the next few slides, we will work out some examples concerning
identification of the communicating classes of a Markov chain from its
transition matrix.

6 / 16
A 3-state Markov Chain
Let us consider a Markov chain with the following transition matrix:
 
0.3 0.5 0.2
P := 0.4 0.3 0.3
0 0 1

Since P1,2 > 0 and P2,1 > 0, states 1 and 2 must belong to the same
communicating class. What about state 3?

You see that if the chain enters state 3, then it gets stuck there. This is
because P3,3 = 1 and P3,j = 0 for j ∈ {1, 2}. Such a state is called an
absorbing state.

Hence, the state 3 consists of a separate communicating class altogether.

This Markov chain thus has two communicating classes, {1, 2} and {3}. You
can reach 3 from both 1 and 2, but cannot get back to either of the latter
states from 3.
7 / 16
A 4-state Markov Chain
Let us consider a Markov chain with the following transition matrix:
 
0.2 0.2 0.3 0.3
0 0.4 0.6 0 
P := 0

0.5 0.5 0 
0.1 0.3 0 0.6

Since both P1,4 and P4,1 are positive, we have 1↔4, and since both P2,3 and
P3,2 are positive, we also have 2↔3.

Now, note that the state 2 can lead only to itself and the state 3 in one step
(since P2,1 = P2,4 = 0), and the state 3 can lead only to itself and the step 2
in one step (since P3,1 = P3,4 = 0).

Hence, once you enter either state 2 or state 3, you get stuck within these
two states, and cannot access any of the states 1 or 4 ever again.

Hence, there are only two communicating classes, {1, 4} and {2, 3}.
8 / 16
Another Example
Consider a 6-state Markov chain with the following transition matrix:
 
0.2 0 0.4 0.3 0 0.1
 0 0.2 0.3 0.5 0 0
 
0 0 0 0.3 0.4 0.3
P := 
 0 0.6 0

 0.4 0 0
0.7 0 0 0 0.1 0.2
0 0 0 0.1 0 0.9
Note that 1→3, 3→5 and 5→1 all in one step, and so, 1, 3, 5 must belong to
the same communicating class.
Similarly, 2→4 and 4→2 both in one step, so 2 and 4 belong to the same
communicating class.
Note that 3→6 in one step. On the other hand, 6→4, 4→2 and 2→3, all in
one step. So, 6→3 by transitivity, and hence, 6 belongs to the same
communicating class as 1, 3, 5.
Next, 6→4, 4→2, 2→3 and 3→6 all in one step, so 6↔2. So, 6 belongs to
the same communicating class as 2, 4. The entire state space {1, 2, 3, 4, 5, 6}
is thus one communicating class.
9 / 16
A Useful Check

Checking if a state i leads to a state j from the definition may be

cumbersome, because it involves computing the powers of the transition
matrix.
Luckily, there is an easier way to do this. This is by drawing a directed graph
(with loop).
Let the state space S be the vertex set of this graph. Draw a directed edge
between two vertices i and j if and only if Pi,j > 0.
After completing drawing the graph, now you can determine whether i→j,
simply by looking for a directed path in this graph from i to j.
Although searching for a directed path between two vertices of a graph is not
a direct task, in most cases it is much easier than computing matrix powers,
since it is done mainly by visual inspection.
Can you justify the above algorithm mathematically? EXERCISE!

10 / 16
Irreducible Markov Chains

In the last example, the entire state space was a single communicating class,
which is another way of saying that any two states communicate. Such a
Markov chain is called irreducible.

Definition: A Markov chain is said to be irreducible, if i↔j for all i, j ∈ S, or

equivalently, if the entire state space is a communicating class.

From the graph perspective, a Markov chain is irreducible if and only if the
corresponding state space graph (as constructed in the previous slide) is
strongly connected, i.e. for all pair (i, j) of vertices, there is a path from i
to j and from j to i.

A simple random walk is irreducible, because every state can be accessed

from every other state.

Is the branching process with Poisson offspring distribution an irreducible

Markov chain? What happens if the offspring distribution is a discrete
distribution on the set of strictly positive integers? EXERCISE!

11 / 16
Outline

1 Accessing One State from Another

2 Communicating Classes and Irreducibility

3 Essential and Inessential States

12 / 16
Can I Get Lost from a State in a Markov Chain?

So, what I mean is that if I am now at state i, and i→j, then is there a
guarantee that j→i too? Otherwise, I would be lost from i forever!

Of course, there is no such guarantee in general. The simplest example is

probably given by the following trandition matrix:
 
0.5 0.5
P :=
0 1

Here, 1→2, but 2 does not lead to 1. So, if you end up landing at 2 from 1,
you are stuck there forever, and never return to 1.

Definition
A state i is called essential, if for every state j such that i→j, it is also true that
j→i. A state which is not essential, is called inessential.

13 / 16
Some Examples

In the 3-state Markov chain example, the states 1 and 2 are both inessential,
since they both lead to state 3, but 3 doesn’t lead to any of them. On the
other hand, state 3 is essential.

In the 4-state Markov chain example, the states 1 and 4 are inessential,
because they both lead to state 2, but once you are at 2, there is no
possibility to return to either of them. On the other hand, both the states 2
and 3 are essential.

In the 6-state Markov chain example, you can easily verify that all states are
essential

In a simple random walk, all states are essential. This is because you can
access any state from any other state.

14 / 16
Essential States Lead to Essential States Only

If i is an essential state and i→j, then j is an essential state, too. Why?

Suppose that j→k. We have to argue that k→j too.

Since j→k and i→j, by transitivity, i→k.

Now, i being essential, we must thus have k→i.

Again, since k→i and i→j, by transitivity, we have k→j. Hence, j is

essential, too.

A Useful Consequence
A useful consequence of the above fact, is that the states in a communicating
class are either all essential, or they are all inessential. This is because, if the
communicating class has at least one essential state, then since that state leads to
all other states in that class, they must all be essential, too.

15 / 16
A Finite State Space Must Have an Essential State
Does an essential state always exist? Well, it does if the state space is finite.

To see this, suppose not; i.e. suppose, if possible, that all states in the finite
state space S are inessential.

Start with a state i0 . Since it is inessential, it leads to a state i1 , such that i1

does not lead back to i0 . Similarly, since i1 is inessential, it leads to a state i2 ,
that does not lead back to i1 .

In this way, we get hold of a sequence of states i0 , i1 , i2 , . . . such that for each
k ≥ 0, ik →ik+1 but ik+1 ̸→ ik .

Now, note that there cannot be any repeated state in the sequence
i0 , i1 , i2 , . . .. This is because, if ij = ik for some k > j ≥ 0, then since by
transitivity ij+1 →ik , we will end up having ij+1 →ij , which is impossible by our
construction.

Hence all terms in the infinite sequence of constructed states must be

distinct, which is also clearly impossible, since the state space has only a
finite number of states.
16 / 16