OR-Notes

J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

Markov processes tutorial class solution

Let:
state 1 = % of fleet buyers having a target % of 100%
state 2 = % of fleet buyers having a target % of 70%
state 3 = % of fleet buyers having a target % of 50%
state 4 = % of fleet buyers having a target % of 20%

then s₁ (the state of the system in year one) is given by

s1 = [0.05, 0.30, 0.45, 0.20] 

and the transition matrix P is given by

P =    | 0.6  0.3  0.1  -   |
       | -    0.7  0.3  -   |
       | -    0.4  0.4  0.2 |
       | -    0.2  0.5  0.3 |

The state-transition diagram is shown below.

We are asked for the % of fleet buyers having a target % for Ford cars of 50%

• in 2 years time; and
• in the long-run.

The state of the system after one year s₂=s₁P

= [0.05, 0.30, 0.45, 0.20] | 0.6  0.3  0.1  -   |
                           | -    0.7  0.3  -   |
                           | -    0.4  0.4  0.2 |
                           | -    0.2  0.5  0.3 |

= [0.03, 0.445, 0.375, 0.15] 

Note here that as a numerical check all the elements of s₂ add to one.

Hence the state of the system in 2 years time s₃ = s₂P

= [0.03, 0.445, 0.375, 0.15] | 0.6  0.3  0.1  -   |
                             | -    0.7  0.3  -   |
                             | -    0.4  0.4  0.2 |
                             | -    0.2  0.5  0.3 |

= [0.018, 0.5005, 0.3615, 0.12] 

Note again that as a numerical check all the elements of s₃ add to one.

Hence the % of fleet buyers having a target % of 50% for Ford cars in 2 years time is 36.15%.

To work out the corresponding % in the long-run we assume that the system reaches equilibrium in the sense that s_t = s_t-1 (=[x₁,x₂,x₃,x₄ say).

Hence from s_t = s_t-1P we have that

[x1,x2,x3,x4] =[x1,x2,x3,x4] | 0.6  0.3  0.1  -   |
                           | -    0.7  0.3  -   |
                           | -    0.4  0.4  0.2 |
                           | -    0.2  0.5  0.3 |

(and note also that x1+x2+x3+x4=1). 

Hence we have the five equations

x1 = 0.6x1
x2 = 0.3x1 + 0.7x2 + 0.4x3 + 0.2x4
x3 = 0.1x1 + 0.3x2 + 0.4x3 + 0.5x4
x4 = 0.2x3 + 0.3x4
x1 + x2 + x3 + x4 = 1

Now from the first equation above 0.4x₁=0 i.e. x₁=0 so substituting this into the other equations above and rearranging we get

0.3x2 = 0.4x3 + 0.2x4  (1)
0.6x3 = 0.3x2 + 0.5x4  (2)
0.7x4 = 0.2x3          (3)
x2 + x3 + x4 = 1       (4)

From equation (3)

x4 = (0.2/0.7)x3       (5)

so substituting equation (5) into equation (1) we get

0.3x2 = 0.4x3 + 0.2(0.2/0.7)x3 
i.e. x2 = [(0.4 + 0.2(0.2/0.7))/0.3]x3  (6)

Substituting equations (5) and (6) into equation (4) we get

x3[[(0.4 + 0.2(0.2/0.7))/0.3] + 1 + (0.2/0.7)] = 1 
i.e. x3 = 0.3559 

Hence from equation (5) we have

x4 = (0.2/0.7)(0.3559) 
i.e. x4 = 0.1017 

and from equation (6) we have

x2 = [(0.4 + 0.2(0.2/0.7))/0.3](0.3559) 
i.e. x2 = 0.5423 

Hence we have

x1 = 0 x2 = 0.5423 x3 = 0.3559 x4 = 0.1017 

As a numerical check we can substitute these values back into our original equations (equations (1)-(5) above). If we do this we will see that the values for x₁, x₂, x₃ and x₄ given above are consistent with these equations (to within rounding errors).

Hence we have that the % of fleet buyers having a target % for Ford cars of 50% in the long-run is 35.59%.

In general it takes a long time for a system to reach the long-run state and hence, in practice, we would not expect this state ever to be reached (due to changing circumstances rendering the transition matrix invalid).

However note that in this particular example the state of the system after just two years (s₃ = [0.018, 0.5005, 0.3615, 0.12]) is close to the long-run system state (= [0, 0.5423, 0.3559, 0.1017]) and so it is likely that we will (effectively) reach the long-run state in just a few years.

For example, the percentage of fleet buyers having a target percentage for Ford cars of 50% the figure after two years is 36.15% and in the long-run is 35.59% - so these figures are very close to each other.

The advantages and disadvantages of using Markov theory to forecast fleet buyers' behaviour include:

• Markov theory simple to apply and understand
• Sensitivity calculations (i.e. "what-if" questions) are easily carried out
• Markov theory gives us an insight into changes in the system over time
• P may be dependent upon the current state of the system (e.g. the transition matrix probabilities may depend upon the % of fleet buyers in a particular system state - for example if a high % of fleet buyers currently have a target percentage of 70% for Ford cars this may influence others to aim for that target percentage). If P is dependent upon both time and the current state of the system i.e. P a function of both t and s_t then the basic Markov equation becomes s_t=s_t-1P(t-1,s_t-1).
• How do we cope with the effect of promotional advertising campaigns?
• Markov theory is only a simplified model of a complex decision-making process.
• What this analysis has neglected is the size of the fleet controlled by each buyer - the behaviour of a buyer with a large fleet is more important than the behaviour of a buyer with a small fleet.