ST3236/MA3238: Stochastic Processes I

Markov Chain: Classification of States

WANG Wanjie
[Link]@[Link]

Department of Statistics and Data Science

National University of Singapore (NUS)

Sunday 7th September, 2025

ST3236 Stochastic Processes I Classification of States 1 / 47

Motivation

Recall: we have 4 types of problems

Short-term questions: solved

Dist. of future steps for a fixed number of steps
Dist. of past steps for a fixed number of steps

Strategy-related questions: solved

First step analysis

Long-run performance?
When n → ∞, what can we claim about Xn ?

Extensions
Next month

ST3236 Stochastic Processes I Classification of States 2 / 47

Long-run Performance

What is the distribution of Xn when n → ∞?

X0 may be a given state or a dist. X0 ∼ π

First step X1 ∼ πP
n-th step Xn ∼ πPn
When n → ∞, will the dist. become stationary?
stationary regarding to the time?
stationary regarding to π?

ST3236 Stochastic Processes I Classification of States 3 / 47

A Motivating Example

Markov Chain Example

1 2 3 4 5 6 7 8
1 .4 .6 0 0 0 0 0 0
2 .5 .5 0 0 0 0 0 0
3 .3
 0 0 .5 0 0 0 .2
4 0 0 0 0 .6 0 0 .4
P=  
5 0
 .4 .3 0 0 .3 0 0
6 0
 0 0 0 0 .4 .6 0
7 0 0 0 0 0 .7 .3 0
8 0 0 0 0 0 0 0 1

ST3236 Stochastic Processes I Classification of States 4 / 47

Motivating Example: Long-run Performance

ST3236 Stochastic Processes I Classification of States 5 / 47

Communication classes of states
Accessibility

Definition
For a Markov Chain {Xn , n = 0, 1, 2, · · · } with transition prob.
matrix P, state j is said to be accessible from state i, denoted by
(m)
i → j, if Pij > 0 for some m ≥ 0.

Example. Find the pairwise accessibility for the following MC.

 
1 0 0 0
 0 0.3 0.7 0 
P=  0
.
0.6 0.4 0 
0.2 0 0.1 0.7

ST3236 Stochastic Processes I Classification of States 6 / 47

Accessibility

Remark.
The accessibility is not symmetric
i → j doesn’t indicate j → i
Once i → j, then i → k for all k accessible from j.
Diagram is helpful to figure out the accessibility.
Accessibility is not to evaluate only one step

ST3236 Stochastic Processes I Classification of States 7 / 47

Communication

Definition
If two states i and j are accessible from each other, i.e., i → j and
j → i, then they are said to communicate, denoted by i ←→ j.
Remark.
(0)
For any state i, i ←→ i because pii = 1 and i → i.

Theorem: Communication
Communication is an equivalence relation, i.e.,
Reflexivity: i ←→ i.
Symmetry: if i ←→ j, then j ←→ i.
Transitivity: if i ←→ j and j ←→ k, then i ←→ k.

ST3236 Stochastic Processes I Classification of States 8 / 47

Communication Equivalence

Reasons.
(0)
Reflexivity: Pii = 1 > 0 for any i, so i ←→ i.
Symmetry: definition.
Transitivity: By the definition, there exists s > 0 and t > 0 so that
(s) (t)
Pij > 0, Pjk > 0.

By the Chapman-Kolmogorov equations,

(s+t)
X (s) (t) (s) (t)
Pik = Pil Plk ≥ Pij Pjk > 0.
l∈S

Therefore, i → k. Similarly, k → i, so i ←→ k.

ST3236 Stochastic Processes I Classification of States 9 / 47

Communication class

Based on the equivalence relation, we can define an equivalence class

Definition: Communication Class
A set of states C are called a communication class, if
for any i, j ∈ C, there is i ←→ j; and
for any i ∈ C and j 6∈ C, i 6←→ j.

