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.

Here we give some more Markov processes examples.

In analysing switching by Business Class customers between airlines the following data has been obtained by British Airways (BA):

Next flight by BA Competition Last flight by BA 0.85 0.15 Competition 0.10 0.90

For example if the last flight by a Business Class customer was by BA the probability that their next flight is by BA is 0.85. Business Class customers make 2 flights a year on average.

Currently BA have 30% of the Business Class market. What would you forecast BA's share of the Business Class market to be after two years?

We have the initial system state s_{1} given by s_{1}
= [0.30, 0.70] and the transition matrix P is given by

P = | 0.85 0.15 |^{2 }= | 0.7375 0.2625 | | 0.10 0.90 | | 0.1750 0.8250 |

where the square term arises as Business Class customers make 2 flights a year on average.

Hence after one year has elapsed the state of the system s_{2}
= s_{1}P = [0.34375, 0.65625]

After two years have elapsed the state of the system = s_{3}
= s_{2}P = [0.368, 0.632]

and note here that the elements of s_{2 }and s_{3} add
to one (as required).

So after two years have elapsed BA's share of the Business Class market is 36.8%

An admissions tutor is analysing applications from potential students for a particular undergraduate course at Imperial College (IC). She regards each potential student as being in one of four possible states:

At the start of the year (month 1 in the admissions year) all potential students are in state 1.

Her review of admissions statistics for recent years has identified the following transition matrix for the probability of moving between states each month:

To 1 2 3 4 From 1 | 0.97 0.03 0 0 | 2 | 0 0.10 0.15 0.75 | 3 | 0 0 1 0 | 4 | 0 0 0 1 |

The admissions tutor has control over the elements in one row of the
above transition matrix, namely row 2.

The elements in this row reflect:

To be more specific, at the start of each month the admissions tutor has to decide the proportion of applicants who should be accepted that month. However she is constrained by a policy decision that, at the end of each month, the total number of rejections should never be more than one-third of the total number of offers, nor should it ever be less than 20% of the total number of offers.

Further analysis reveals that applicants who wait longer than 2 months between applying to IC and receiving a decision (reject or accept) almost never choose to come to IC, even if they get an offer of a place.

Formulate the problem that the admissions tutor faces each month as a linear program. Comment on any assumptions you have made in so doing.

We have the initial system state s_{1} given by s_{1}
= [1, 0, 0, 0] and the transition matrix P given by

P = | 0.97 0.03 0 0 | | 0 0.10 0.15 0.75 | | 0 0 1 0 | | 0 0 0 1 |

Hence after one month has elapsed the state of the system s_{2}
= s_{1}P = [0.97, 0.03, 0, 0]

After two months have elapsed the state of the system = s_{3}
= s_{2}P = [0.9409, 0.0321, 0.0045, 0.0225]

After three months have elapsed the state of the system = s_{4}
= s_{3}P = [0.912673, 0.031437, 0.009315, 0.046575]

and note here that the elements of s_{2}, s_{3} and
s_{4} add to one (as required).

Hence 4.6575% of potential students will have been accepted after 3 months have elapsed.

It is not possible to work out a meaningful long-run system state as the admissions year is only (at most) 12 months long. In reality the admissions year is probably shorter than 12 months.

With regard to the linear program we must distinguish within state 2 (those who have applied to IC but an accept/reject decision has not yet been made) how long an applicant has been waiting.

Hence expand state 2 to states:

Hence we have the new transition matrix

1 2a 2b 3 4 P = 1 | 0.97 0.03 0 0 0 | 2a | 0 0 1-X-Y X Y | 2b | 0 0 0 1-y y | 3 | 0 0 0 1 0 | 4 | 0 0 0 0 1 |

Here X is the reject probability each month for a newly received application and Y is be the acceptance probability each month for a newly received application (these are decision variables for the admissions tutor), where X>=0 and Y>=0.

In a similar fashion y is the acceptance probability each month for an application that was received one month ago (again a decision variable for the admissions tutor).

Each month then, at the start of the month, we have a known proportion in each of the states 1, 2a, 2b, 3 and 4.

Hence the equation for the (unknown) proportions [z_{1},z_{2a},z_{2b},z_{3},z_{4}]
at the end of each month is given by:

where P is the transition matrix given above involving the variables X,Y and y. If we were to write this matrix equation out in full we would have 5 linear equalities. In addition we must have that:

and the policy conditions are:

Hence we have a set of linear constraints in the variables [X,Y,y,z_{1},z_{2a},z_{2b},z_{3},z_{4}]

An appropriate objective function might be to maximise the sum of the acceptance probabilities (Y+y) but other objectives could be suggested for this system.

Hence we have an LP that can be solved to decide X,Y and y each month.

Comments are:

- row 1 of the transition matrix constant throughout the year
- does not take into account any information we might have on how applicants respond to the offers made to them

A petrol station owner is considering the effect on his business (Superpet) of a new petrol station (Global) which has opened just down the road. Currently (of the total market shared between Superpet and Global) Superpet has 80% of the market and Global has 20%.

Analysis over the last week has indicated the following probabilities for customers switching the station they stop at each week:

To Superpet Global From Superpet 0.75 0.25 Global 0.55 0.45

- What will be the expected market share for Superpet and Global after another two weeks have past?
- What would be the long-run prediction for the expected market share for Superpet and Global?

Letting

- state 1 = Superpet
- state 2 = Global

we have the initial system state s_{1} given by s_{1}
= [0.80, 0.20] and the transition matrix P given by

P = |0.75 0.25 | |0.55 0.45 |

Hence after one week has elapsed the state of the system s_{2}
= s_{1}P = [0.71, 0.29] and so after two weeks have elapsed the
state of the system = s_{3} = s_{2}P = [0.692, 0.308] and
note here that the elements of s_{2} and s_{3} add to one
(as required).

Hence the market shares after two weeks have elapsed are 69.2% and 30.8% for Superpet and Global respectively.

Assuming that in the long-run the system reaches an equilibrium [x_{1},
x_{2}] where

[x_{1}, x_{2}] = [x_{1}, x_{2}]P and
x_{1} + x_{2} = 1

we have that

x_{1}= 0.75x_{1}+ 0.55x_{2}(1)

x_{2}= 0.25x_{1}+ 0.45x_{2}(2)

and x_{1}+ x_{2}= 1 (3)

From (3) we have that x_{2} = 1-x_{1}

so substituting into (1) we get

x_{1} = 0.75x_{1} + 0.55(1-x_{1})

i.e. (1-0.75+0.55)x_{1} = 0.55

i.e. x_{1} = 0.55/0.80 = 0.6875

Hence x_{2} = 1-x_{1} = 1-0.6875 = 0.3125

Note that as a check we have that these values for x_{1} and
x_{2} satisfy equations (1) - (3) (to within rounding errors).

Hence the long-run market shares are 68.75% and 31.25% for Superpet and Global respectively.

A company is considering using Markov theory to analyse brand switching between three different brands of floppy disks. Survey data has been gathered and has been used to estimate the following transition matrix for the probability of moving between brands each month:

To Brand 1 2 3 From Brand 1 | 0.80 0.10 0.10 2 | 0.03 0.95 0.02 3 | 0.20 0.05 0.75

The current (month 1) market shares are 45%, 25% and 30% for brands 1, 2 and 3 respectively.

- What will be the expected market shares after two months have elapsed (i.e. in month 3)?
- What is the long-run prediction for the expected market share for each of the three brands?
- Would you expect the actual market share to approach the long-run prediction for the market or not (and why)?

We have the initial system state s_{1} given by s_{1}
= [0.45, 0.25, 0.30] and the transition matrix P given by

P = |0.80 0.10 0.10 | |0.03 0.95 0.02 | |0.20 0.05 0.75 |

Hence after one month has elapsed the state of the system s_{2}
= s_{1}P = [0.4275, 0.2975, 0.2750] and so after two months have
elapsed the state of the system = s_{3} = s_{2}P = [0.4059,
0.3391, 0.2550] and note here that the elements of s_{2} and s_{3}
add to one (as required).

Hence the market shares after two months have elapsed are 40.59%, 33.91% and 25.50% for brands 1, 2 and 3 respectively.

Assuming that in the long-run the system reaches an equilibrium [x_{1},
x_{2}, x_{3}] where

[x_{1}, x_{2}, x_{3}] = [x_{1}, x_{2},
x_{3}]P and x_{1} + x_{2} + x_{3} = 1

we have that

x_{1} = 0.80x_{1} + 0.03x_{2} + 0.20x_{3}

