Markov Chains

(Part 3)

State Classification

Markov Chains - 1
State Classification
Accessibility

State j is accessible from state i if

pij(n) >0 for some n>= 0, meaning that starting at state i,
there is a positive probability of transitioning to state j in
some number of steps.
This is written j i
State j is accessible from state i "j if and only if there is
a directed path from i to j in the state transition
diagram.
Note that every state is accessible from itself because
! definition and
we allow n=0 in the above
p(0)ii=P(X0=i | X0=i)=1>0.
Markov Chains - 2
State Classification Example 1
Consider the Markov chain Which states are accessible
from state 0?
&0.4 0.6 0 0 0#
$0.5 0.5 0 0 0! States 0 and 1 are accessible
P=$ 0 0 0 .3 0 .7 0 ! from state 0
$0 0 0.5 0.4 0.1! Which states are accessible
$% 0 0 0 0.8 0.2!"
from state 3?
States 2, 3, and 4 are
Draw its state transition diagram accessible from state 3
0.6 Is state 0 accessible from state
0.4 0 1 0.5 4?
No
0.5
0.7 0.1

0.3 2 3 4 0.2
Markov Chains - 3
0.5 0.4 0.8
State Classification Example 2
Now consider a Markov chain Is state 2 accessible from state 0?
with the following state Yes
transition diagram Is state 0 accessible from state 2?
No
Is state 1 accessible from state 0?
Yes
Is state 0 accessible from state 1?
No
Example 2

Markov Chains - 4
State Classification
Communicability

States i and j communicate if state j is accessible from

state i, and state i is accessible from state j (denote j i)
Communicability is
Reflexive: Any state communicates with itself
Symmetric: If state i communicates with state j, then state j
communicates with state i
Transitive: If state i communicates with state j, and state j
communicates with state k, then state i communicates with state k
For the examples, which states communicate with each
other?

Markov Chains - 5
State Classification
Communicability

Example 1: 0.6

0.4 0 1 0.5
01, 234
0.5
0.7 0.1

0.3 2 3 4 0.2

0.5 0.4 0.8

Example 2:

00, 11, 22

Markov Chains - 6
State Classes

Two states are said to be in the same class if the two

states communicate with each other, that is i j, then i
and j are in same class.
Thus, all states in a Markov chain can be partitioned
into disjoint classes
If states i and j are in the same class, then i j.
If a state i is in one class and state j is in another class, then i
and j do not communicate.

How many classes exist in the examples?

Which states belong to each class?

Markov Chains - 7
State Classes

Example 1: 0.6

0.4 0.5
01, 234
0 1
2 classes {0,1} {2,3,4}
0.5
0.7 0.1

0.3 2 3 4 0.2

0.5 0.4 0.8

Example 2:
00, 11, 22
3 classes {0} {1} {2}
Markov Chains - 8
Gambler s Ruin Example

Consider the gambling game with probability p=0.4 of

winning on any turn
State transition diagram and one-step transition
probability matrix: 0.4 0.4

1 0 1 2 3 1

0 1 2 3 0.6 0.6
0 "1 0 0 0%
$ '
1 $0.6 0 0.4 0 '
2 $ 0 0.6 0 0.4'
$0
3 # 0 0 1 '&
How many classes are there?
Markov Chains - 9
Three: {0} {1,2} {3}
!
Irreducibility
A Markov chain is irreducible if all states belong to one
class (all states communicate with each other).
If there exists some n for which pij(n) >0 for all i and j,
then all states communicate and the Markov chain is
irreducible.
If a Markov chain is not irreducible, it is called reducible.
If a Markov chain has more than one class, it is
reducible.
Are the examples reducible or irreducible?
Ex 1: Reducible {0,1} {2,3,4}
Ex 2: Reducible {0} {1} {2}
Gamblers Ruin Ex: Reducible {0} {1,2} {3}
Markov Chains - 10
Examples of Irreducible Chains
Weather example 1-p
1-q
p Sun Rain
0 1

Inventory example
P(D = 0)

P(D = 1) P(D = 2)