It is well-defined.
Every state belongs to one and only one communication class
Some properties are shared among states in the same class
If i → j for i ∈ C1 and j ∈ C2 , then for any i0 ∈ C1 and j 0 ∈ C2 , there is
i0 → j 0 .
Further, since C1 6= C2 , we have j 6→ i and j 0 6→ i0 .

ST3236 Stochastic Processes I Classification of States 10 / 47

Example
Consider the following transition prob. matrices (states 1, 2, 3, · · · , ignored
in matrices). Find the communication classes.
 
0 0.5 0.5
P =  0.75 0 0.25 
0.75 0.25 0

ST3236 Stochastic Processes I Classification of States 11 / 47

Example: Reducible Chain
Try to find the communication classes in the following MC.

ST3236 Stochastic Processes I Classification of States 12 / 47

Reducible Chain

Definition: Reducible Chain

An MC is irreducible if all the states communicate with one another,
i.e. there is only one communication class in the MC.
Otherwise, the chain is said to be reducible.

Reducible MC ⇐⇒ more than 1 classes

Irreducible MC ⇐⇒ one class
An irreducible MC can have finite states, or infinitely many
states.

ST3236 Stochastic Processes I Classification of States 13 / 47

Classes in the Motivating Example

ST3236 Stochastic Processes I Classification of States 14 / 47

Typical Form
A typical irreducible MC (probabilities neglected):

Each rectangle contains one class

Two classes cannot communicate with each other, otherwise they will
be one class.
We can see a “flow” between classes
ST3236 Stochastic Processes I Classification of States 15 / 47
Recurrent and Transient States
Example: Flow between Classes

In the long run

The flow will be trapped in
states 4/3/2 finally
If the flow starts from 1, then it
will end in 2/3
If the flow starts from 7, it may
return to 7 for some turns but
finally end in 2
If the flow starts from 8, it may
pass by 5/6/7 first but still end
in 4/3/2 finally

We can see
Some classes are “transient”, and some are kind of an “end”
Mathematical expression?

ST3236 Stochastic Processes I Classification of States 16 / 47

First Return Probability

Definition: First Return Probability

For any state i, define the probability that starting from state i, the
first return to i is at the nth transition:
(n)
fii = P (X1 6= i, X2 6= i, · · · , Xn−1 6= i, Xn = i|X0 = i).
(0)
Note. fii := 0.

By “first”, we require the process never visits state i between

time points t = 0 and t = n.
(0)
When n = 0, we set fii = 0.

ST3236 Stochastic Processes I Classification of States 17 / 47

First Return Prob.

Consider the following example. What is the first return probability

(n)
f11 for any n?

ST3236 Stochastic Processes I Classification of States 18 / 47

Recurrent and Transient States

Define
∞ N
(n) (n)
X X
fii = fii = lim fii
N →∞
n=0 n=0

fii denotes the probability of revisiting i in the future.

fii ≤ 1 since it is a probability

Definition: Recurrent and Transient States

A state i is said to be recurrent if fii = 1; and transient if fii < 1.

If it will revisit state i “for sure”, then state i is recurrent;

otherwise, the flow will finally leave state i

ST3236 Stochastic Processes I Classification of States 19 / 47

Recurrent and Transient States

Back to the following example.

What is f44 ? Is state 4 recurrent or transient?

What is f22 ? Is state 2 recurrent or transient?
What is f11 ? Is state 1 recurrent or transient?

ST3236 Stochastic Processes I Classification of States 20 / 47

Recurrence and Number of Revisits

How does the definition of recurrence relate to our intuition about the flow?

Intuition: the flow will come back on and on, which seems to be
“trapped”
Let Ni be the number of times that the MC revisits state i

Ni = ∞
P
n=1 I(Xn = i)

“Come back on and on”: E[Ni |X0 = i] = ∞

“recurrent” means E[Ni |X0 = i] = ∞. “transient” means there may be
revisits, but limited, i.e. E[Ni X0 = i] < ∞
Compare to the definition based on fii , we want to prove

