**Application to Markov Chains**

** **

** Introduction **Suppose there
is a physical or mathematical system that has

** Example **Suppose a car rental agency has three
locations in Ottawa: Downtown location (labeled A), East end location (labeled
B) and a West end location (labeled C). The agency has a group of delivery
drivers to serve all three locations.
The agency's statistician has determined the following:

**1. **Of
the calls to the Downtown location, 30%
are delivered in Downtown area, 30% are delivered in the East end, and 40% are delivered in the
West end

**2. **Of
the calls to the East end location, 40%
are delivered in Downtown area, 40% are delivered in the East end, and 20% are delivered in the
West end

**3. **Of
the calls to the West end location, 50%
are delivered in Downtown area, 30% are delivered in the East end, and 20% are delivered in the
West end.

After making a delivery, a driver
goes to the nearest location to make the next delivery. This way, the location
of a specific driver is determined only by his or her previous location.

We model this problem with the
following matrix:

_{}

T is called the **transition matrix**
of the above system. In our example, a **state** is the location of a
particular driver in the system at a particular time. The entry s_{ji }in
the above matrix represents the probability of transition from the state
corresponding to i** **to the state
corresponding to j. (e.g. the state corresponding to 2 is B)

To make matters simple, let's assume that it takes each delivery person the
same amount of time (say 15 minutes) to make a delivery, and then to get to
their next location. According to the statistician's data, after 15 minutes, of
the drivers that began in A, 30% will again be in A, 30% will be in B, and 40%
will be in C. Since all drivers are in one of those three locations after their
delivery, each column sums to 1. Because we are dealing with probabilities,
each entry must be between 0 and 1, inclusive. The most important fact that
lets us model this situation as a Markov chain is that the next location for
delivery depends only on the current location, not previous history. It is also
true that our matrix of probabilities does not change during the time we are
observing.

Now, let’s start with a simple question. I f you begin at location C, what
is the probability (say, P) that you will be in area B after 2 deliveries?
Think about how you can get to B in two steps. We can go from C to C, then from
C to B, we can go from C to B, then from B to B, or we can go from C to A, then
from A to B. To figure out P, let
P(XY) denote the probability of going from X to Y in one delivery (where
X,Y can be A,B or C). Do you remember how probabilities work? If two (or more)
independent events must both (all) happen, to obtain the probability of them
both (all) happening, we multiply their probabilities together. To obtain the
probability of either (any) happening, we add the probabilities of those events
together.

This gives us P =
P(CA)P(AB) + P(CB)P(BB) + P(CC)P(CB) for the probability that a delivery person
goes from C to B in 2 deliveries. Substituting into our formula using the
statistician's data above gives P = (.5)(.3) + (.3)(.4) + (.2)(.3) = .33.This
tells us that if we begin at location C, we have a 33% chance of being in
location B after 2 deliveries.

Let's try this for another pair. If we
begin at location B, what is the probability of being at location B after 2
deliveries? Try this yourself before you read further! The probability of going
from location B to location B in two deliveries is P(BA)P(AB) + P(BB)P(BB) +
P(BC)P(CB) = (.4)(.3)+(.4)(.4) + (.2)(.3) = .34. Now it wasn't so bad
calculating where you would be after 2 deliveries, but what if you need to know
where you will be after 5, or 15 deliveries? That could take a LONG time. There
must be an easier way, right? Look carefully at where these numbers come
from. As you might suspect, they are
the result of matrix multiplication.. Going from C to B in 2 deliveries is the
same as taking the inner product of row 2 and column 3. Going from B to B in 2
deliveries is the same as taking the inner product of row 2 and column 2. If you multiply T by T, the (2, 3) and (2,2) entries are respectively, the same
answers that you got for these two questions above. The rest of T^{2}
answers the same type of question for any other pair of locations X and Y.

_{}

You will notice that the elements on each column still add to 1 and each
element is between 0 and 1, inclusive. Since we are modeling our problem with a
Markov chain, this is essential. This matrix indicates the probabilities of
going from location *i* to location *j* in exactly 2 deliveries.

