For solutions subscribe to www.youtube.

com/rohitpathak
Problems on
Markov chain
1. Show that If P is the tpm of a homogeneous Markov chain, then the n step tpm
is given by
P (n) = P n = P n−1 × P.
2. Two manufacturers A and B are competing with each other in a restricted market.
Over the years A’s costumers have exhibited a high degree of loyalty as measured
by the fact that customers are using A’ product 80% of the time. Also the cus-
tomers of A purchasing the product from B have switched back to A’s product
60% of the time. (a) Construct and interpret the state transition matrix in terms
of (i) retention and loss (ii) retention and gain. (b) Calculate the probability of a
customer purchasing A’s product at the end of the second period.
3. The school of international studies for population found out by its survey that the
mobility of the population of a state to village, town and a city is in the following
percentages-
To
Village Town City
From Village 50 30 20
Town 10 70 20
City 10 40 50
What will be the proportion of population in village town and the city after two
years, given that the present population has proportions of 0.7, 0.2 and 0.1 in the
village, town and city respectively? What will be the respective proportions in
the long run?
4. A salesman’s territory consists of cities A, B and C. He never sells in the same city
on successive days. If he sells in city A, then next day he sells in city B. However
if he sells on either B or C, then next day he is twice as likely to sell in city A as
in the other city. In the long run how often does he sell in each of the cities?
5. Assume that the weather Fair, Cloudy and Rainy in a certain locality can be
modeled as the homogeneous Markov chain whose tpm is given below-
F C R
 
F 0.8 0.15 0.05
C 0.5 0.3 0.2 
R 0.6 0.3 0.1
[ ]
If the initial state distribution is given by p(0) = 0.7 0.2 0.1 , find p(3) and the
steady state distribution.
6. A professor has three pet questions, one of which occurs on every test he gives.
The students know his habit well. He never uses the same question twice in a row.
If he used question 1 last time, he tosses a coin and uses the question 2 if a head
For solutions subscribe to www.youtube.com/rohitpathak
comes up. If he used question 2 he tosses two coins and switches to question 3 if
both come up with head. If he used question 3, he tosses three coins and switches
to question 1 if all three come up with head. In the long run which question does
he use most often and with how much frequency is it used?

7. A grocer stocks his store with three types of detergents A, B and C. When brand
A is sold out the probability is 0.7 that he stocks up with brand A again. When
he sells out brand B the probability is 0.8 that he will stock up again with brand
B. Finally when he sells out brand C, the probability is 0.6 that he will stock up
with brand C again. When he switches to another detergent he does so for the
remaining two brands. Find the transition matrix. In the long run, how does he
with equal probabilities stock up with detergent?

8. A communication source can generate one of three possible messages 1, 2 and 3

with the following transition probabilities-

Next Massage
1 2 3
Current Massage 1 0.5 0.3 0.2
2 0.4 0.2 0.4
3 0.3 0.3 0.4

Initially, the probabilities of generating the messages 1, 2 and 3 are 0.3, 0.3 and
0.4 respectively. What are the probabilities after 3 periods.

9. A man is at an integral point on the x−axis between the origin and the point 3. He
takes a unit step to the right with probability 1/3 or to the left with probability
2/3, unless he is at the origin, where he takes a step to the right to reach the point
1 or is at the point 3, where he takes a step to the left to reach the point 2. What
is the probability that (i) he is at the point 1 after 3 walks?.

10. A gambler’s luck follows a pattern. If he wins a game, the probability of his
winning the next game is 0.6. However if he loses a game , the probability of his
losing the next game is 0.7. There is an even chance that the gambler wins the
first game. What is the probability that the gambler wins (i) the second game
(ii) the third game?

11. A professor tried not to be late for class too often. If he is late one day, he is 90%
sure to be on time next day. If he is on time, then the next day there is a 30%
chance of his being late. In the long run how often he is late for the class?

12. A manufacturing company has a certain piece of equipment that is inspected at

the end of each day and classified as just overhauled, good, fair or inoperative.
If the piece is is inoperative, it is overhauled, a procedure that takes one day.
Assume that the working condition of the equipment follows a Markov process
For solutions subscribe to www.youtube.com/rohitpathak
with the following transition matrix-
 
0 3/4 1/4 0
0 1/2 1/2 0 
P =0