= ∞, fii = 1
E[Ni |X0 = i]
< ∞, fii < 1.

ST3236 Stochastic Processes I Classification of States 21 / 47

Theorem: Number of Revisits

Theorem: Number of Revisits

For a state i, consider the expected number of visits to i,
E[Ni |X0 = i], then
If fii = 1 (i.e. i is recurrent), there is E[Ni |X0 = i] = ∞.
fii
If fii < 1 (i.e. i is transient), there is E[Ni |X0 = i] = 1−fii ;

Theoretical evidence for the definition of recurrent/transient states

Recurrent states: E[Ni |X0 = i] is infinite, i.e. the process revisits it
again and again in the long run
Transient states: E[Ni |X0 = i] increases when fii increases. However,
we will never revisit i again in the long run.

ST3236 Stochastic Processes I Classification of States 22 / 47

Proof
Ni ≥ 1 means starting with i, there is at least one revisit.
∞
X (k)
P (Ni ≥ 1|X0 = i) = fii = fii .
j=1

Now we consider the event Ni ≥ 2. By the law of total probability,

∞
X
P (Ni ≥ 1|X0 = i) = P (Ni ≥ 2|first revisit happens at step k)
k=1
×P (first revisit happens at step k|X0 = i)
∞
X (k)
= P (Ni ≥ 2|Xk = i)fii
k=1
X∞
(k)
= P (Ni ≥ 1|X0 = i)fii
k=1
∞
X (k)
= P (Ni ≥ 1|X0 = i) fii = fii2 .
k=1

In general, we have P (Ni ≥ m|X0 = i) = fiim

ST3236 Stochastic Processes I Classification of States 23 / 47
Proof

Expectation.
∞
X ∞ X
X k
E[Ni |X0 = i] = kP (Ni = k|X0 = i) = P (Ni = k|X0 = i)
k=1 k=1 m=1
X∞ ∞
X
= P (Ni = k|X0 = i) Reorder
m=1 k=m
X∞
= P (Ni ≥ m|X0 = i)
m=1

Introduce the result P (Ni ≥ m|X0 = i) = fiim

∞ ∞
X X fii
E[Ni |X0 = i] = P (Ni ≥ m|X0 = i) = fiim = .
m=1 j=1
1 − fii
Consider the recurrent case where fii = 1. All the analysis hold,
therefore,
P (Ni ≥ m|X0P = i) = fiim = 1 for recurrent state i;
E[Ni |X0 = i] ∞ k
k=1 fii → ∞.

ST3236 Stochastic Processes I Classification of States 24 / 47

Example

Consider a MC with transition probability matrix

1 2 3 4
1 1 0 0 0
 

P= 2  0 0.3 0.7 0 .
30 0.6 0.4 0
4 0.2 0 0.1 0.7

(1) (i)
State 1. Absorbing state, there is f11 = 1, f11 = 0, i = 2, 3, · · ·

f11 = 1 =⇒ Recurrent.

State 2 and 3 are in the same absorbing class. Discuss next page
(1) (2) (3)
State 4. There is f44 = 0.7, f44 = 0, f44 = 0, · · ·

f44 = 0.7 =⇒ Transient

ST3236 Stochastic Processes I Classification of States 25 / 47

Example (cont’d)

State 2. For it, we have

(1)
f22 = 0.3,
(2)
f22 = 0.7 × 0.6 = P (X1 6= 2, X2 = 2|X0 = 2) = p23 p32
(3)
f22 = 0.7 × 0.4 × 0.6 = p23 p33 p32
(4)
f22 = 0.7 × 0.4 × 0.6 = p23 p233 p32
···
∞
X (k)
f22 = f22 = 0.3 + 0.7 × (1 + 0.4 + +0.42 · · · ) × 0.6
k=1
= 1.

Therefore, State 2 is recurrent.

Similarly, for state 3, there is
∞
X (k)
f33 = f33 = 0.4 + 0.6 × (1 + 0.3 + 0.32 + · · · ) × 0.7 = 1.
k=1

