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.

Consider the following problem: company K, the manufacturer of a breakfast cereal, currently has some 25% of the market. Data from the previous year indicates that 88% of K's customers remained loyal that year, but 12% switched to the competition. In addition, 85% of the competition's customers remained loyal to the competition but 15% of the competition's customers switched to K. Assuming these trends continue determine K's share of the market:

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

This problem is an example of a *brand switching* problem that
often arises in the sale of consumer goods.

In order to solve this problem we make use of *Markov chains* or
*Markov processes* (which are a special type of *stochastic process*).
The procedure is given below.

Observe that, each year, a customer can either be buying K's cereal
or the competition's. Hence we can construct a diagram as shown below where
the two circles represent the two *states* a customer can be in and
the arcs represent the probability that a customer makes a *transition*
each year between states. Note the circular arcs indicating a "transition"
from one state to the same state. This diagram is known as the *state-transition
diagram* (and note that all the arcs in that diagram are directed arcs).

Given that diagram we can construct the *transition matrix* (usually
denoted by the symbol P) which tells us the probability of making a transition
from one state to another state. Letting:

- state 1 = customer buying K's cereal and
- state 2 = customer buying competition's cereal

we have the transition matrix P for this problem given by

To state 1 2 From state 1 |0.88 0.12 | 2 |0.15 0.85 |

Note here that the sum of the elements in each row of the transition matrix is one. Note also that the transition matrix is such that the rows are "From" and the columns are "To" in terms of the state transitions.

Now we know that currently K has some 25% of the market. Hence we have the row matrix representing the initial state of the system given by:

State 1 2 [0.25, 0.75]

We usually denote this row matrix by s_{1} indicating the state
of the system in the first period (years in this particular example). Now
Markov theory tells us that, in period (year) t, the state of the system
is given by the row matrix s_{t} where:

s_{t} = s_{t-1}(P) =s_{t-2}(P)(P) = ... = s_{1}(P)^{t-1}

We have to be careful here as we are doing matrix multiplication and
the order of calculation is important (i.e. s_{t-1}(P) is not equal
to (P)s_{t-1} in general). To find s_{t} we could attempt
to raise P to the power t-1 directly but, in practice, it is far easier
to calculate the state of the system in each successive year 1,2,3,...,t.

We already know the state of the system in year 1 (s_{1}) so
the state of the system in year two (s_{2}) is given by:

s_{2} = s_{1}P

= [0.25,0.75] |0.88 0.12 | |0.15 0.85 | = [(0.25)(0.88) + (0.75)(0.15), (0.25)(0.12) + (0.75)(0.85)] = [0.3325, 0.6675]

Note that this result makes intuitive sense, e.g. of the 25% currently buying K's cereal 88% continue to do so, whilst of the 75% buying the competitor's cereal 15% change to buy K's cereal - giving a (fractional) total of (0.25)(0.88) + (0.75)(0.15) = 0.3325 buying K's cereal.

Hence in year two 33.25% of the people are in state 1 - that is buying
K's cereal. Note here that, as a numerical check, the elements of s_{t}
should always sum to one.

In year three the state of the system is given by:

s_{3} = s_{2}P

= [0.3325, 0.6675] |0.88 0.12 | |0.15 0.85 | = [0.392725, 0.607275]

Hence in year three 39.2725% of the people are buying K's cereal.

Now it is plainly nonsense to suggest that we can predict to four decimal
places K's market share in two years time - but the calculation **has
enabled us to get some insight into the change in K's share of the market
over time that we otherwise might not have had**.

The above problem was solved using the package, the input being shown below.

The output is shown below, first after a single time period (year in this case), then for after two time periods.

Using the package we can also graph the change in K's market share over time. This can be seen below. Note how (for this particular example) the market share rises steeply in the first few periods but then tails off and appears to reach a limit.

One advantage of using the package is that we can easily investigate changes. For example suppose, through a marketing/advertising campaign, that company K could increase the loyalty of their customers, specifically increase the transition probability from K to K by 0.01, i.e. to 0.89.

Now if K were to do this suppose we believe that the competition will respond with their own campaign and this will enable them to maintain loyalty amongst their own customers, with the Competition to Competition transition probability increasing from 0.85 to 0.86.

Will K have a larger or smaller (or the same) market share after two years in this case and what will be its market share?

Using the package we have:

and

indicating that this situation will not improve K's market share in two years - as can be seen above this is now 38.5625% whereas before it was higher - 39.2725%. Knowing this without the effort and expense of a marketing campaign is obviously extremely valuable.