x_{2} = 0.10x_{1} + 0.95x_{2} + 0.05x_{3}

x_{3} = 0.10x_{1} + 0.02x_{2} + 0.75x_{3}

x_{1} + x_{2} + x_{3} = 1

Rearranging we get

0.20x_{1}= 0.03x_{2}+ 0.20x_{3}(1)

0.05x_{2}= 0.10x_{1}+ 0.05x_{3}(2)

0.25x_{3}= 0.10x_{1}+ 0.02x_{2}(3)

x_{1}+ x_{2}+ x_{3}= 1 (4)

Now subtracting equation (3) from equation (2) we get

0.05x_{2} - 0.25x_{3} = 0.05x_{3} - 0.02x_{2}

i.e. 0.07x_{2} = 0.30x_{3}

i.e. x_{2}= (0.30/0.07)x_{3}(5)

Now from equation (4) we have

x_{1} = 1 - x_{2} - x_{3}

so substituting in equation (1) we get

0.20(1 - x_{2} - x_{3}) = 0.03x_{2} + 0.20x_{3}

i.e. 0.20 = 0.23x_{2} + 0.40x_{3}

Substituting from equation (5) for x_{2} we get

0.20 = 0.23(0.30/0.07)x_{3} + 0.40x_{3}

i.e. x_{3} = 0.1443

Hence from equation (5)

x_{2} = (0.30/0.07)x_{3} = 0.6184

and x_{1} = 1 - x_{2} - x_{3} = 1 - 0.6184 -
0.1443 = 0.2373

Note that as a check we have that these values for x_{1}, x_{2}
and x_{3} satisfy equations (1) - (4) (to within rounding errors).

Hence the long-run market shares are 23.73%, 61.84% and 14.43% for brands 1, 2 and 3 respectively.

Have that after two months s_{3} (calculated above) not close
to the long-run market shares and would expect changing circumstances to
render the transition matrix invalid.

In analysing switching between different brands of copper pipe survey data has been used to estimate the following transition matrix for the probability of moving between brands each month:

To Brand 1 2 3 4 From Brand 1 | 0.95 0.02 0.02 0.01 2 | 0.05 0.90 0.02 0.03 3 | 0.10 0.05 0.83 0.02 4 | 0.13 0.13 0.02 0.72

The current (month 1) market shares are 45%, 23%, 20% and 12% for brands 1, 2, 3 and 4 respectively.

- What will be the expected market shares after two months have elapsed (i.e. in month 3)?
- What is the long-run prediction for the expected market share for each of the four brands?
- Would you expect the actual market share to approach the long-run prediction for the market or not (and why)?
- The management of brand 1 are concerned that they should be aiming for a long- run market share of 75% by manipulating the transition probabilities from brand 1 to brands 2, 3 and 4 (as well as the transition probability from brand 1 to brand 1). Formulate the problem of deciding appropriate transition probabilities as a linear program.

We have the initial system state s_{1} given by s_{1}
= [0.45, 0.23, 0.20, 0.12] and the transition matrix P given by

P = | 0.95 0.02 0.02 0.01 | | 0.05 0.90 0.02 0.03 | | 0.10 0.05 0.83 0.02 | | 0.13 0.13 0.02 0.72 |

Hence after one month has elapsed the state of the system s_{2}
= s_{1}P = [0.4746, 0.2416, 0.1820, 0.1018] and so after two months
have elapsed the state of the system = s_{3} = s_{2}P =
[0.494384, 0.249266, 0.16742, 0.08893] and note here that the elements
of s_{2} and s_{3} add to one (as required).

Hence the market shares after two months have elapsed are 49.44%, 24.93%, 16.74% and 8.89% for brands 1, 2, 3 and 4 respectively.

Assuming that in the long-run the system reaches an equilibrium [x_{1},
x_{2}, x_{3}, x_{4}] where

[x_{1}, x_{2}, x_{3}, x_{4}] = [x_{1},
x_{2}, x_{3}, x_{4}]P and x_{1} + x_{2}
+ x_{3} + x_{4} = 1

we have that

x_{1} = 0.95x_{1} + 0.05x_{2} + 0.10x_{3}
+ 0.13x_{4}

x_{2} = 0.02x_{1} + 0.90x_{2} + 0.05x_{3}
+ 0.13x_{4}