State 3 is also recurrent.

ST3236 Stochastic Processes I Classification of States 26 / 47
From state to communication class
Return Probability

Definition: Return Probability

For any state i, define return probability to be the probability that
starting from state i and returns at i at the nth transition is that:
(n)
Pii = P (Xn = i|X0 = i).

(0) (1) (2)

According to the definition, Pii = 1, Pii = Pii , Pii = (P2 )ii ,
(n)
Given n, 0 ≤ Pii ≤ 1.
Pn (n)
It’s possible that i=0 Pii > 1.

ST3236 Stochastic Processes I Classification of States 27 / 47

First Return Prob. and Return Prob.

Define
event En = {X0 = i, X1 6= i, X2 6= i, · · · , Xn−1 6= i, Xn = i}; and
event An = {X0 = i, Xn = i}

Then we have
(n) (n)
fii = P (En |X0 = i), Pii = P (An |X0 = i),
(n) (n)
En ⊆ An , so fii ≤ for all n = 0, 1, 2, · · ·
Pii ,
P∞ P∞ (n)
En s are disjoint, so P (∪∞
n=1 En ) = n=1 P (En ) = n=1 fii ≤ 1
P∞ (n)
An s are not disjoint, so it’s possible that n=1 Pii ≥ 1

ST3236 Stochastic Processes I Classification of States 28 / 47

First Return Prob. and Return Prob.

Consider this toy example.

(n)
Return probability P11 :
(n)
First return probability f11 :
(6) (6)
What are f11 and P11 ?

ST3236 Stochastic Processes I Classification of States 29 / 47

Return Prob.

Consider the following example.

(n)
What is the return probability P44 for any n?
(n)
What is the return probability P22 for any n?

ST3236 Stochastic Processes I Classification of States 30 / 47

 (n) (n)
Connection between Pii and fii
(n) (n)
What are the connections between Pii and fii ?
According to the law of total probability,
n
(n)
X
Pii = P (first arrives i at step k|X0 = i)P (Xn = i|Xk = i)
k=1
Xn
= P (Ek |X0 = i)P (An−k |X0 = i)
k=1
n
(k) (n−k)
X
= fii Pii
k=1
n
(k) (n−k) (n)
X
= fii Pii + 0 ∗ Pii
k=1
n
(k) (n−k)
X
= fii Pii
k=0

(0)
The last equality comes from fii = 0.
ST3236 Stochastic Processes I Classification of States 31 / 47
 (n) (n)
Connection between Pii and fii

Theorem: Return Prob. and First Return Prob.

n
(n) (k) (n−k)
X
Pii = fii Pii .
k=0

Remark.
Such type of formula is called a “convolution”
(0) (1)
Note that fii = 0 and fii = Pii , which is given.
(n) (0) (n−1)
To find out Pii , we only need Pii to Pii
(1) (2) (3)
Hence, starting with Pii = Pii , we can proceed to Pii , Pii ,
(n)
and finally Pii .

ST3236 Stochastic Processes I Classification of States 32 / 47

 (n)
Connection between Ni and Pii

P∞
Consider the definition of Ni . Note Ni = n=1 I{Xn = i}.
∞
X
E[Ni |X0 = i] = E[ I{Xn = i}|X0 = i]
n=1
∞
X
= E[I{Xn = i}|X0 = i]
n=1
X∞
= P (Xn = i|X0 = i) Property of indicator function
n=1
X∞
(n)
= Pii
n=1

P∞ (n)
Therefore, for recurrent states, n=1 Pii is infinite, and for transient
states, it is finite.

ST3236 Stochastic Processes I Classification of States 33 / 47

Theorem: Return Prob.

Theorem: Recurrence/Transient States and Return Prob.

State i is recurrent if and only if
∞
(n)
X
Pii = ∞.
n=1