Recall that the question asked for K's share of the market in the long-run.
This implies that we need to calculate s_{t} as t becomes very
large (approaches infinity).

The idea of the long-run is based on the ** assumption** that,
eventually, the system reaches "equilibrium" (often referred
to as the "steady-state") in the sense that s

There are two basic approaches to calculating the steady-state:

- Computational - find the steady-state by calculating s
_{t}for t=1,2,3,... and stop when s_{t-1}and s_{t}are approximately the same. This is obviously very easy for a computer and is the approach used by the package. - Algebraic - to avoid the lengthy arithmetic calculations needed to
calculate s
_{t}for t=1,2,3,... we have an algebraic short-cut that can be used. Recall that in the steady-state s_{t}= s_{t-1}(= [x_{1},x_{2}] say for the example considered above). Then as s_{t}= s_{t-1}P we have that

[x_{1},x_{2}] = [x_{1},x_{2}] |0.88 0.12 | |0.15 0.85 |

(and note also that x_{1} + x_{2} = 1). Hence we have
three equations which we can solve.

Note here that we have used the word assumption above. This is because not all systems reach an equilibrium, e.g. the system with transition matrix

|0 1 | |1 0 |

will never reach a steady-state.

Adopting the algebraic approach above for the K's cereal example we have the three equations:

x_{1} = 0.88x_{1} + 0.15x_{2}

x_{2} = 0.12x_{1} + 0.85x_{2}

x_{1} + x_{2} = 1

and rearranging the first two equations we get

0.12x_{1} - 0.15x_{2} = 0

0.12x_{1} - 0.15x_{2} = 0

x_{1} + x_{2} = 1

Note here that the equation x_{1} + x_{2} = 1 is essential.
Without it we could not obtain a unique solution for x_{1} and
x_{2}. Solving we get x_{1} = 0.5556 and x_{2}
= 0.4444

Hence, in the long-run, K's market share will be 55.56%.

A useful numerical check (particularly for larger problems) is to substitute the final calculated values back into the original equations to check that they are consistent with those equations.

The above problem was solved using the package, the output being shown below.

In the output shown above note:

- the steady state probabilities. These figures are as calculated before.
- recurrence time for each state - these are the expected number of periods that will elapse before a person in one state is again in that state (e.g. we would expect there to be 1.80 periods (on average) between a person buying K's cereal and their next purchase of K's cereal).

Comments

The above analysis is plainly simplistic. We cannot pretend to have accurately predicted market shares into the future. Changing circumstances will change the transition matrix over time. However what the above analysis has given us is some insight that we did not have before. For example:

- we now have some numeric insight into how fast we might expect K's market share to grow over time
- we now have some numeric insight into what might be the maximum market share we can expect K to achieve
- we now have some numeric insight into whether an advertising campaign aimed at changing transition probabilities will increase K's market share or not

Such insights, based as they are on a quantitative analysis, can help us in decision making. For example, if we wanted K to have a market share of 35% in two years time we need do nothing (on current trends). If we wanted K to have a market share of 50% in two years time then, on current trends, we do need to do something. How much we need to change any given transition probability to achieve our target market share of 50% in two years time is easily calculated.

Moreover reflect on what all the TV/other media advertisements for consumer
items are meant to do. For many items (since the total market demand is
effectively stable, what is often called by economists a **saturated market,
"all the people who are going to buy are already buying"**)
what such advertisements are meant to achieve is to **alter consumer switching
(transition) probabilities**.You should be clear that transition probabilities
need not be regarded as fixed numbers - rather they are often things that
we can influence/change.

Data

Nowadays many supermarkets in the UK have their own **"loyalty
cards"** which are swiped through the checkout at the same time
as a customer makes their purchases. These provide a mass of detailed information
from which supermarkets (or others) can deduce brand switching transition
matrices:

- Do you think those matrices might be of interest (value) to other companies or not?
- For example, suppose you were a manufacturer/marketer of breakfast cereal how much would you pay a leading supermarket for continuing and detailed electronic information on cereal brand switching?
- How much extra would you pay for exclusive rights with that supermarket (so your competitors cannot have access to that data)?
- How useful would a continuing flow of such information be to you to judge the effect of promotional/marketing campaigns?

Now consider how many different products/types of products a supermarket sells. The data they are gathering on their databases through the use of loyalty cards can be extremely valuable to them.

