OPERATIONS RESEARCH

LECTURE FOUR
Markov chains
Lecturer: Dr. Emily Roche
INTRODUCTION
This lecture will focus on probability transition matrix and solving problems involving
Markov chain.
Intended learning outcomes
At the end of this lecture, you will be able to
i. Define Markov chain
ii. Explain properties of a Markov Chain
iii. Formulate transition probability matrix
iv. Solve steady state conditions for a business problem
References
These lecture notes should be supplemented with relevant topics from the books listed
in the Bibliography at the end of the lecture

Transition matrix and State matrix

These are matrices in which the individual elements are in the form of probabilities.

Transition matrix:
Many types of application involve a set of states {𝑆1 , 𝑆2 , … , 𝑆𝑛 } of given population for
instance residence of a city may live downtown or I suburbs, soft drink customers may
buy pepsi-cola, cocacola or another brand and so on.
Members of a given population will change state. The probability that a member of a
population will change state. The probability that a member of population will change
from the 𝑗 𝑡ℎ state to the 𝑖 𝑡ℎ state is given by 𝑃𝑖𝑗 wher 𝑃𝑖𝑗 is a number between 0 and
1. i.e., 0 ≤ 𝑃𝑖𝑗 ≤ 1.
In particular 𝑃𝑖𝑖 is the probability that a member of population will remain in the
𝑖 𝑡ℎ state. If the probability 𝑃𝑖𝑗 = 0, a member is certain not to change from the 𝑗 𝑡ℎ state to
the 𝑖 𝑡ℎ . 𝑃𝑖𝑗 = 1 means that the member is certain to move from the 𝑗 𝑡ℎ state to the
𝑖 𝑡ℎ state.
The collection of all probabilities 𝑃𝑖𝑗 is represented by a square matrix 𝑃 as:

𝑃11 𝑃12 𝑃13 … 𝑃1𝑛 𝑆1

𝑃21 𝑃22 𝑃23 … 𝑃2𝑛 𝑆2
𝑃31 𝑃32 𝑃33 … 𝑃3𝑛 𝑆3 𝑇𝑜
𝑃= ⋮ ⋮ ⋮ ⋱ ⋮ ⋮
𝑃
( 𝑛1 𝑃𝑛2 𝑃𝑛3 ⋯ 𝑃𝑛𝑛 ) 𝑆𝑛
𝑆1 𝑆2 𝑆3 ⋯ 𝑆𝑛
𝐹𝑟𝑜𝑚

The matrix 𝑃 is called the transition matrix. The sum of elements in each column of 𝑃 is
one. A matrix that has this property is called a Stochastic matrix.
A stochastic matrix is a matrix 𝑃 that has each element as a number between 0 and 1 i.e.,
0 ≤ 𝑃 ≤ 1, and the sum of elements in each column is one.

Example
1 1 1
2 3 6
1 1 0.1 0.8 1
1 0
𝐴=( ); 𝐵= 0 ; 𝐶 = (0.2 0.1 0 )
0 1 4 2 0.7 0.2 0.1
1 2 1
(4 3 3)

𝐴 and 𝐵 are stochastic matrices because each of their elements are non-negative and they
sum to 1 in each column.
𝐶 is not stochastic matrix because the elements in the 2𝑛𝑑 and 3𝑟𝑑 column do not sum to
one.
State matrix:
A state matrix of population is a column matrix whose entries represent portions of the
total population that are in each of the various states.
For example, consider a population of 10,000 with the following states
State Number in state
𝑆1 Under 21 years old 2, 500
𝑆2 21 − 65 years old 4, 500
𝑆3 Over 65 years old 3, 000

The portions of the total population in each state will be given as:
2, 500 4,500 3,000
𝑆1 = = 0.25; 𝑆2 = = 0.45; 𝑆3 = = 0.3
10, 000 10,000 10,000

The state matrix therefore becomes;

0.25
𝑋 = (0.45)
0.3

In general, a state matrix of population with 𝑛 states having portions of 𝑋1 , 𝑋2 , 𝑋3 , … , 𝑋𝑛

is
𝑋1
𝑋2
𝑋 = 𝑋3
⋮
(𝑋𝑛 )
Where 𝑋𝑖 = fraction/portion of; 𝑋1 + 𝑋2 + 𝑋3 + ⋯ + 𝑋𝑛 = 1

Multiplying a transition matrix by a state matrix, we obtain a new state matrix. This
new state matrix gives the portions of the total population that will be in each of the
various states after one transition
 𝑃11 𝑃12 𝑃13 … 𝑃1𝑛 𝑋1 𝑌1
