Markov Chains
Part 2: Rental Cars
Suppose a car rental agency
has three locations, numbered 1, 2, and 3. A customer may rent a car from any of
the three locations and return the car to any of the three locations. The
agency's statistician has determined that customers return the cars to
the various locations according to the following probabilities:

Rented From 


1: 
2: 
3: 
Returned 
1: 
0.8 
0.3 
0.2 
to 
2: 
0.1 
0.2 
0.6 

3: 
0.1 
0.5 
0.2 
Let M denote the
matrix defined by the preceding table, and let p_{k} = [x_{1k},x_{2k},x_{3k}]^{T}
be a vector that gives the probabilities that a car will be at each of
the locations after k rentals; i.e., x_{1k} is the probability
that it will be at location 1 after k rentals. Thus, for every vector p_{k}
, x_{1k} + x_{2k} + x_{3k} = 1 (assuming that no
cars are stolen). If a car is initially at location 2, then p_{0}
= [0,1,0]^{T}, and p_{1} = Mp_{0},
p_{2} = Mp_{1} = M^{2}p_{0},
p_{3} = Mp_{2} = M^{3}p_{0},
etc. If we have the initial location, p_{0}, of a car, then
the limit as k goes to infinity of M^{k}p_{0}
gives us the probabilities for its eventual location.
 Enter the expressions for
p_{0} and M in your worksheet, and calculate p_{k}
for k = 3, 5, 7, ... . Use the results to estimate the limiting probabilities.
After a large number of rentals, what is the probability that the car will
be at any given location?
 Repeat step 1 for a car
starting at location 1.
 Repeat step 1 for a car
starting at location 3. What do you deduce from these calculations?
 Recall that the steadystate
vector p has the property that Mp = p. As you did
in Part 1, solve the system Mp = p [or the equivalent system
(M  I)p = 0] to find p.
 Note that the sum of the entries in each column of M  I
is 0. What does this say about the invertibility or singularity
of the matrix M  I?
 Find the reduced row echelon form of M  I. Is your result
consistent with your answer to the previous question? If not,
perform the row reduction one step at a time. Do you get the
same result? Explain.
Among the solutions
of this system, the steadystate vector is the one whose entries sum to
1. Find the steadystate vector and compare this answer to the ones you computed in the preceding steps.
 If the Markov chain p_{1}, p_{2}, p_{3}, ... converges to p, then
p should be the limit as k goes to infinity of M^{k}p_{0}.
Compute M^{2}, M^{5}, M^{8},
etc., until you can guess the limiting matrix M^{inf}. Then
compute M^{inf}p_{0} for each of the
three possible choices of p_{0}. Compare your answers to
the steadystate vector you computed above. What characteristic of the
limiting matrix causes your answers to be what they are?
 What is the implication
of the result of the preceding step with respect to the starting location
of a rental car and its eventual location? If the agency owns 1000 cars,
how many parking spaces should it have at each of locations 1, 2, and 3?
modules at math.duke.edu