Note too that the availability of such data enables more detailed models
to be constructed. For example in the cereal problem we dealt with above
the competition was represented by just one state. With more detailed data
that state could be disaggregated into a number of different states - maybe
one for each competitor brand of cereal. If we have n states then we need
n^{2} transition probabilities. Estimating these probabilities
is easy if we have access to a supermarket database which tells us from
individual consumer data whether people switched or not, and if so to what.

Also we could have different models for different segments of the market - maybe brand switching is different in rural areas from brand switching in urban areas for example. Families with young children would obviously constitute another important brand switching segment of the cereal market.

Note here that if we wish to investigate brand switching in a numeric
way then **transition probabilities are key**. Unless we can get such
numbers nothing numeric is possible.

Consider now how, in the absence of readily available information on brand switching as gathered by a supermarket (e.g. because we cannot afford the price the supermarkets are asking for such information), we might get information as to transition probabilities. One way, indeed this is how this was done before loyalty cards, is to survey customers individually. Someone physically stands outside the supermarket and asks shoppers about their current purchases and their previous purchases. Whilst this can be done it is plainly expensive - particularly if we need to achieve a reasonable geographic coverage that is regularly updated as time passes.

Both of the above ways of estimating transition matrices - buying electronic
information and manual surveys - cost money. There is however one way that
is effectively **COST FREE **although, as will become apparent
below, it does involve some intellectual effort. This involves estimating
the transition probabilities (i.e. the entire transition matrix) from the
observed market shares. We illustrate how this can be done below.

Estimating the transition matrix - two periods

Consider a simple two state example involving two companies. Suppose that the market shares in the first period are [0.3,0.7] and in the next period they are [0.2,0.8] - what then would you estimate the transition matrix to be?

Letting the transition matrix be:

| p_{1}1-p_{1}| |1-p_{2}p_{2}|

we have that

[0.2,0.8] = [0.3,0.7]| p_{1}1-p_{1}| |1-p_{2}p_{2}|

so that we have

0.2 = 0.3p_{1}+ 0.7(1-p_{2}) 0.8 = 0.3(1-p_{1}) + 0.7p_{2}

which give

-0.5 = 0.3p_{1}- 0.7p_{2 }0.5 = -0.3p_{1}+ 0.7p_{2}

and as these two equations are identical (one is the other with the
sign changed) we have no unique way of determining values for p_{1}
and p_{2}.