Now that we have this matrix, it should be easier to find where we will be
after 3 deliveries. We will let p(AB) represent the probability of going from A
to B in 2 deliveries. Let's find the probability of going from C to B in 3
deliveries: it is p(CA)P(AB) +
p(CB)P(BB) + p(CC)P(CB) = (.37)(.3) + (.33)(.4) + (.3)(.3) = .333. You will see
that this probability is the inner product of row 2 of T^{2 }and column
3 of T. Therefore, if we multiply T^{2} by T, we will get the
probability matrix for 3 deliveries.

_{}

By now, you probably know how we find the matrix of probabilities for 4, 5 or more deliveries. Notice that the elements on each column still add to 1. Therefore, it is important that you do not round your answers. Keep as many decimal places as possible to retain accuracy.

_{}, _{}, _{},

_{}

What do you notice about these matrices as we take into account more and
more deliveries? The numbers in each row seems to be converging to a particular
number. **Think about what this tells us about our long-term probabilities**.
This tells us that after a large number of deliveries, it no longer matters
which location we were in when we started. At the end of the week, we have
(approximately) a 38.9% Chance of being at location A, a 33.3% chance of being
at location B, and a 27.8% chance of being in location C. This convergence will
happen with most of the transition matrices that we consider.

**Remark** If all the entries of the transition matrix
are between 0 and 1 EXCLUSIVELY, then convergence is guaranteed to take place.
Convergence may take place when 0 and 1 are in the transition matrix, but
convergence is no longer guaranteed.

For an example, look
at the matrix

_{}

Think about the
situation that this matrix represents in order to understand why *A ^{k}*
oscillates as

Sometimes, you will be
given a vector of initial distributions to describe how many or what proportion
of the objects are in each state in the beginning. Using this vector, you can
find out how many (or what proportion) of the objects are in each state at any
later time. If the initial distribution vector consist of numbers between 0 and
1, it tells you what proportion of the total number of objects are in each
state in the beginning, and the elements in the column sum to one.
Alternatively, the vector of initial distributions could contain the actual
number of objects or people in each state in the beginning. In this case, all the elements will be
nonnegative and the elements in each row will add to the total number of
objects or people in the entire system. In our example above, the vector of
initial distributions tells us what proportion of the drivers originally begins
in each area. For example, if we start out with a uniform distribution, we will
have 1/3 of our drivers in each area. Thus, the vector

_{}

is the vector of
initial distribution. After one delivery, the distribution will be
(approximately) 40% of our drivers in area A, 33.4% in area B, and 26.6% in
area C. We found this by multiplying our initial distribution matrix by our
transition matrix, as follows:

_{}

After many deliveries, we saw that some convergence occurs, so that the area from which we start doesn't matter. This will mean that we will obtain the same right-hand side no matter with which initial distribution we start. For example,

_{}

Notice that each right-hand side is the same as one of the columns of our transition matrix after many deliveries. This is exactly what we expected because we said that about 38.9% of the people will be in area A after many deliveries regardless of what percentage of the people were in area A in the initial distribution. Check this with several initial distributions to convince yourself of the truth of this statement.

If the initial distribution indicates the actual number of people in the system, the following can represent our system after one delivery:

_{}

Did you notice that we now have a fractional number of people in areas A and C after one delivery? We know that this cannot happen, but this gives us a good idea of approximately how many delivery people are in each area. After many deliveries, the right-hand side of this equality will also be very close to a particular vector. For example,

_{}

The particular vector that the product converges to is the total number of
people in the system (54 in this case) times any columnn of the matrix that *A ^{k}*
converges to as

_{}

Try some examples to convince yourself that the vector indicating the number
of people in each area after many deliveries will not change if people are
moved from one state to another in the initial distribution. Also notice that
the number of people in the entire system never changes. People move from place
to place, but the system never loses or gains people. This can also be
illustrated easily using block multiplication: Since, for large N, T^{N}
= [w
w w] has its 3 columns the same,
then if v = (coulmn vector) (p_{1},
p_{2}, p_{3}) is the initial distribution vector ,T^{N}
v = [w w w] (p_{1}, p_{2}, p_{3}) (transpose)= p_{1}w+
p_{2}w+ p_{3}w =( p_{1}+ p_{2}+ p_{3})w
=(total number of people initially) w.