P∞ (n)
For recurrent states, starting from any m > 0, n=m Pii = ∞,
which means a significant prob. to return
P∞ (n)
For transient states, the revisiting prob. n=m Pii → 0 when
m → ∞. In the long run, the probability of coming back vanishes

ST3236 Stochastic Processes I Classification of States 34 / 47

Recurrence Property vs 3 Measurements

According to the theorems and definitions, starting at i,

(n)
fii is the prob. that the first return to i happens at n-th step;
fii is the prob. that it returns to i in finite steps;
(n)
Pii is the prob. that it is at i at n-th step;
Ni is the number of revisits to i.
States:
P∞ (n)
Recurrent ⇔ fii = 1 ⇔ n=1 Pii = ∞ ⇔ E[Ni |X0 = i] = ∞

P∞ (n)
Transient ⇔ fii < 1 ⇔ n=1 Pii < ∞ ⇔ E[Ni |X0 = i] < ∞

ST3236 Stochastic Processes I Classification of States 35 / 47

 (n)
Pii for States in the Same Class
Now consider i, j in the same class, i.e. i ←→ j
Since i ←→ j, there exists n and m, so that
(n) (m)
Pij > 0, Pji >0

Consider any integer v > 0. Then

(m+n+v) (m) (v) (n)
Pjj ≥ Pji Pii Pij .
Sum over v = 0, 1, 2, · · · on both sides,
∞
X ∞
X ∞
X ∞
X
(m+n+v) (m) (v) (n) (m) (v) (n) (v)
Pjj ≥ Pji Pii Pij = Pji ( Pii )Pij = C1 Pii .
v=0 v=0 v=0 v=0
It means, there is a constant C1 > 0, so that
∞
X ∞
X ∞
X ∞
X
(w) (w) (m+n+v) (v)
Pjj ≥ Pjj ≥ Pjj ≥ C1 Pii
w=0 w=m+n v=0 v=0
P∞ (v) P∞
(w)
If v=0 Pii = ∞, then w=0 Pjj → ∞. Hence, j is also recurrent.
transient, then v=0 Pii ≤ C11 ∞
P∞ (v) P (w)
If j is w=0 Pjj is finite. Therefore,
i is transient.
If i is transient, with the same analysis, j is transient.
ST3236 Stochastic Processes I Classification of States 36 / 47
States in the same class

Theorem
If a state i is recurrent and i ←→ j, then state j is recurrent;
If a state i is transient and i ←→ j, then state j is transient.

It means, the recurrent/transient status can be seen as a status

for one communication class
A communication class is either recurrent or transient . A class
is recurrent (transient) means all the states in this class are
recurrent (transient).
An MC with finite states must have a least one recurrent class

ST3236 Stochastic Processes I Classification of States 37 / 47

Example

Now, consider the previous example.

1 2 3 4
11 0 0 0
P= 2 0 0.3 0.7 0 .
30 0.6 0.4 0
4 0.2 0 0.1 0.7

After we find state 2 is recurrent, we can claim state 3 is

recurrent.

ST3236 Stochastic Processes I Classification of States 38 / 47

Example

Consider the MC in following diagram. Figure out whether each state

is recurrent or transient.

ST3236 Stochastic Processes I Classification of States 39 / 47

Reducible Chains

For reducible chains, there are multiple classes:

Transient class
in the long run, the probability stays in this class is 0
Recurrent class
When there are finite states, there must be at least one recurrent
class
If Ck is a recurrent class, then Pij = 0 for any i ∈ Ck and j ∈
/ Ck
(Ck is kind of absorbing class)
Figure out the prob. of entering this class
The probability can be found by first step analysis
Given X0 = i, in the long run, we have the prob. that the process
stays in each class

ST3236 Stochastic Processes I Classification of States 40 / 47

Example

Consider the Markov chain.

1 2 3 4 5
1 0.3 0.7 0 0 0 
2 0.5 0.5 0 0 0 
P= 3 0

0 1 0 0 .

4 0 0 0.4 0.4 0.2
 
5 0.1 0.1 0 0.2 0.6