To overcome this one approach that will yield valid numeric values for
p_{1} and p_{2} is to say that whatever the transition
matrix is, we would like the diagonal entries (p_{1} and p_{2})
to be as large as possible. This is equivalent to saying that we believe
that the combined probabilities of making a transition away from the original
states should be as small as possible. This is equivalent to saying that
consumers/customers are loyal and tend to stay with what they know ("brand
inertia"). Hence we can formulate the problem of determining p_{1}
and p_{2} as

maximise p_{1} + p_{2}

subject to

0.5 = -0.3p_{1} + 0.7p_{2
}0 <= p_{1} <= 1

0 <= p_{2} <= 1

where we have added restrictions on p_{1} and p_{2},
namely that they must lie between zero and one. Now this problem is just
a linear
programming (LP) problem that can be easily solved using the package,
as below.

so that the solution is p_{1}=(2/3) and p_{2}=1. It
is easily checked that these values satisfy the equation 0.5 = -0.3p_{1}
+ 0.7p_{2}. Hence our transition matrix is:

| 2/3 1/3 | | 0 1 |

Note here that, as our original equation 0.5 = -0.3p_{1} + 0.7p_{2}
implied, there are **many** possible transition matrices that exactly
correspond to the observed market shares. What we have done here in producing
the transition matrix shown above is to choose **one** of these transition
matrices as derived from the solution to an optimisation problem.

To extend our example suppose that the observed market shares are

first [0.3,0.7] then [0.2,0.8] then [0.15,0.85] then [0.13,0.87]

where the first two periods here are as in the example dealt with above. What would you estimate the transition matrix to be now?

Obviously we could take each successive pair of market shares and use exactly the same approach as above, deriving transition matrices that apply between each and every time period.

We have done this above for the first two periods and obtained

| 2/3 1/3 | | 0 1 |

If we do this for periods 2 and 3 we have

[0.15,0.85] = [0.2,0.8]| p_{1}1-p_{1}| |1-p_{2}p_{2}|

for which the corresponding linear equation is

0.15 = 0.2p_{1}+ 0.8(1-p_{2})

i.e. -0.65 = 0.2p_{1}- 0.8p_{2 }

which following the same approach as before leads to the linear program

maximise p_{1} + p_{2}

subject to

-0.65 = 0.2p_{1} - 0.8p_{2
}0 <= p_{1} <= 1

0 <= p_{2} <= 1

for which the solution is p_{1}=(3/4) and p_{2}=1. It
is easily checked that these values satisfy the equation -0.65 = 0.2p_{1}
- 0.8p_{2}. Hence our transition matrix is:

| 3/4 1/4 | | 0 1 |

So we now have a different transition matrix to the one we derived when we considered just the first two periods! So this approach, whilst possible, leads to conceptual difficulties - did the transition matrix really change between periods or do we need a better way of estimating it?

**Suppose we want a SINGLE transition matrix that, when applied over
all time periods, best captures the observed market shares - how can we
find it?**

Well, as before, let us assume that this single transition matrix is

| p_{1}1-p_{1}| |1-p_{2}p_{2}|

and recall that we have

first [0.3,0.7] then [0.2,0.8] then [0.15,0.85] then [0.13,0.87]

then, from the initial market shares of [0.3,0.7] we have that the market shares in the next period are

[0.3,0.7]| p_{1}1-p_{1}| |1-p_{2}p_{2}|

= [0.3p_{1} + 0.7(1-p_{2}), 0.3(1-p_{1}) + 0.7p_{2}]
- as against the observed market shares in this period of [0.2,0.8]

For the next period, starting from [0.2,0.8] we have

[0.2,0.8]| p_{1}1-p_{1}| |1-p_{2}p_{2}|

= [0.2p_{1} + 0.8(1-p_{2}), 0.2(1-p_{1}) + 0.8p_{2}]
- as against the observed market shares in this period of [0.15,0.85]

For the next period, starting from [0.15,0.85] we have

[0.15,0.85]| p_{1}1-p_{1}| |1-p_{2}p_{2}|

= [0.15p_{1} + 0.85(1-p_{2}), 0.15(1-p_{1})
+ 0.85p_{2}] - as against the observed market shares in this period
of [0.13,0.87]

Hence we can construct a table as below:

Time State Calculated Observed 1 1 0.3p_{1}+ 0.7(1-p_{2}) 0.2 2 0.3(1-p_{1}) + 0.7p_{2}0.8 2 1 0.2p_{1}+ 0.8(1-p_{2}) 0.15 2 0.2(1-p_{1}) + 0.8p_{2}0.85 3 1 0.15p_{1}+ 0.85(1-p_{2}) 0.13 2 0.15(1-p_{1}) + 0.85p_{2}0.87

Plainly it would be ideal if we could choose values for p_{1}
and p_{2} such that each of the calculated expressions **EXACTLY**
matches the observed market shares i.e. choose p_{1} and p_{2}
such that

0.3p_{1}+ 0.7(1-p_{2}) = 0.2 0.3(1-p_{1}) + 0.7p_{2}= 0.8 0.2p_{1}+ 0.8(1-p_{2}) = 0.15 0.2(1-p_{1}) + 0.8p_{2}= 0.85 0.15p_{1}+ 0.85(1-p_{2}) = 0.13 0.15(1-p_{1}) + 0.85p_{2}= 0.87

The above are all linear equations so we can approach solving them via an LP as before - simply

maximise p_{1}+ p_{2}

subject to

0.3p_{1}+ 0.7(1-p_{2}) = 0.2 0.3(1-p_{1}) + 0.7p_{2}= 0.8 0.2p_{1}+ 0.8(1-p_{2}) = 0.15 0.2(1-p_{1}) + 0.8p_{2}= 0.85 0.15p_{1}+ 0.85(1-p_{2}) = 0.13 0.15(1-p_{1}) + 0.85p_{2}= 0.87 0 <= p_{1}<= 1 0 <= p_{2}<= 1

If we solve this LP numerically we will find that the problem is infeasible
- i.e. there are no values for p_{1} and p_{2} that satisfy
the above equations. Hence we seem to have reached an impasse.

One way forward so as to choose values for p_{1} and p_{2}
is again to solve an optimisation problem, but where this time we minimise
the squared difference between the calculated state in each time period
and the observed state, i.e. minimise the sum of squared errors (a common
approach in parameter estimation). Hence we need to solve:

minimise

[0.3p_{1}+ 0.7(1-p_{2}) - 0.2]^{2}+ [0.3(1-p_{1}) + 0.7p_{2}- 0.8]^{2}+ [0.2p_{1}+ 0.8(1-p_{2}) - 0.15]^{2}+ [0.2(1-p_{1}) + 0.8p_{2}- 0.85]^{2}+ [0.15p_{1}+ 0.85(1-p_{2}) - 0.13]^{2}+ [0.15(1-p_{1}) + 0.85p_{2}- 0.87]^{2}

subject to:

0 <= p_{1} <= 1

0 <= p_{2} <= 1

Simplifying this objective we have

minimise [0.3p_{1} - 0.7p_{2} + 0.5]^{2} + [-0.3p_{1}
+ 0.7p_{2} - 0.5]^{2} + [0.2p_{1} - 0.8p_{2}
+ 0.65]^{2} + [-0.2p_{1} + 0.8p_{2} - 0.65]^{2}
+ [0.15p_{1} - 0.85p_{2} + 0.72]^{2} + [-0.15p_{1}
+ 0.85p_{2} - 0.72]^{2}

which is

minimise 2[0.3p_{1} - 0.7p_{2} + 0.5]^{2} +
2[0.2p_{1} - 0.8p_{2} + 0.65]^{2} + 2[0.15p_{1}
- 0.85p_{2} + 0.72]^{2}

Obviously we need to simplify this expression - in doing so note that
any constant terms can be ignored, since they cannot affect the values
for p_{1} and p_{2} chosen, merely the value of the objective
function. In a similar fashion we can drop the common multiplier of 2 associated
with each of the three terms in this objective.

After simplification we have the problem:

minimise 0.1525[p_{1}]^{2} + 1.8525[p_{2}]^{2
}- 0.995p_{1}p_{2} + 0.776p_{1} - 2.964p_{2}
subject to 0<= p_{1}<=1 and 0<= p_{2}<= 1

This is a nonlinear (quadratic) program that can be easily solved using the package as below:

Hence we can see that the solution is p_{1}=0.53, p_{2}=0.94
and hence the transition matrix is

| 0.53 0.47 | | 0.06 0.94 |

Using these values of p_{1}=0.53 and p_{2}=0.94 we have:

Time State Calculated Estimated Observed 1 1 0.3p_{1}+ 0.7(1-p_{2}) 0.201 0.2 2 0.3(1-p_{1}) + 0.7p_{2}0.799 0.8 2 1 0.2p_{1}+ 0.8(1-p_{2}) 0.142 0.15 2 0.2(1-p_{1}) + 0.8p_{2}0.846 0.85 3 1 0.15p_{1}+ 0.85(1-p_{2}) 0.131 0.13 2 0.15(1-p_{1}) + 0.85p_{2}0.870 0.87

which appears to be a very good estimation, via a single transition matrix, of the observed market shares.

**Be clear here - what we have done above is to find, in a logical
consistent systematic fashion, a transition matrix that "best fits"
the observed market shares - that transition matrix may (or may not) correspond
to the transition probabilities which we would find were we to survey customers
or gather electronic information in the real-world. Hopefully though the
transition matrix found will provide insight that we did not have before.**

Here the transition matrix we have derived above does give us further insight into the situation - we can see for example that customers of company 2 (state 2) are very loyal (94% remain with that company at each time period). Customers of company 1 (state 1) are not loyal on the other hand - only 53% remaining with company 1 at each time period - almost equivalent to customers tossing a coin to decide whether to go with company 1 or company 2. This numeric insight with respect to customer loyalty may be one that we could not have gained simply by looking at the observed market shares of

first [0.3,0.7] then [0.2,0.8] then [0.15,0.85] then [0.13,0.87]

and obviously suggests a way in which company 1 might try to gain market share (or arrest their declining market share) - namely increase customer loyalty.

Example

To consolidate your knowledge of Markov processes consider the following example. Suppose the chip industry is controlled by four companies: Crispy, Crunchy, Mushy and Scrunchy. If customers buy either Crispy or Crunchy they never buy another brand. If they buy Mushy the probabilities that they will buy Crispy, Crunchy, Mushy and Scrunchy next month are 0.45, 0.4, 0.05 and 0.1 respectively. If they buy Scrunchy the probabilities that they will buy Crispy, Crunchy, Mushy and Scrunchy next month are 0.1, 0.2, 0.3 and 0.4 respectively.

- represent this situation on a state-transition diagram
- if the buyers are initially distributed as 20%, 30%, 30% and 20% for Crispy, Crunchy, Mushy and Scrunchy respectively what will be the situation after two months?

The state-transition diagram for this problem is shown below.

Letting

- state 1 = Crispy
- state 2 = Crunchy
- state 3 = Mushy
- state 4 = Scrunchy

we have that

P = | 1 0 0 0 | | 0 1 0 0 | | 0.45 0.4 0.05 0.1 | | 0.1 0.2 0.3 0.4 |

and s_{1} = [0.2, 0.3, 0.3, 0.2]

Note here that the states corresponding to Crispy and Crunchy are *absorbing*
states (states which, once reached, cannot be left). States which are non-absorbing
are often called *transient* states.

Hence the state of the system in the second month s_{2} = s_{1}P

= [0.2, 0.3, 0.3, 0.2]| 1 0 0 0 | | 0 1 0 0 | | 0.45 0.4 0.05 0.1 | | 0.1 0.2 0.3 0.4 |

= [0.355, 0.46, 0.075, 0.11]

The state of the system in the third month s_{3} = s_{2}P

= [0.355, 0.46, 0.075, 0.11]| 1 0 0 0 | | 0 1 0 0 | | 0.45 0.4 0.05 0.1 | | 0.1 0.2 0.3 0.4 |

= [0.39975, 0.512, 0.03675, 0.0515]

The above problem was solved using the package, the input being shown below.

The output is shown below. For simplicity we have shown the state of the system after 20 time periods. It will be seen that (as we would expect) all the buyers end up in one of the two absorbing states.

**Note here that, if absorbing states are present, the mathematics
needed to calculate the long-run system state is MUCH MORE complicated
than the approach given before that worked when absorbing states were not
present. Indeed, as a reflection of this, the package refuses to calculate
a steady state for this example.**

To see why this is so try to apply the same method as we used above
when we had no absorbing states - letting the long-run system state be
[x_{1},x_{2},x_{3},x_{4}] we have

[x_{1},x_{2},x_{3},x_{4}] = [x_{1},x_{2},x_{3},x_{4}]| 1 0 0 0 | | 0 1 0 0 | | 0.45 0.4 0.05 0.1 | | 0.1 0.2 0.3 0.4 |

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

Taking the last two equations from this matrix equation we get

x_{3} = 0.05x_{3} + 0.3x_{4}

x_{4} = 0.1x_{3} + 0.4x_{4}

i.e. x_{3} = (0.3/0.95)x_{4} and x_{3} = (0.6/0.1)x_{4
}and the only values of x_{3} and x_{4} that satisfy
these two equations are x_{3}=x_{4}=0 (as we might have
suspected). Using x_{3}=x_{4}=0 the remaining equations
from above become

x_{1} = x_{1}

x_{2} = x_{2}

x_{1} + x_{2} = 1

which are somewhat difficult to solve !

Any problem for which a state-transition diagram can be drawn can be analysed using the approach given above.

The advantages and disadvantages of using Markov theory 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. 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-1}P(t-1,s_{t-1}). - Markov theory is only a simplified model of a complex decision-making process.