P(D =!2)
P(D " 3) 0 1 2 3 P(D = 0)
! ! P(D = 1)
P(D " 1) P(D = 1)
! P(D = 0) P(D = 0)
! P(D " 2) !
! ! P(D!" 3)
! !
! Markov Chains - 11

!
Periodicity of the Gambler s Ruin
0.4 0.4

1 0 1 2 3 1

0.6 0.6

Observe: if you start in State 1 at time 0, you can only

come back to it in times 2, 4, 6, 8,
In other words, 2 is the greatest common denominator of
all integers n > 0, for which pii(n) > 0
We say, the period of State 1 is 2. The period of State 2
is also 2. And observe, they are in the same class.
State 0 has a period of 1, called aperiodic
Markov Chains - 12
Periodicity

The period of a state i is the greatest common

denominator (gcd) of all integers n > 0, for which
pii(n) > 0
Periodicity is a class property
If states i and j are in the same class, then their periods are the
same
State i is called aperiodic if there are two consecutive
numbers s and (s+1) such that the process can be in
state i at these times, i.e., the period is 1

Markov Chains - 13
Periodicity Examples
Which of the following Markov chains are aperiodic?
Which are irreducible?
&1 1 0 0#
&1 2 0# $ 2 2 !
&0 1 0# $ 3 3 ! $ 1 1 0 0!
P = $0 0 1! P = $1 0 1 ! P =$ 2 2 !
$% 1 0 0!" $ 2 2!
2 1
$% 0 14 3 4!" $0 0
3 3!
Irreducible, because all $ 1 3 !
0 0
states communicate Irreducible
$
% 4 4!"
Period =3 Aperiodic
1 1
Reducible, 2 classes
2/3 1/2 Each class is aperiodic
0 1 2 1/2 1/3
0 1 2
1 1/3 3/4 1 3
1/2 1/4 0 2
1/2 1/2 2/3 3/4
1/2 1/4
Markov Chains - 14
Transient States
Consider the gambling example again:
Suppose you are in state 1. What is the probability that you will
never return to state 1 again?
For example, if you win in state 1, and then win again in state 2,
then you will never return to state 1 again. The probability this
happens in 0.4*0.4 = 0.16
Thus, there is a positive probability that, starting in state 1, you
will never return to state 1 again.
State 1 is called a transient state.
In general, a state i is said to be transient if, upon
entering state i, there is a positive probability that the
process may never return to state i again
A state i is transient if and only if there exists a state j
(different from i) that is accessible from state i, but i is not
accessible from j
In a finite-state Markov chain, a transient state is Markov
visited
Chains - 15

only a finite number of times

Recurrent States
A state that is not transient is called recurrent.
State i is said to be recurrent if, upon entering state i,
the process will definitely return to state i
Since a recurrent state definitely will be revisited after
each visit, it will be visited infinitely often.
A special type of recurrent state is an absorbing state,
where, upon entering this state, the process will never
leave it. State i is an absorbing state if and only if pii = 1.
Recurrence (and transience) is a class property
In a finite-state Markov chain, not all states can be
transient
Why? Because there has to be another state j to move to, so
there would have to be states
Markov Chains - 16
Transient and Recurrent States
Examples

Gambler s ruin:
0.4 0.4
Transient states: {1,2}
Recurrent states: {0} {3} 1 0 1 2 3 1
Absorbing states: {0} {3} 0.6
0.6
Inventory problem
Transient states: None
Recurrent states: {0,1,2,3} P(D = 0)
Absorbing states: None P(D = 1) P(D = 2)

P(D =!2)
P(D " 3) 0 1 2 3 P(D = 0)
! ! P(D = 1)
P(D " 1) P(D = 1)
! P(D = 0) P(D = 0)
! P(D " 2) !
! Markov Chains - 17
! P(D!" 3)
! !
!
Examples of Transient and Recurrent
States
Transient {0} {1} Aperiodic
Absorbing {2} Aperiodic
1 1

Recurrent {0,1,2}
Period = 3

Transient {0,1}, Period = 2

Recurrent {2,3}, Period = 2 Markov Chains - 18
Recurrent {0,1}, Aperiodic
Ergodic Markov Chains

In a finite-state Markov chain, not all states can be

transient, so if there are transient states, the chain is
reducible
If a finite-state Markov chain is irreducible, all states
must be recurrent
In a finite-state Markov chain, a state that is recurrent
and aperiodic is called ergodic
A Markov chain is called ergodic if all its states are
ergodic.
We are interested in irreducible, ergodic Markov
chains
Markov Chains - 19