Homework 5: Stats 217

Due on July 27, 2022 at 11:59 pm. Each problem carries 10 points.

1. Consider the following transition probability matrix on state space {0, 1, 2, 3, 4, 5}. Find the
equivalence classes and classify states as transient or recurrent with proper justification.

2. Consider the markov chain corresponding to the random walk on {0, 1, ..., N } with reflecting
barriers at 0 and N (derived in homework 4).

(a) Show that it is irreducible. Is it recurrent or transient?

(b) Compute its stationary distribution when p = 0.5.

1
Stats 217 Homework Set #5
Q1 Markov Chain from transition probability matrix
Label the Markov Chain {𝑋𝑛 }𝑛≥0, the state space 𝑆 = {0,1,2,3,4,5}, and the transition probability matrix
as P. We are given that
1/3 0 2/3 0 0 0
0 1/4 0 3/4 0 0
2/3 0 1/3 0 0 0
𝑃=
0 1/5 0 4/5 0 0
1/4 1/4 0 0 1/4 1/4
[1/6 1/6 1/6 1/6 1/6 1/6]
Reading the transition probability matrix, we have a first pass mapping:

0 → {0,2}
1 → {1,3}
2 → {0,2}

3 → {1,3}
4 → {0,1,4,5} + {2,3} = 𝑆
5→𝑆
Since state 5 leads to the entire state space and state 4 leads to state 5, then state 4 also leads to the
entire state space. Tidying up, we see that:

0 ↔ 2, 1 ↔ 3, 4 ↔ 5, 4,5 → 𝑆
Therefore, the equivalent classes are {0,2}, {1,3}, {4,5}.

Class {4,5} is transient

Since the class {4,5} leads to states {0,1,2,3} which don’t lead back to them i.e. 𝑓(0,4) = 0 the class
{4,5} is transient.

Class {0,2} is recurrent

Consider
∞

𝑓 (0,0) = ∑ 𝑓 (𝑛) (0,0)

𝑛=0

From inspecting P, 𝑓 (0) (0,0)=0 (by definition); 𝑓 (1) (0,0) = 𝑝(0,0) = 1/3

𝑓 (2) (0,0) = 𝑝(0,2)𝑝(2,0) = 4/9

4
𝑓 (𝑛) (0,0) = 𝑝(0,2)𝑝(𝑛−2) (2,2)𝑝(2,0) = , 𝑛≥2
3𝑛
 ∞ ∞
1 1 1 4 1 1 4 1
𝑓 (0,0) = + 4 ∑ 𝑛 = + ∑ 𝑛 = + =1
3 3 3 9 3 3 91 −1
𝑛=2 𝑛=0
3
Therefore, state 0 is recurrent and its entire class is recurrent (lecture 8 Theorem 2.1)

Class {1,3} is recurrent

Similarly: 𝑓 (1) (1,1) = 𝑝(1,1) = 1/4

𝑓 (2) (1,1) = 𝑝(1,3)𝑝(3,1) = 3/20

(𝑛) ( 3 4 𝑛−2
𝑓 1,1) = 𝑝(1,3)𝑝(𝑛−2) (3,3)𝑝(3,1) = ( ) , 𝑛≥2
20 5
∞
1 3 4 𝑛−2 1 3 1
𝑓 (1,1) = + ∑( ) = + =1
4 20 5 4 20 1 − 4
𝑛=2
5
Therefore, state 1 is recurrent and its entire class is recurrent (lecture 8 Theorem 2.1)
Q2
The transition probability matrix from HW4 is given as
0 1 0 0 ⋯ 0 0 0
1−𝑝 0 𝑝 0 ⋯ 0 0 0
0 1−𝑝 0 𝑝 ⋯ 0 0 0
𝑃= ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
0 0 0 0 ⋯ 0 𝑝 0
0 0 0 0 ⋯ 1−𝑝 0 𝑝
[ 0 0 0 0 ⋯ 0 1 0]

Part a) Irreducible and Recurrent

The first pass state relations:

0 → 1, 𝑁 → (𝑁 − 1)
𝑛 → (𝑛 − 1), (𝑛 + 1); 𝑛 ∈ {1, … , 𝑁 − 1}
That is, each interior state (1 to N-1) leads to its left and right neighbours. The end states (0 and N) are
not absorbing and lead to their sole neighbour. From this, we can surmise that the ball can travel to any
position from any position:

𝑆↔𝑆
Therefore, the Markov Chain is irreducible. By Corollary 3.2 (lecture 8), the Markov Chain is recurrent.

Part b)
The stationary vector is given by

𝜋 𝑇 𝑃 = 𝜋 𝑇 , ∑ 𝜋𝑖 = 1
𝑖

And for p=0.5

𝜋0 𝑇 0 1 0 0 ⋯ 0 0 0 𝜋0 𝑇
𝜋1 0.5 0 0.5 0 ⋯ 0 0 0 𝜋1
𝜋2 0 0.5 0 0.5 ⋯ 0 0 0 𝜋2
⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ = ⋮
𝜋𝑁−1 0 0 0 0 ⋯ 0 0.5 0 𝜋𝑁−1
[ 𝜋𝑁 ] 0 0 0 0 ⋯ 0.5 0 0.5 [ 𝜋𝑁 ]
[0 0 0 0 ⋯ 0 1 0]
𝜋1 /2 𝜋0
𝜋0 + 𝜋2 /2 𝜋1
(𝜋1 + 𝜋3 )/2 𝜋2
= ⋮
⋮
𝜋𝑁−2 /2 + 𝜋𝑁 𝜋𝑁−1
[ 𝜋𝑁−1 /2 ] [ 𝜋𝑁 ]
Using the first two entries of the equivalent vectors:
 𝜋1 𝜋2
= 𝜋0 ; 𝜋0 + = 𝜋1 ⇒ 𝜋2 = 𝜋1 = 2𝜋0 = 𝛼
2 2
Subsequent equivalences are of the form (2 ≤ 𝑛 ≤ 𝑁 − 2):
𝜋𝑛−1 + 𝜋𝑛+1
= 𝜋𝑛
2
That is, that the n’th element is the average of its neighbours. Since we have 𝜋2 = 𝜋1 = 𝛼, therefore
𝛼
𝜋𝑛 = 𝛼, 𝑛 ∈ {1, … , 𝑁 − 1}. And again from the last entries, we have 𝜋𝑁 =
2

We know that ∑𝑖 𝜋𝑖 = 1
𝑁 𝑁−1
𝛼 𝛼
1 = ∑ 𝜋𝑖 = 𝜋0 + ∑ 𝜋𝑖 + 𝜋𝑁 = + (𝑁 − 1) 𝛼 + = 𝑁𝛼
2 2
𝑖=0 𝑖=1

Therefore, the stationary distribution is given as:

𝜋0 𝑇 1/2𝑁 𝑇
𝜋1 1/𝑁
𝜋2 1/𝑁
⋮ =
⋮
𝜋𝑁−1 1/𝑁
[ 𝜋𝑁 ] [1/2𝑁]