One interesting application of Markov processes that I know of concerns the Norwegian offshore oil/gas industry. In Norway a state body, the Norwegian Petroleum Directorate, (together with the Norwegian state oil company (STATOIL)), have a large role to play in planning the development of oil/gas offshore facilities.

The essential problem the Norwegian Petroleum Directorate has is how
to plan pipelines/field startup/production so as to maximise the contribution
to the Norwegian economy over time. Here the time scales are very long,
typically 30 to 50 *years*.

There is decision flexibility with respect to a number of items, e.g.

- rate of production (how fast it comes out of the ground)
- new field start-up's (when should they start)
- pipeline construction and capacity (where should we build them, when should we build them and how large should they be)

The objective is to maximise the benefit to the Norwegian economy over time.

Of critical importance is the oil price - yet we cannot sensibly forecast this with accuracy for the length of time, 30 to 50 years, we need to consider.

To overcome this problem they model oil price as a Markov process with three price levels (states), corresponding to optimistic, most likely and pessimistic scenarios. They also specify the probabilities of making a transition between states each time period (year). Different transition matrices can be used for different time scales (e.g. different matrices for the near, medium and far future).

Whilst this is plainly a simple approach it does have the advantage of capturing the uncertainty about the future in a model that is relatively easy to understand and apply.

Population modelling studies (where we have objects which "age") are also an interesting application of Markov processes:

- One example of this would be modelling the car market as a Markov process to forecast the "need" for new cars as old cars naturally die off. To see this try modelling this market with states corresponding to number of owners/age of car.
- Another example would be to model the clinical progress of a patient in hospital as a Markov process and see how their progress is affected by different drug regimes.

Some more markov processes examples can be found here.