x_{3} = 0.02x_{1} + 0.02x_{2} + 0.83x_{3}
+ 0.02x_{4}

x_{4} = 0.01x_{1} + 0.03x_{2} + 0.02x_{3}
+ 0.72x_{4}

x_{1} + x_{2} + x_{3} + x_{4} = 1

Rearranging we get

0.05x_{1}= 0.05x_{2}+ 0.10x_{3}+ 0.13x_{4}(1)

0.10x_{2}= 0.02x_{1}+ 0.05x_{3}+ 0.13x_{4}(2)

0.17x_{3}= 0.02x_{1}+ 0.02x_{2}+ 0.02x_{4}(3)

0.28x_{4}= 0.01x_{1}+ 0.03x_{2}+ 0.02x_{3}(4)

x_{1}+ x_{2}+ x_{3}+ x_{4}= 1 (5)

Now from equation (3) we have

0.17x_{3} = 0.02(x_{1} + x_{2} + x_{4})

and from equation (5) we have

x_{1} + x_{2} + x_{4} = 1 - x_{3}

Hence

0.17x_{3} = 0.02(1-x_{3})

i.e. 0.19x_{3} = 0.02

i.e. x_{3} = (0.2/0.19) = 0.10526

Now subtracting equation (2) from equation (1) we get

0.05x_{1} - 0.10x_{2} = 0.05x_{2} + 0.10x_{3}
- 0.02x_{1} - 0.05x_{3}

i.e. 0.07x_{1}- 0.15x_{2}= 0.05x_{3}(6)

Also substituting for x_{4} from equation (5) in equation (4)
we have

0.28(1 - x_{1} - x_{2} - x_{3}) = 0.01x_{1}
+ 0.03x_{2} + 0.02x_{3}

i.e. 0.28 = 0.29x_{1} + 0.31x_{2} + 0.30x_{3}

i.e. 0.29x_{1}+ 0.31x_{2}= 0.28 - 0.30x_{3 }(7)

Multiplying equation (6) by 0.31 and equation (7) by 0.15 and adding we get

(0.31)(0.07)x_{1} + (0.15)(0.29)x_{1} = (0.31)(0.05)x_{3}
+ (0.15)(0.28) - (0.15)(0.30)x_{3}

and since we know x_{3} = 0.10526 we have x_{1} = 0.59655

Hence from equation (6) we find that x_{2} = 0.24330 and from
equation (5) that x_{4} = 0.05489

Note that as a check we have that these values for x_{1}, x_{2},
x_{3} and x_{4} satisfy equations (1) - (5) (to within
rounding errors).

Hence the long-run market shares are 59.66%, 24.33%, 10.53% and 5.49% for brands 1, 2, 3 and 4 respectively.

Have that after two months s_{3} (calculated above) not close
to the long-run market shares and would expect changing circumstances to
render the transition matrix invalid.

We need a long-run system state of [0.75, x_{2}, x_{3},
x_{4}] where x_{2}, x_{3} and x_{4} are
unknown (but sum to 0.25) and we have a transition matrix given by

P =

| p_{1 }p_{2}p_{3}p_{4}| | 0.05 0.90 0.02 0.03 | | 0.10 0.05 0.83 0.02 | | 0.13 0.13 0.02 0.72 |

where p_{1}, p_{2}, p_{3} and p_{4}
are unknown (but sum to one).

Hence using the equation

[0.75, x_{2}, x_{3}, x_{4}] = [0.75, x_{2},
x_{3}, x_{4}]P

we have the equations

0.75 = 0.75p_{1} + 0.05x_{2} + 0.10x_{3} + 0.13x_{4}

x_{2} = 0.75p_{2} + 0.90x_{2} + 0.05x_{3}
+ 0.13x_{4}

x_{3} = 0.75p_{3} + 0.02x_{2} + 0.83x_{3}
+ 0.02x_{4}

x_{4} = 0.75p_{4} + 0.03x_{2} + 0.02x_{3}
+ 0.72x_{4}

together with

x_{2} + x_{3} + x_{4} = 0.25

p_{1} + p_{2} + p_{3} + p_{4} = 1

Here we have six equations in seven unknowns and so to solve we need an appropriate objective. In order to avoid having to change the transition probabilities too much a suitable objective would be

maximise p_{1}