What will happen in the long run?

Remark. Now we have to consider different initial states.

ST3236 Stochastic Processes I Classification of States 41 / 47

Example

To answer the questions, first we check this MC

it is a reducible MC, with 3 classes
Class 1: {1, 2}
Class 2: {3}, an absorbing state
Class 3: {4, 5}
Draw the diagram and check the flow

Note. Class 1 is an absorbing class. Class 2 is an absorbing class. Both

are recurrent.
Consider Class 3. Note that P43 = 0.4 and 3 is an absorbing state, so
f33 ≤ 0.6 < 1. Therefore, 4 is transient, so Class 3 is transient, with
limiting prob. 0.

ST3236 Stochastic Processes I Classification of States 42 / 47

Example

Starting from state 1 or 2.

Since state 1 and 2 are in class 1, which is an absorbing class.
(n) (n) (n)
Hence, P13 = P14 = P15 = 0 for any n, and the limit is 0.
The process will stay in class C1 forever.

Starting from state 3.

State 3 is an absorbing state.
Obviously, there is

lim P (Xn = 3|X0 = 3) = 1, lim P (Xn = i|X0 = 3) = 0, i = 1, 2, 4, 5.

n→∞ n→∞

ST3236 Stochastic Processes I Classification of States 43 / 47

Example
Starting from state 4 or 5
Now we already know there are two absorbing classes. We wonder
what is the prob. being absorbed in each class.
Build a new MC, where we use A = {1, 2} to denote Class 1.
A 3 4 5
A 1 0 0 0
3 0 1 0 0
P= .
4 0 0.4 0.4 0.2

5 0.2 0 0.2 0.6

Let T = min{n : Xn = A or 3}.

Let ui = P (XT = A|X0 = i), i = 4, 5. According to FSA, we have


 uA = 1
u3 = 0

 u4 =
 0.4u3 + 0.4u4 + 0.2u5
u5 = 0.2uA + 0.2u4 + 0.6u5


Solve it, there is u4 = 0.2, u5 = 0.6.

ST3236 Stochastic Processes I Classification of States 44 / 47
Example

Starting from state 4 or 5

For the new MC, the process will stay at either A or 3 in the long run
Therefore, we further have

P (XT = 3|X0 = 4) = 0.8, P (XT = 3|X0 = 5) = 0.4.

So, when n → ∞, we have that

(n) (n) (n)
P (Xn ∈ C1 |X0 = 4) → 0.8, P43 → 0.2, P44 → 0, P45 → 0.

and
(n) (n) (n)
P (Xn ∈ C1 |X0 = 5) → 0.6, P53 → 0.4, P54 → 0, P55 → 0.

ST3236 Stochastic Processes I Classification of States 45 / 47

Summary

For a reducible MC, how to derive the long-run performance?

First, we figure out all the classes
Then, we set up a new MC in the following way:
Transient classes: no change
Recurrent classes
One recurrent class Ck is abbreviated by one absorbing state k in
the new MC P
For this k, set Pkk = 1, and Pik = j∈Ck Pij
The new MC has transient states and absorbing states only
Consider each initial state X0 = i
(n)
If state i is recurrent, then Pik → 0 for any k not communicate
with i;
If state i is transient, then we have

(n) 0, jis transient;
Pij →
ui (k), j ∈ Ck .

Here, ui (k) is the prob. being absorbed by k in the new MC,

given X0 = i. It can be found by first step analysis.

ST3236 Stochastic Processes I Classification of States 46 / 47

Summary: Classification of States

Accessibility
Communication and communication class
It is an equivalent class
It can pass the transient/recurrent status
Reducible chains and the typical form
Recurrent/Transient states
Return probability and first return probability: definition,
difference and connection
Definition of recurrent/transient states
Theorem about P the number of revisits
(n)
Theorem about Pii
Recurrent/transient classes
Long-run performance of reducible chains

ST3236 Stochastic Processes I Classification of States 47 / 47