𝑃21 𝑃22 𝑃23 … 𝑃2𝑛 𝑋2 𝑌2
𝑃31 𝑃32 𝑃33 … 𝑃3𝑛 𝑋3 𝑌3
𝑃𝑋 = =
⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
𝑃
( 𝑛1 𝑃𝑛2 𝑃𝑛3 ⋯ 𝑃𝑛𝑛 ) 𝑋
( 𝑛) 𝑌
( 𝑛)
Transition matrix state matrix New state matrix

Example

Two grocery stores in Sabaab compete for the same customers. Although each store has
a few loyal customers, some shop in all stores. After conducting a survey, the
management of one of the stores has determined that 40% of the people who shop at store
𝐴 will shop at the same store, while 60% will go to store 𝐵. For store 𝐵, 80% of the people
will reurn to the same store while 20% will go to store 𝐴. If 3,000 people shoped at 𝐴 and
5,000 people shoped at 𝐵 this week, how many will shop at each store next week?

Solution

3
0.4 0.2
𝑃=( ) 𝑋0 = (8)
0.6 0.8 5
8
0.4 0.2 0.375 0.275
New state = 𝑃𝑋0 = ( )( )= ( )
0.6 0.8 0.625 0.725

The number of people who will shop at the different stores next week will be:

𝐴 = 0.275 × 8,000 = 2,200

𝐵 = 0.725 × 8,000 = 5,800

Definition

Markov chain, named after the Russian mathematician Andrew Markov, is an

experiment consisting of the sequence of trials for which an outcome of each trial depends
on the outcome of the previous trial
Markov processes are defined as a set of trials which follow a certain sequence depending
on the transition probabilities. These probabilities indicate how a particular activity or
product moves from one state to another.

i.e.

0.375 0.275
𝑋0 = ( ); 𝑋1 = 𝑃𝑋0 = ( ); 𝑋2 = 𝑃𝑋1
0.625 0.725

Illustration

From the previous example, determine the customer numbers in each state after 3 weeks.

0.275 0.4 0.2 0.275 0.255

𝑋1 = 𝑃𝑋0 = ( ); 𝑋2 = 𝑃𝑋1 = ( )( )= ( );
0.725 0.6 0.8 0.725 0.745
0.4 0.2 0.255 0.251
𝑋3 = ( )( )= ( )
0.6 0.8 0.745 0.749

After 3 weeks;

𝐴 = 0.251 × 8,000 = 2,008 customers

𝐵 = 0.749 × 8,000 = 5,992 customers

𝑵𝒕𝒉 state Markov chain

Let 𝑃 be the transition matrix and 𝑋 be the state matrix. The 𝑛𝑡ℎ state Markov chain is
given by

𝑋𝑛 = 𝑃𝑛 𝑋0

In the previous example, find the 2𝑛𝑑 state matrix (𝑋2 )

0.4 0.2 0.4 0.2 0.375

𝑋2 = 𝑃2 𝑋0 = ( )( )( )
0.6 0.8 0.6 0.8 0.625
0.28 0.24 0.375 0.255
= ( )( )= ( )
0.72 0.76 0.625 0.745

Example

The market research department for a manufacturing plant has determined that a portion
of the population will purchase their product during any given month. It further found
out that of the people who purchased from them, 20% of them will not purchase next
month while 30% who do not purchase their product at any given month will purchase
next month. In a population of 10,000 people, 1,000 people purchased the product this
month. How many will purchase the product in 3 months?

Solution

0.8 0.3 0.1

𝑃=( ) 𝑋0 = ( )
0.2 0.7 0.9
0.8 0.3 0.1 0.35
𝑋1 = ( )( ) = ( )
0.2 0.7 0.9 0.65
0.8 0.3 0.35 0.475
𝑋2 = ( )( )= ( )
0.2 0.7 0.65 0.525
0.8 0.3 0.475 0.5375
𝑋3 = ( )( )= ( )
0.2 0.7 0.525 0.4625

Therefore, those who will purchase = 0.5375 × 10,000 = 5375

Regular Markov chain

A stochastic matrix 𝑃 is called a regular matrix if sme powers of 𝑃 have only positive
entries. This implies that all the elements in 𝑃𝑛 are all positive for 𝑛 = 1, 2, 3, …

Example

0.5 0.25
i. 𝑃=( )
0.5 0.75

𝑃 is regular since it is stochastic and 𝑃1 has only positive entries.

0.5 1 0.75 0.5

ii. 𝑃=( ); 𝑃2 = ( )
0.5 0 0.25 0.5

𝑃 is regular because it is stochastic and 𝑃2 has only positive entries.

0.5 0.5
iii. 𝑃=( )
0.25 0.75

𝑃 is not regular since it is not stochastic (sum of elements in its columns is not equal to 1).

