IE 325 STOCHASTIC MODELS

HOMEWORK 4 SOLUTIONS

SPRING 2024

1. Consider the Markov chains (MC) whose transition probability matrices are given below. For each
Markov chain:
(a) What are the communicating classes? Specify the closed classes, if any.
(b) Is the MC irreducible?
(c) Classify the states.
(d) Is the MC ergodic?
(1)
0 1 2 3 4
 
0 0 0.5 0.5 0 0
1  0.5 0 0 00.5
 
 
Pa = 2 
 0.5 0 0.5 0 0 
3  0.5 0.5 0 0 0 
 

4 0 0.5 0.5 0 0
(2)
0 1 2 3
 
0 0.3 0.7 0 0
 
1
 0 0 0.4 0.6 
Pb = 
2
 0.2 0.2 0.6 0  
3 0.1 0.5 0 0.4
(3)
0 1 2 3
 
0 0 1 0 0
 
1
0 0 1 0
Pc = 
2
0 0 0 1
3 0 0 0 1
Solution. [(1)]

(a) C1 = {0, 1, 2}, C2 = {3}, C3 = {4}.

A communicating class is called closed class if there is no transition from a state within this class
to a state out of this class. In this MC, C1 is a closed class.
(b) Since there are three communicating classes, this MC is not irreducible.
1
2 SPRING 2024

(c) C1 = {0, 1, 2}(positive recurrent)

C2 = {3} (transient)
C3 = {4} (transient)
(d) Since this MC is not irreducible, it can be concluded that it is not ergodic.
[(2)]

(a)
C1 = {0, 1, 2, 3}
(b) Since there is only one communicating class, this MC is irreducible.
(c) C1 = {0, 1, 2, 3}(positive recurrent, aperiodic)

(d) Since this MC is irreducible, positive recurrent, and aperiodic, it can be concluded that it is
ergodic.

[(3)]

(a) C1 = {0}, C2 = {1}, C3 = {2}, C4 = {3}.C4 is a closed class.

(b) Since there are four communicating classes, this MC is not irreducible.
(c) C1 = {0} (transient)
C2 = {1} (transient)
C3 = {2} (transient)
C4 = {3} (absorbing)

(d) This MC is not irreducible or positive reccurent. Therefore, it can be concluded that it is not
ergodic.
2. Consider the Markov chains whose transition probability matrices are given below. For each Markov
chain, classify its states and determine if the Markov chain is ergodic. What can you say about the limit
behavior of each Markov chain?
(a)
0 1 2
 
0 0 0.5 0.5
Pa = 1  0.5 0 0.5 
 

2 0.5 0.5 0
 IE 325 STOCHASTIC MODELS HOMEWORK 2 SOLUTIONS 3

(b)
0 1 2 3
 
0 0 0 0 1
 
1 0 0 0 1
Pb =  
2  0.5
 0.5 0 0
3 0 0 1 0
(c)
0 1 2 3 4
 
0 0.5 0 0.5 0 0
1  0.25 0.5 0.25 0 0 
 
 
Pc = 2 
 0.5 0 0.5 0 0 
3 0 0 0 0.5 0.5 
 

4 0 0 0 0.5 0.5
(d)
0 1 2 3 4
 
0 0.25 0.75 0 0 0
1 0.5 0.5 0 0 0
 
 
Pd = 2 
 0 0 1 0 0
1 2
3 0 0 0
 
3 3
4 1 0 0 0 0

3 A professor continually gives exams to her students. She can give three possible types of exams, and
her class is graded as either having done well or badly. Let pi denote the probability that the class does
well on a type i exam, and suppose that p1 = 0.3, p2 = 0.6, and p3 = 0.9. If the class does well on an
exam, then the next exam is equally likely to be any of the three types. If the class does badly, then the
next exam is always type 1. In the long run, what proportion of exams are type i, i = 1, 2, 3?
Solution.

4. Mark the following statements as TRUE or FALSE.

4 SPRING 2024

(a) A MC with a periodic state, cannot be ergodic.

(b) If a state j in some MC is transient, it will be visited infinitely many times.
(c) If you are given that a MC is aperiodic, positive recurrent, and irreducible, then you don’t need
any additional information to determine if that MC is ergodic.
(d) If you are given that a MC is periodic and irreducible, then you don’t need any additional
information to determine if that MC is ergodic.
(e) A MC with three communicating classes cannot be ergodic.
(f) "A MC with at least two states, one of which is an absorbing state, may be ergodic."
Solution.
(a) TRUE. A MC needs to be positive recurrent, irreducible and aperiodic, to be ergodic.
(b) FALSE. A transient state will not be visited again after the MC leaves the state. Therefore, it
wil be only visited a finite number of times.
(c) TRUE. All the necessary conditions are provided. One may determine this MC is ergodic.
(d) TRUE. Although all necessary conditions are not given, the one knows the MC does not satisfy
the aperiodicity condition. Therefore, it can be concluded that this MC is not ergodic.
(e) TRUE. Three communicating classes mean that the MC is not irreducible. Therefore, it cannot
be ergodic either.
(f) FALSE. An absorbing state prevents irreducibility. Irreducibility is a condition of ergodicity.
Therefore, a MC with an absorbing state cannot be ergodic.
5. Consider two urns A and B containing a total of four balls. An experiment is performed in which a
ball is selected at random (all selections equally likely) at time t = 1, 2, ... from among the totality of four
balls. Then, an urn is selected at random with equal probabilities and the ball previously drawn is placed
in this urn. The state of the system at each trial is represented by the number of balls in A. Calculate
the expected number of balls in urn A in the long run?
Solution. Let (Xn )n≥0 be a Markov Chain denoting the number of balls in urn A at time n with
state space E = {0, 1, 2, 3, 4}. The transition probability matrix is defined below:

0 1 2 3 4
 
0 0.5 0.5 0 0 0
1  0.125 0.5 0.375 0 0
 

 
P = 2 0 0.25 0.5 0.25 0  ,
3 0 0 0.375 0.5 0.125 
 

4 0 0 0 0.5 0.5

Let us analyze the probabilities.

State 0: If at time n there are no balls in A, then with probability 1, we pick a random ball from B and
then with equal probability we either put in A or back in B. By symmetry, we can argue for State 4.

State 1: Given that at time n we have only one ball in urn A,

• P10 : To have an empty urn at the next draw, one can observe that the probability of picking a
ball from urn A is 0.25 which is then transferred to urn B with probability 0.5 making it equal
to 0.125.
• P12 : To have two balls in urn A, the probability of picking a ball from urn B is 0.75 which is then
transferred to urn A with probability 0.5 making it equal to 0.375.
• P11 : To keep the number of balls constant, the only possible ways are to choose a ball from an
urn and to keep it in the same urn from where it was drawn. With probability 0.125, the ball
chosen from A is kept in A. This includes probability of picking a ball from A (0.25) and keeping
 IE 325 STOCHASTIC MODELS HOMEWORK 2 SOLUTIONS 5

it back in A (0.5). With probability 0.375, the ball chosen from B is kept in B. This includes
probability of picking a ball from B (0.75) and keeping it back in B (0.5).(Remember there are 3
balls in B and a single ball in A.
By symmetry, we can argue for State 3.

State 2: Given that at time n we have two balls in urn A,

• P21 : One can observe that the probability of picking a ball from urn A is 0.5 which is then
transferred to urn B with probability 0.5 making it equal to 0.25.
• P23 : To have three balls in urn A, the probability of picking a ball from urn B is 0.5 which is
then transferred to urn A with probability 0.5 making it equal to 0.25.
• P22 : To keep the number of balls constant, the only possible ways are to choose a ball from an urn
and to keep it in the same urn from where it was drawn. With probability 0.25, the ball chosen
from either one of the two nodes is kept back in the same node. (Remember the probability of
picking a ball initially is 0.5 for both urns)
Then the equations to calculate the limiting probabilities are as follows:

π0 = 0.5π0 + 0.125π1
π1 = 0.5π0 + 0.5π1 + 0.25π2
π2 = 0.375π1 + 0.5π2 + 0.375π3
π3 = 0.25π2 + 0.5π3 + 0.5π4
π4 = 0.125π3 + 0.5π4
4
X
πj = 1
j=0

The answers are as follows: π0 = 0.0625, π1 = 0.25, π2 = 0.375, π3 = 0.25, π4 = 0.0625. Let X denote the
number of balls in A in the long run. Then,

E[X] = 0.25 + 2(0.375) + 3(0.25) + 4(0.0625) = 2

6. Susan, Karen and Jane are three friends. Each of them has a distinct favourite color. Susan’s favourite
color is blue, Karen’s favourite color is pink and Jane’s favourite color is orange. Susan has 1 blue and 4
orange cards. Karen has 3 pink, 2 blue and 2 orange cards. Finally, Jane has 4 pink, 3 blue and 2 orange
cards. They want to play a game and Susan starts the game by randomly selecting a card from her cards
and puts it right back. For the following stages, a card is randomly selected from the cards of the person
whose favourite color was previously selected. In the long run, what proportion of the selected cards are
blue? What proportion are pink? What proportion are orange?
Solution. Let Xn denote the color of the selected card at stage n. Then (Xn )n≥0 is a Markov Chain
on state space E = {B, P, O}. Using the information given in the question, the one-step transition
probability matrix can be written as follows:

B P O
 
1 4
B 5 0 5
 
2 3 2
P = P
 
7 7 7 
 
3 4 2
O 9 9 9

The probabilities depend on the color selected in the previous trial. Based on the color, the concerned
girl selects the next color card on the next trial. For example consider Ppo . This means at the nth trial,
a pink card is selected which means Karen will select the next card from her stack of cards because pink
6 SPRING 2024

is her favorite color. Karen has 3 pink, 2 blue, and 2 orange cards in her stack. The probability that she
chooses orange is 27 . Likewise, all the probabilities are calculated accordingly.
To find the long run probabilities, one needs to solve π = π · P and π · 1 = 1. Therefore the following
equalities are solved:
1 
5 0 45
h i h i  
2 3 2
π1 π2 π3 = π1 π2 π3 ·  7 7 7
3 4 2
9 9 9
1 2 3
π1 = π1 + π2 + π3
5 7 9
3 4
π2 = π2 + π3
7 9
4 2 2
π3 = π1 + π2 + π3
5 7 9
1 = π1 + π2 + π3
25 28 36
π1 = , π2 = , π3 = .
89 89 89
Therefore,
• 28.09% of the selected cards are blue.
• 31.46% of the selected cards are pink.
• 40.45% of the selected cards are orange.
7. Two urns A and B contain a total number of k balls. In each step, urn B is chosen with probability
p (0 < p < 1/2), and urn A is chosen with probability 1 − p. Then a ball is selected from that urn and
placed in other urn. If urn A becomes empty we transfer 0 balls from urn A to urn B with probability
1 − p, and 1 ball from urn B to A with probability p.
(a) Model this process as a Markov chain.
(b) Determine the one-step transition probability matrix.
(c) Does the Markov chain have a limiting distribution? If so, find the limiting distribution.
Solution.
(a) Let (Xn )n≥0 denote the number of balls in urn A at time n which is dependent on the previous
trial. Therefore it is a Markov Chain with state space E = {0, 1, 2, ..., k}. The state transition
diagram is as follows:
p p p

1−p 0 1 2 ... k−1 k p

1−p 1−p 1−p

(b)
0 1 2 3 4 ··· k−1 k
 
0 1−p p 0 0 0 ··· 0 0
1 1 − p 0 p 0 0 ··· 0 0
 
 
2 0 1 − p 0 p 0 ··· 0 0
P =  
3 0 0 1−p 0 p ··· 0 0
 
.. 
 .. .. .. .. .. .. .. .. 
.

. . . . . . . .
k 0 0 0 0 0 ··· 1−p p

(c) The chain is irreducible since all states communicate with each other. It is also aperiodic since
it includes a self-transition, P00 > 0. Since it is a finite state space Markov Chain, these two
 IE 325 STOCHASTIC MODELS HOMEWORK 2 SOLUTIONS 7

conditions show that the Markov Chain is ergodic. Let us write the equations for a stationary
p
distribution. For state 0, we can write π0 = (1 − p)π0 + (1 − p)π1 , which results in π1 = 1−p π0 .
For state 1, we can write π1 = pπ0 + (1 − p)π2 = (1 − p)π1 + (1 − p)π2 , which results in
p p
π2 = 1−p π1 . Similarly for any j ∈ E, we obtain πj = απj−1 , where α = 1−p . Note that since
0 < p < 12 , we conclude that 0 < α < 1. We obtain πj = αj π0 , ∀j ∈ E. Finally we must have
1−αk+1
Pk Pk j 1−α
1 = j=0 πj = j=0 α π0 (0 < α < 1) = 1−α π0 (geometric series). Thus, π0 = 1−αk+1 .
1−α
Therefore, the stationary distribution is given by πj = 1−αk+1
αj , ∀j ∈ E.

8. The four towns A, B, C and D are connected by railroad lines as shown in the diagram below. Each

day, in whichever town it is in, a train chooses one of the lines out of that town at random and traverses
it to the next town, where the process repeats the next day.

(a) In the long run, what is the probability of finding the train in town D?
(b) In the long run, what is the probability of finding the train traversing from D to B?
(c) Assume that number of customers get on the train is 3, 5, 6 and 7 if the train departs towns A,
B, C and D, respectively. Calculate the expected number of customers on the train in the long
run.

Solution.

(a) let E = {A, B, C, D} be the towns. Then the transition probability matrix is given by:

A B C D
 
1 1
A 0 2 0 2
1 1 1

B
3 0 3 3

P = ,
C
0 1 0 0
D 12 1
2 0 0

Then the limiting probability equations are as follows:

1 1
πA = πB + πD
3 2
1 1
πB = πA + πC + πD
2 2
1
πC = πB
3
1 1
πD = πA + πB
2 3
1 = πA + πB + πC + πD

Solving these equations gives us πA = 0.25, πB = 0.375, πC = 0.125, πD = 0.25. So probability

of finding the train in D is 0.25.
(b) The probability that the train travels from D to B is πD ∗ PDB = (0.25)(0.5) = 0.125.
8 SPRING 2024

(c) Let N denote the expected number of customers on the train and ni denote the number of
customers get on train at state i.
X
E[N ] = n i πi
i∈E

= n A πA + n b πB + n C πC + n D πD
3 45 3 7
= + + +
4 8 4 4
= 5.125