i.e. find the largest value for the transition probability from brand 1 to itself such that we achieve the long-run market share of 75%.

Hence the LP is

maximise p_{1}

subject to

0.75 = 0.75p_{1} + 0.05x_{2} + 0.10x_{3} + 0.13x_{4}

x_{2} = 0.75p_{2} + 0.90x_{2} + 0.05x_{3}
+ 0.13x_{4}

x_{3} = 0.75p_{3} + 0.02x_{2} + 0.83x_{3}
+ 0.02x_{4}

x_{4} = 0.75p_{4} + 0.03x_{2} + 0.02x_{3}
+ 0.72x_{4}

x_{2} + x_{3} + x_{4} = 0.25

p_{1} + p_{2} + p_{3} + p_{4} = 1

x_{2}, x_{3}, x_{4} >= 0

p_{1}, p_{2}, p_{3}, p_{4} >= 0

An operational researcher is analysing switching between two different products. She knows that in period 1 the market shares for the two products were 55% and 45% but that in period 2 the corresponding market shares were 67% and 33% and in period 3 70% and 30%. The researcher believes that an accurate representation of the market share in any period can be obtained using Markov processes. Assuming her belief is correct:

- Estimate the transition matrix.
- Calculate the market shares in period 4 using the estimated transition matrix.
- If the actual market shares for period 4 were 71% and 29% would you revise your estimate of the transition matrix or not? Give reasons for your decision.

We have that s_{1}, the state of the system in period 1, is
given by s_{1}=[0.55, 0.45] with s_{2}=[0.67, 0.33] and
s_{3}=[0.70, 0.30]

Assuming the researcher is correct then s_{1} and s_{2}
are linked by s_{2} = s_{1}(P) where P is the transition
matrix. We also have that s_{3} and s_{2} are linked by
s_{3} = s_{2}(P).

Now we have that P will be a 2 by 2 matrix, and that the elements of each row of P add to one, so that we can write

P = |x_{1}1-x_{1}|

|x_{2}1-x_{2}|

where x_{1} and x_{2} are unknown.

Using s_{2} = s_{1}(P) we have

[0.67, 0.33] = [0.55, 0.45] |x_{1}1- x_{1}|

|x_{2}1- x_{2}|

and using s_{3} = s_{2}(P) we have

[0.70, 0.30] = [0.67, 0.33] |x_{1}1- x_{1}|

|x_{2}1- x_{2}|

Hence, expanding, we have

0.67 = 0.55x_{1}+ 0.45x_{2}(1)

0.33 = 0.55(1 - x_{1}) + 0.45(1 - x_{2}) (2)

0.70 = 0.67x_{1}+ 0.33x_{2}(3)

0.30 = 0.67(1 - x_{1}) + 0.33(1 - x_{2}) (4)

Equation (2), when rearranged, becomes equation (1) and similarly equation (4), when rearranged, becomes equation (3). Hence we have two simultaneous equations (equations (1) and (3)) in two unknowns.

From equation (1)

x_{1} = (0.67 - 0.45x_{2})/0.55

so substituting for x_{1} in equation (3) we get

0.70 = 0.67[(0.67 - 0.45x_{2})/0.55] + 0.33x_{2}

i.e. (0.70)(0.55) = (0.67)(0.67) - (0.67)(0.45)x_{2} + (0.33)(0.55)x_{2}

i.e. x_{2} = [(0.67)(0.67)-(0.70)(0.55)]/[(0.67)(0.45)-(0.33)(0.55)]

i.e. x_{2} = 0.5325 and

x_{1} = (0.67 - 0.45x_{2})/0.55 = 0.7825

Hence our estimate of the transition matrix P

= |x_{1}1-x_{1}|

|x_{2}1-x_{2}|

= |0.7825 0.2175| |0.5325 0.4675|

Note as a check we can verify that, with this estimated transition matrix,
we have s_{2} = s_{1}(P) and s_{3} = s_{2}(P).

The market shares for period 4 are given by

s_{4} = s_{3}(P)

= [0.70, 0.30] |0.7825 0.2175| |0.5325 0.4675|

i.e. s_{4} = [0.7075, 0.2925]

and note here that the elements of s_{4} add to one (as required).

Hence the estimated market shares for period 4 are 70.75% and 29.25%.