I hope the above
example gave you a good idea about the process of Markov chains. Now here is
the general setting:

** Definitions** For a Markov chain with

The following Theorem
gives the relation between two consecutive state vectors:

*If X _{n+1} and X_{n} are two
consecutive state vectors of a Markov chain with transition matrix T, then X_{n+1}=T
X_{n}*

_{ }

_{ }

For a Markov chain, we are usually
interested in the long-term behavior of a general state vector *X _{n}*.
In other words, we would like to
find the limit of

_{}

then

_{}

Clearly *X _{n}*
oscillates between the vectors (0, 1) and (1, 0) and therefore does not
approach a fixed vector.

A question is: what makes *X _{n}* approach a limiting vector as

** Definition **A transition matrix

For example, the matrix

_{}

is regular since

_{}.

A Markov chain process
is called **regular** if its transition matrix is regular.

We state now the main
theorem in Markov chain theory:

*1.
**If T is a
regular transition matrix, then as n approaches infinity, T ^{n}→S
where S is a matrix of the form [v, v,…,v] with v being a constant vector.*

*2.
**If T is a
regular transition matrix of a Markov chain process, and if X is any state
vector, then as n approaches infinity, T ^{n}X→p, where p is a
fixed probability vector (the sum of its entries is 1), all of whose entries
are positive.*

* *

Consider a Markov
chain with a regular transition matrix *T, *and let *S* denote the
limit of *T ^{n} *as

* *

Is there a way to compute the steady-state vector of a regular Markov chain
without using the limit? Well, if we can solve *Tp*=*p*, for *p*,
then yes! You might have seen this sort of thing before (and certainly will in
your first linear algebra course) Recall the definition of an eigenvector and
an eigenvalue of a square matrix:

Given a square
matrix *A, *we say that the number λ is an **eigenvalue **of *A*
if there exists a nonzero vector *X* satisfying: *AX=λX*. In this
case, we say that *X* is an **eigenvector **of *A* corresponding
to the eigenvalue λ.** **

It is now clear that a
steady-state vector of a regular Markov chain is an eigenvector for the
transition matrix corresponding to the eigenvalue 1.

Recall that the
eigenvalues of a matrix *A* are the solutions to the equation det(*A-*
λI)=0
where I is the identity matrix of the same size as *A. *If λ is an
eigenvalue of *A, *then an eigenvector corresponding to λ is a non-zero
solution to the homogeneous system (*A-* λI)*X*=0. Consequently, there are
infinitely many eigenvectors corresponding to a fixed eigenvalue.

** Example** If you have
lived in Ottawa for a while, you must have realized that the weather is a main
concern of the population. An unofficial study of the weather in the city in
early spring yields the following observations:

1.
It is almost
impossible to have two nice days in a row

2.
If we have a nice
day, we just as likely to have snow or rain the next day

3.
If we have snow
or rain, then we have an even chance to have the same the next day

4.
If there is a
change from snow or rain, only half of the time is this a change to a nice day.

a.
Write the
transition matrix to model this system.

b.
If it is nice
today, what is the probability of being nice after one week?

c.
Find the long
time behaviour of the weather.

** Solution** 1) since the weather tomorrow depends only on
today, this is a Markov chain process. The transition matrix of this system is

_{}

where the letters *N,
R, S* represent Nice, Rain, Snow respectively.

2) If it is nice
today, then the initial state-vector is

_{}

After seven days (one week), the state-vector would be

_{}

So, there is about 20%
chance of being nice in one week.

3) Notice first that we are dealing with a regular
Markov chain since the transition matrix is regular, so we are sure that the
steady-state vector exists. To find it we solve the homogeneous system (*T-I)X=0*
which has the following coefficient matrix:

* *

_{}

Reducing to reduced echelon form gives

_{}.

The general solution of this system is

_{}

So what solution do we choose? Remember that a steady-state vector is in particular a probability vector; that is the sum of its components is 1: 0.5t+t+t=1 gives t=0.4. Thus, the steady-state vector is

_{}

In the long term, there is 20% chance of getting a nice day, 40% chance of having a rainy day and 40% chance of having a snowy day.