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:

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,1,0]^T, and p₁ = Mp₀, p₂ = Mp₁ = M²p₀, p₃ = Mp₂ = M³p₀, etc. If we have the initial location, p₀, of a car, then the limit as k goes to infinity of M^kp₀ gives us the probabilities for its eventual location.

1. Enter the expressions for p₀ 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?
2. Repeat step 1 for a car starting at location 1.
3. Repeat step 1 for a car starting at location 3. What do you deduce from these calculations?
4. Recall that the steady-state 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 steady-state vector is the one whose entries sum to 1. Find the steady-state vector and compare this answer to the ones you computed in the preceding steps.

5. If the Markov chain p₁, p₂, p₃, ... converges to p, then p should be the limit as k goes to infinity of M^kp₀. Compute M², M⁵, M⁸, etc., until you can guess the limiting matrix M^inf. Then compute M^infp₀ for each of the three possible choices of p₀. Compare your answers to the steady-state vector you computed above. What characteristic of the limiting matrix causes your answers to be what they are?
6. 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