If the actual market shares are 71% and 29% then this compares well with the shares estimated above and so there would seem no reason to revise the estimate of the transition matrix.

An admissions tutor is analysing (with help from the Management School!) applications from potential students for undergraduate courses at Imperial College (IC). A potential student can (for the purpose of preliminary analysis) be regarded as being in one of five possible states:

- State 1: has not applied to IC
- State 2: has applied to IC
- State 3: has applied to IC and has been interviewed
- State 4: has applied to IC and has been rejected
- State 5: has applied to IC and has been made an offer of a place

At the start of the year (month 1 in the admissions year) all potential students are in state 1.

A review of admissions statistics has identified the following transition matrix for the probability of moving between states each month:

To 1 2 3 4 5 From 1 | 0.95 0.05 0 0 0 | 2 | 0 0.2 0.7 0 0.1 | 3 | 0 0 0.3 0.6 0.1 | 4 | 0 0 0 1 0 | 5 | 0 0 0 0 1 |

- What percentage of potential students will have been offered places after 3 months have elapsed?
- Is it possible to work out a long-run system state or not (and why)?
- Formulate the problem of deciding the percentage of potential students who have been offered places in each month up to (and including) the 10th month of the admissions year as a linear program
- Discuss the importance of the objective function of the linear program derived above.
- Discuss what enhancements/changes could be made to the above preliminary analysis in order to enable the admissions tutor to better analyse the admission of students.

We have the states as defined in the question with

s_{1}=[1,0,0,0,0]

and P = | 0.95 0.05 0 0 0 | | 0 0.2 0.7 0 0.1 | | 0 0 0.3 0.6 0.1 | | 0 0 0 1 0 | | 0 0 0 0 1 |

Hence

s_{2} = s_{1}P = [0.95, 0.05, 0, 0, 0]

s_{3} = s_{2}P = [0.9025, 0.0575, 0.035, 0, 0.005]

s_{4} = s_{3}P = [0.857375, 0.056625, 0.05075, 0.021,
0.01425]

Therefore 1.425% of potential students are offered a place after 3 months.

No long-run system state as absorbing states (4 and 5) are present (or because the admissions year restarts after period 12).

Let s_{it} = the proportion in state i at the end of period
t then the matrix equation s_{t} = s_{t-1}(P) t=2,...,12

becomes the linear equations

s_{1t}= 0.95s_{1t-1}t=2,.. .,12

s_{2t}= 0.05s_{1t-1}+ 0.2s_{2t-1}t=2,...,12

s_{3t}= 0.7s_{2t-1}+ 0.3s_{3t-1}t=2,...,12

s_{4t}= 0.6s_{3t-1}+ 1s_{4t-1 }t=2,...,12

s_{5t}= 0.1s_{2t-1}+ 0.1s_{3t-1}+ 1s_{5t-1 }t=2,...,12

with initial conditions

s_{11}= 1 s_{21}= s_{31}= s_{41}= s_{51}= 0

It *does not* matter about the objective function - any linear
function of the variables will do, since there is only *one* feasible
solution to the above system of linear equations.

Points are:

- add more states (e.g. refuses offer, withdraws, etc)
- time alteration of transition matrix e.g. better candidates apply earlier, only interview early in the year, number of applications not spread evenly over the year
- consider departmental pattern
- classes of applicant (e.g. low fee/high fee)
- analysis of results (e.g. how long wait for interview)

A company is considering using Markov theory to analyse brand switching between four different brands of breakfast cereal (brands 1, 2, 3 and 4). An analysis of data has produced the transition matrix shown below for the probability of switching each week between brands.

To brand 1 2 3 4 From brand 1 | 0.5 0.2 0.3 0.0 | 2 | 0.0 0.4 0.4 0.2 | 3 | 0.7 0.0 0.3 0.0 | 4 | 0.8 0.1 0.0 0.1 |

- draw the state-transition diagram
- what will be the market shares in week 3 if the current (week 1) market shares for the four brands are 20%, 30%, 15%, 35% for brands 1, 2, 3, 4 respectively?
- what is the long-run prediction for the market shares for each of the four brands?
- would you expect the actual market shares to approach the long-run prediction for the market or not (and why?)
- what advantages and disadvantages can you think of in using Markov theory to forecast market shares in brand switching?

State-transition diagram easy to draw.