0 1/2 1/2
1 0 0 0
It costs 125/− to overhaul a machine (including lost time) on an average and
75/− in production is lost if the machine is found to be inoperative. Compute the
expected per day cost of maintenance in the long run.
13. On January 1 this year bakery A had 40% of its local market share while the other
two bakeries B and C had 40% and 20 % of the market share respectively. Based
upon a study by a marketing research firm, the following facts were compiled-
Bakery A retains 90% of its customers while gaining 5% of B’s customers and
10% of C’s customers. Bakery B retains 85% of its customers while gaining 5% of
A’s customers and 7% of C’s customers. Bakery C retains 83% of its customers
and gains 5% of A’s customers and 10% of B’s customers. What will each firms
share be on January 1 next year and what will each firm’s market share be at
equilibrium?
14. Assume that a computer system is in one of the three states busy, idle or under-
going repair. observing its state at 2 P.M. each day, it is believed that the system
behaves like a homogeneous Markov chain with the transition probability matrix-
 
0.6 0.2 0.2
0.1 0.8 0.1
0.6 0 0.4
On a particular day the system may be found with the state probabilities 0.3, 0.45
and 0.25 respectively. Determine the state probabilities (i) after 3 days. (ii) in
the long run.
15. Consider the Markov chain shown in the figure. Assumed that when there is an
arrow from state si to state sj , then pij > 0. Find the equivalence classes for this
Markov chain.
s1 s3 s4 s5

s8 s6
s2

s7

16. Show that all the states of the Markov chain are periodic. Find the period of all
the states.  
0 0.15 0.85 0
0.32 0 0 0.68
P = 0.27 0

0 0.73
0 0.64 0.36 0
For solutions subscribe to www.youtube.com/rohitpathak
 
1 0 0 0
1/4 1/4 1/4 1/4
17. Consider P =  
1/2 0 1/2 0  , then show that s3 , s4 are recurrent but s1 , s2
2/3 0 1/3 0
are transient.
 
1/5 4/5 0
18. Consider P = 9/20 0 11/20 , then show that all the states are recurrent.
1/4 3/4 0
 
1 0 0
19. Consider P = 0.15 0 0.85 , then the show that the states s2 and s3 are
0 0.45 0.55
transient and s1 is recurrent.
20. Three boys A, B and C are throwing a ball to each other. A always throws the
ball to B and B always throws ball to C, but C is just as likely to throw the ball
to B as to A. Find the tpm and show that
(i) the Markov chain is irreducible and regular. and
(ii) all the states are a periodic.
21. Define-
(i) Ergodic Markov chain
(ii) recurrent state
(iii) transient state
(iv) absorbing state. For the following Markov chain, determine whether the
Markov chain is ergodic. Also determine the recurrent, transient and absorbing
states.  
0.2 0.8 0 0
 0 0 0.9 0.10
P = 0.4 0.5 0.1 0 


0 0 0 1
22. Two boys B1 , B2 and two girls G1 , G2 are throwing a ball from one to another.
Each boy throws the ball to the other boy with the probability 1/2 and to each
girl with probability 1/4. On the other hand, each girl throws the ball to each boy
with probability 1/2 and never to the other girl.
(i) Show that the Markov chain is ergodic and regular.
(ii) In the long run how often does each receive the ball?
 
0.20 0.80 0
23. Show that for P =  0 0.45 0.55 , all the states are recurrent.
0.25 0.37 0.38
 
0.6 0 0.40 0
 0 1 0 0
24. Show that in P =  
0.90 0 0.1 0 , the states s2 and s4 are absorbing states.
0 0 0 1
For solutions subscribe to www.youtube.com/rohitpathak
 
0.75 0.25 0
25. Show that If P =  0 0.5 0.5 , then P is regular.
0.6 0.4 0
 
0.5 0 0.5
26. Show that P =  0 1 0  ,is not regular.
0 0 1
 
0.75 0.25 0
27. Show that P =  0 0.5 0.5 , is irreducible.
0.6 0.4 0
 
0 0.15 0.85 0
0.32 0 0 0.68
28. Show that P =  0.27 0
 , not regular ergodic
0 0.73
0 0.64 0.36 0
 
0.5 0 0.5
29. Show that P =  0 1 0  , is neither regular nor ergodic.
0 0 1
 
1 0 0
30. Show that P = 0.3 0.5 0.2 , is absorbing.
0 0 1
 
0.6 0 0.40 0
 0 1 0 0
31. Show that P =  
0.90 0 0.1 0 , is non-absorbing.
0 0 0 1
 
0 2/3 1/3
32. A three-state Markov chain is given by  1/2 0 1/2 . Show that the Markov
01/2 1/2 0
chain is irreducible and all the states are a periodic.