A regular Markov chain is concerned with the long-term trends or steady states after
many trials.
If 𝑃 is a regular matrix then the sequence 𝑃1 , 𝑃2 , 𝑃3 , 𝑃4 , … , 𝑃𝑛 approaches a stable matrix
𝑃̅.
The sequence 𝑃1 𝑋, 𝑃2 𝑋, 𝑃3 𝑋, 𝑃4 𝑋, … approaches 𝑋̅, where 𝑋̅ is called the stable
distribution matrix.
The elements in each column of 𝑃̅ are equal to the corresponding elements in the column
of matrix 𝑋̅. To find 𝑋̅, solve the equation
𝑃𝑋̅ = 𝑋̅
Example
1 1

Find the stable distribution matrix and stable matrix if 𝑃 = (21 4

3)
2 4

Solution
1 1
𝑋 𝑋1 𝑋
Let 𝑋̅ = ( 1 ) ⟹ (21 4
3) (𝑋 ) = ( 1)
𝑋2 2 𝑋2
2 4

𝐼 1 𝐼 1
𝑋1 + 𝑋2 = 𝑋1 − 𝑋1 + 𝑋2 = 0
∴ 2 4 ⟹ 2 4
1 3 1 1
𝑋 + 𝑋 = 𝑋2 𝑋 − 𝑋 =0
2 1 4 2 2 1 4 2
1 1
𝑋2 = 𝑋1
4 2
𝑋2 = 2𝑋1
But, X1 + X 2 = 1
1 2
X1 + 2X1 = 1 ⟹ 𝑋1 = ; 𝑋2 =
3 3

1 1 1
𝑋̅ = (3) 𝑃̅ = (3 3)
2 2 2
3 3 3
Example
3 1 1
4 3 3
1 1 1
Let 𝑃 = 8 3 2
, find the stable distribution matrix.
1 1 1
(8 3 6)

Solution
𝑃𝑋̅ = 𝑋̅
3 1 1
4 3 3
1 1 1 ̅
𝑋 = 𝑋̅
8 3 2
1 1 1
(8 3 6)

3 1 1
𝑋1 + 𝑋2 + 𝑋3 = 𝑋1
4 3 3
1 1 1
𝑋 + 𝑋 + 𝑋 = 𝑋2
8 1 3 2 2 3
1 1 1
𝑋1 + 𝑋2 + 𝑋3 = 𝑋3
8 3 6

1 1 1
− 𝑋1 + 𝑋2 + 𝑋3 = 0
4 3 3 −3𝑋1 + 4𝑋2 + 4𝑋3 = 0
1 2 1
𝑋 − 𝑋 + 𝑋 =0 ⟹ 3𝑋1 − 16𝑋2 + 12𝑋3 = 0
8 1 3 2 2 3 3𝑋1 + 8𝑋2 − 20𝑋3 = 0
1 1 5
𝑋1 + 𝑋2 − 𝑋3 = 0
8 3 6

Eliminating 𝑋1 using equation (𝑖)

12𝑋2 = 16𝑋3
−12𝑋2 + 16𝑋3 = 0
⟹ 4
12𝑋2 − 16𝑋3 = 0 𝑋2 = 𝑋3
3
Substituting for 𝑋2 in equation (𝑖)
16
−3𝑥1 + 𝑋 + 4𝑋3 = 0
3 3
 28 28
3𝑋1 = 𝑋 ⇒ 𝑋1 = 𝑋
3 3 9 3
But 𝑋1 + 𝑋2 + 𝑋3 = 1

28 4 49 9
𝑋1 + 𝑋2 + 𝑋3 = 1 ⇒ 𝑋 =1 ∴ 𝑋3 =
9 3 9 3 49

28 12 9
𝑋1 = ; 𝑋2 = ; 𝑋3 =
49 49 49

28 28 28 28
49 49 49 49
12 12 12 12
Thus 𝑋̅ = 49
𝑃̅ = 49 49 49
9 9 9 9
(49) (49 49 49)

Areas of application of Markov chains

The Markov processes or chains are frequently applied as follows: -

Brand Switching - By using the transitional probabilities, we can be able to express the
way consumers switch their tastes from one product to another.

Insurance industry - Markov analysis may be used to study the claims made by the
insured persons and decide the level of premiums to be paid in future.

Movement of urban population - By formulating a transition matrix for the current

population in the urban areas, one can be able to determine what the population will be
in say 5 years.

Movement of customers from one bank to another - Customers tend to look for efficient
banks. Therefore, at a certain time when a given bank improve on their customer
satisfaction it will tend to attract several customers who will move from certain banks to
more efficient ones.
Bibliography
Lucey, T. (2002). Quantitative Techniques (6th ed.). Cengage Learning.

Taha, H. A. (2017). Operation Research An introduction (10th ed.). Prentice-Hall, Inc.