Letting P represent the transition matrix given in the question we have
that s_{1} = [0.2, 0.3, 0.15, 0.35] and so

s_{2} = s_{1}P = [0.485, 0.195, 0.225, 0.095] and s_{3}
= s_{2}P = [0.476, 0.1845, 0.291, 0.0485]

Note that the elements of s_{2} and s_{3} add to one.

Solve the simultaneous equations

[x_{1}, x_{2}, x_{3}, x_{4}] = [x_{1},
x_{2}, x_{3}, x_{4}](P)

and x_{1} + x_{2} + x_{3} + x_{4} =
1

i.e. x_{1} = 0.5x_{1} + 0.7x_{3} + 0.8x_{4}

x_{2} = 0.2x_{1} + 0.4x_{2} + 0.1x_{4}

x_{3} = 0.3x_{1} + 0.4x_{2} + 0.3x_{3}

x_{4} = 0.2x_{2} + 0.1x_{4}

x_{1} + x_{2} + x_{3} + x_{4} = 1

The solution is x_{1} = 0.4879 x_{2} = 0.1689 x_{3}
= 0.3056 x_{4} = 0.0375

Note, after solution, substitute these values back into the equations above to check that they are consistent.

In general it takes a long time for the system to reach the long-run
system state and hence we would not expect that state ever to be reached
(due to changing circumstances rendering the transition matrix invalid).
However note that in this particular example s_{3} = the state
of the system after just 2 weeks (= [0.476, 0.1845, 0.291, 0.0485]) is
close to the long-run system state and so it is likely that we will (effectively)
reach the long-run prediction within a few weeks.

Points to make include:

- Markov theory simple to understand and apply
- Markov theory gives us an insight into changes in the system over time
- sensitivity calculations (i.e. "what-if" questions) are easily carried out
- entrants to, and exits from, the market can be modelled
- P may be dependent upon the current state of the system (i.e. the current market share)
- how do we cope with the effect of promotional (advertising) campaigns
- Markov theory is only a simplified model of a complex decision-making process.

British Gas currently has three schemes for quarterly payment of gas bills, namely:

(1) cheque/cash payment

(2) credit card debit

(3) bank account direct debit

Their research department has estimated the following matrix of probabilities for switching between schemes:

Will switch next quarter to scheme 1 2 3 Currently pays by scheme 1 | 0.85 0.10 0.05 | 2 | 0.04 0.90 0.06 | 3 | 0.02 0.23 0.75 |

If 70% currently pay by scheme (1), 20% by scheme (2) and 10% by scheme (3) what will be the corresponding percentages after:

- two quarters; and
- in the long-run.

Here we have a Markov process with three states where

s_{1} = [0.7, 0.2, 0.1]

and P = | 0.85 0.10 0.05 | | 0.04 0.90 0.06 | | 0.02 0.23 0.75 |

The state of the system after one quarter s_{2} = s_{1}P

= [0.605, 0.273, 0.122]

Note that, as required, the elements of s_{2} sum to one. The
state of the system after 2 quarters s_{3} = s_{2}P

= [0.52761, 0.33426, 0.13813]

Again note that the elements of s_{3} add to one.

Hence after two quarters the percentage paying by scheme (1) will be 52.761%, the percentage paying by scheme (2) will be 33.426% and the percentage paying by scheme (3) will be 13.813%.

To calculate the long-run situation let [x_{1},x_{2},x_{3}]
represent the long-run system state - then we have that

[x_{1},x_{2},x_{3}] = [x_{1},x_{2},x_{3}](P)

where x_{1} + x_{2} + x_{3} = 1.

This gives us the four equations

x_{1} = 0.85x_{1} + 0.04x_{2} + 0.02x_{3}

x_{2} = 0.10x_{1} + 0.90x_{2} + 0.23x_{3}

x_{3} = 0.05x_{1} + 0.06x_{2} + 0.75x_{3}

x_{1} + x_{2} + x_{3} = 1

Solving these four simultaneous equations gives

x_{1} = 0.1908, x_{2} = 0.6218 and x_{3} = 0.1874

Note that after solution we can substitute these values back into our four equations above to check that these values are consistent with those equations.

Hence in the long-run the percentage paying by scheme (1) will be 19.08%, the percentage paying by scheme (2) will be 62.18% and the percentage paying by scheme (3) will be 18.74%.