Objectives: Topics
-
Markov chains
-
Steady-state vectors
-
Convergence
Print preview
Section 4.9/5.9 Markov Chains
Handout 4.9/5.9 Markov Chains
Objectives: Goals
-
Construct stochastic matrices and probability vectors.
-
Model and solve real-world problems using Markov chains (e.g., compute steady-state vectors).
-
Determine whether a stochastic matrix is regular.
Example 4.1.
A small town has two libraries, \(A\) and \(B\text{.}\)
-
After 1 month, among the books checked out from \(A\text{:}\)
-
80% return to \(A\)
-
20% return to \(B\)
-
-
After 1 month, among the books checked out from \(B\text{:}\)
-
30% return to \(A\)
-
70% return to \(B\)
-
If both libraries start with 1000 books today, how many books does each library have after 1 month?
Solution.
After 1 month, Library \(A\) will receive \(80\%\) of the books that were in Library \(A\) and \(30\%\) of the books that were in Library \(B\text{.}\) Therefore, we have that the number of books in Library \(A\) after 1 month is:
\begin{equation*}
0.8(1000) + 0.3(1000) = 800 + 300 = 1100\text{.}
\end{equation*}
After 1 month, Library \(B\) will receive \(20\%\) of the books that were in Library \(A\) and \(70\%\) of the books that were in Library \(B\text{.}\) Therefore, we have that the number of books in Library \(A\) after 1 month is:
\begin{equation*}
0.2(1000) + 0.7(1000) = 200 + 700 = 900\text{.}
\end{equation*}
Example 4.2.
(a)
Let \(\vec x_i \in \mathbb{R}^2\) be the vector which gives how many books are in libraries \(A\) and \(B\) after \(i\) months. What are \(\vec x_0\) and \(\vec x_1\text{?}\)
Solution.
We have \(\vec x_0 = \begin{bmatrix} 1000 \\ 1000 \end{bmatrix}\) and \(\vec x_1 = \begin{bmatrix} 1100 \\ 900 \end{bmatrix}\text{.}\)
(b)
Find the \(2 \times 2\) matrix \(P \) so that \(\vec x_1 = P\vec x_0\)
Solution.
Let \(P\) be the matrix with the distribution probabilities from Library \(A\) in column 1 and the distribution probabilities from Library \(B\) in column 2; that is, let
\begin{equation*}
P = \begin{bmatrix} 0.8 \amp 0.3 \\ 0.2 \amp 0.7 \end{bmatrix}\text{.}
\end{equation*}
Then we have that
\begin{equation*}
P\vec x_0 = \begin{bmatrix} 0.8 \amp 0.3 \\ 0.2 \amp 0.7 \end{bmatrix}\begin{bmatrix} 1000 \\ 1000 \end{bmatrix} = \begin{bmatrix} 0.8(1000) + 0.3(1000) \\ 0.2(1000) + 0.7(1000) \end{bmatrix} = \begin{bmatrix} 1100 \\ 900 \end{bmatrix} = \vec x_1\text{.}
\end{equation*}
(c)
How many books does each library contain after \(2\) months; that is, what is \(\vec x_2\text{?}\)
Solution.
Since multiplication by \(P\) models the change from \(\vec x_0\) to \(\vec x_1\text{,}\) it follows that multiplication by \(P\) should model the change from \(\vec x_1\) to \(\vec x_2\text{.}\) Therfore, we have that
\begin{equation*}
\vec x_2 = P\vec x_1 = \begin{bmatrix} 0.8 \amp 0.3 \\ 0.2 \amp 0.7 \end{bmatrix}\begin{bmatrix} 1100 \\ 900 \end{bmatrix} = \begin{bmatrix} 0.8(1100) + 0.3(900) \\ 0.2(1100) + 0.7(900) \end{bmatrix} = \begin{bmatrix} 1150 \\ 850 \end{bmatrix}\text{.}
\end{equation*}
Thus, after 2 months, Library \(A\) will contain 1150 books and Library \(B\) will contain 850 books.
(d)
How many books does each library contain after \(n\) months?
Solution.
Note that an alternative way to calculate \(\vec x_2\) is
\begin{equation*}
\vec x_2 = P\vec x_1 = P(P\vec x_0) = P^2\vec x_0\text{.}
\end{equation*}
If we wanted to calculate \(\vec x_3\text{,}\) we could do something similar, like
\begin{equation*}
\vec x_3 = P\vec x_2 = P(P^2\vec x_0) = P^3\vec x_0\text{.}
\end{equation*}
It follows that
\begin{equation*}
\vec x_n = P^n\vec x_0\text{.}
\end{equation*}
In most examples, \(P^n\) will be difficult to calculate for large \(n\text{.}\) Usually, we are more interested in what happens in the long term, so we are interested in finding
\begin{equation*}
\vec \ell = \lim_{n\rightarrow \infty} \vec x_n\text{.}
\end{equation*}
(e)
What if each library had started with \(100\) books instead of \(1000\) books. Would \(P\) change? What would be the new \(\vec x_0, \vec x_1, \vec x_2\text{?}\)
Solution.
Note that \(P\) models the distribution of books and has nothing to do with the specific number of books. Therefore, \(P\) would remain the same, regardless of how many books start off in Library \(A\) and Library \(B\text{.}\)
Since \(100\) is one-tenth that of \(1000\text{,}\) the only change for \(\vec x_i\) would be scaling by a factor of \(\frac{1}{10}\text{;}\) that is, the new \(\vec x_i\) would be
\begin{equation*}
\vec x_0 = \begin{bmatrix} 100 \\ 100 \end{bmatrix}, \quad \vec x_1 = \begin{bmatrix} 110 \\ 90 \end{bmatrix}, \quad \vec x_2 = \begin{bmatrix} 115 \\ 85 \end{bmatrix}\text{.}
\end{equation*}
Note that for either version of \(\vec x_i\text{,}\) the proportion of books in each library stays the same even if the actual number changes. Therefore, in general, it will be okay to simply determine how \(P\) acts on vectors which keep track of proportion of books between the libraries instead of specific numbers.
Definition 4.3 Markov Chain Definitions.
A few important definitions:
-
A probability vector is a vector \(\vec x\) whose entries are nonnegative and sum to 1.
-
A stochastic matrix is a square matrix whose columns are probability vectors.
-
A Markov chain is a sequence of probability vectors \(\vec x_k\) satisfying \(\vec x_{k+1}=P\vec x_k\) for a stochastic matrix \(P\text{.}\)
-
A steady-state vector for \(P\) is a probability vector \(\vec q\) such that \(P\vec q=\vec q\text{.}\)
Solution.
Suppose the Markov chain \(\vec x_0, \vec x_1, \vec x_2, \dots\) converges to the vector \(\vec \ell\text{.}\) Then we have that
\begin{equation*}
\vec \ell = \lim_{n\rightarrow \infty}\vec x_n = \lim_{n\rightarrow \infty}P^n\vec x_0\text{.}
\end{equation*}
Note that
\begin{equation*}
P\vec \ell = P\left(\lim_{n\rightarrow \infty}P^n\vec x_0\right) = \lim_{n\rightarrow\infty}P^{n+1}\vec x_0 = \vec \ell\text{.}
\end{equation*}
Therefore, if the Markov chain converges to some vector \(\vec \ell\text{,}\) we have \(P\vec \ell = \vec \ell\text{,}\) so \(\vec \ell\) is a steady-state vector for \(P\text{.}\)
As you might imagine, calculating the limit \(\displaystyle \lim_{n\rightarrow\infty}P^n\vec x_0\) might be quite difficult. However, if we know that the Markov chain converges and we find that there is only a single steady-state vector for \(P\text{,}\) then that unique steady-state vector must be the limit! This is how we will find the limit of a Markov chain.
One thing to note is that in the event where there is a unique steady-state vector (which will be most examples in MATH 1554), the choice of starting probabiility vector \(\vec x_0\) will NOT change the limit vector \(\vec \ell\text{.}\)
Example 4.4.
Determine a steady-state vector for the stochastic matrix:
\begin{equation*}
P = \begin{bmatrix}
0.8 \amp 0.3\\
0.2 \amp 0.7
\end{bmatrix}
\end{equation*}
Solution.
We want to find a probability vector \(\vec q\) so that \(P\vec q = \vec q\text{.}\) We can rearrage this equation by subtracting \(\vec q\) from both sides and factoring to obtain the following equation:
\begin{equation*}
P\vec q = \vec q \quad \implies \quad P\vec q - I\vec q = \vec 0 \quad \implies \quad (P - I)\vec q = \vec 0\text{,}
\end{equation*}
where we rewrote \(\vec q\) as \(I\vec q\) to make clear what is left over after factoring out \(\vec q\text{.}\) It follows that \(\vec q\) should be a probability vector that lives in \(\Nul(P - I)\text{.}\) Note that
\begin{equation*}
P - I = \begin{bmatrix} 0.8 - 1 \amp 0.3 \\ 0.2 \amp 0.7-1 \end{bmatrix} = \begin{bmatrix} -0.2 \amp 0.3 \\ 0.2 \amp -0.3 \end{bmatrix} \sim \begin{bmatrix} -2 \amp 3 \\ 0 \amp 0 \end{bmatrix}\text{.}
\end{equation*}
Since \(P - I\) has only one free variable, we know that \(\dim(\Nul(P-I)) = 1\text{.}\) Therefore, \(\Nul(P-I)\) is spanned by a single nonzero vector. By inspecting the REF of \(P-I\) given above, we see that \(\vec v = \begin{bmatrix} 3 \\ 2 \end{bmatrix}\) is a nonzero vector in \(\Nul(P-I)\text{.}\) Therefore, we have that
\begin{equation*}
\Nul(P-I) = \Span\left\{\begin{bmatrix} 3 \\ 2 \end{bmatrix}\right\}\text{.}
\end{equation*}
Note that \(\vec v\) is not a probability vector since its entries add to 5. We can modify \(\vec v\) by scaling it by a factor of \(\frac{1}{5}\) which will result in a probability vector living in \(\Nul(P - I)\text{.}\) Since this is the only way to create a probability vector in \(\Nul(P-I)\text{,}\) we see that
\begin{equation*}
\vec q = \frac{1}{5}\vec v = \begin{bmatrix} \frac{3}{5} \\ \frac{2}{5} \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix}
\end{equation*}
is the unique steady-state vector for \(P\text{.}\) We can check that \(\vec q\) is a steady-state vector. Note that
\begin{equation*}
P\vec q = \begin{bmatrix} 0.8 \amp 0.3 \\ 0.2 \amp 0.7 \end{bmatrix} \begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix} = \begin{bmatrix} 0.8(0.6) + 0.3(0.4) \\ 0.2(0.6) + (0.7)(0.4) \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix} = \vec q\text{.}
\end{equation*}
What does the steady-state vector \(\vec q\) tells us about the libraries in Example 4.1? It tells us the proportional distribution of the books between the two libraries. Since the two libraries had a total of 2000 books between them, we see that the limit vector of the Markov chain is
\begin{equation*}
\vec \ell = 2000 \vec q = 2000\begin{bmatrix} 0.6 \\ 0.4 \end{bmatrix} = \begin{bmatrix} 1200 \\ 800 \end{bmatrix}\text{.}
\end{equation*}
Thus, after many months, we should expect Library \(A\) to have 1200 books and Library \(B\) to have 800 books.
Definition 4.5 Regular Stochastic Matrix.
A stochastic matrix \(P\) is regular if some power \(P^k\) has all entries strictly positive.
Theorem 4.6 Convergence Theorem.
If \(P\) is a regular stochastic matrix, then \(P\) has a unique steady-state vector \(\vec q\text{,}\) and the sequence \(\vec x_{k+1}=P\vec x_k\) converges to \(\vec q\) as \(k\to\infty\text{.}\)
In \(\mathbb{R}^2\text{,}\) the probability vectors form the line segment between \((1,0)\) and \((0,1)\text{.}\) A stochastic matrix maps probability vectors to probability vectors, and the iterates \(P^k\vec x_0\) converge to the steady state.
Illustration of several probability vectors in \(\mathbb{R}^2\text{,}\) under repeated multiplication by a regular stochastic matrix, converging to a steady-state vector.
Example 4.7.
A rental company has three locations A, B, and C. Cars may be returned to any location. The table gives the weekly rental/return pattern: 
There are 18 cars at each location today.
(a)
Construct the stochastic matrix \(P\text{.}\) Is \(P \) regular?
Solution.
We can build the following table describing how the cars move between the three rental companies.
Table 4.8.
It follows that
| rented from | ||||
| A | B | C | ||
| A | .8 | .1 | .2 | |
| returned to | B | .2 | .6 | .3 |
| C | .0 | .3 | .5 | |
\begin{equation*}
P = \begin{bmatrix} 0.8 \amp 0.1 \amp 0.2 \\ 0.2 \amp 0.6 \amp 0.3 \\ 0 \amp 0.3 \amp 0.5 \end{bmatrix}\text{.}
\end{equation*}
Since \(P\) has at least one entry which is 0, it is not clear whether \(P\) is regular or not. By Definition 4.5, in order to show \(P\) is regular, we need to show that some power of \(P\) has no entries which are 0. Note that
\begin{equation*}
P^2 = \begin{bmatrix} 0.8 \amp 0.1 \amp 0.2 \\ 0.2 \amp 0.6 \amp 0.3 \\ 0 \amp 0.3 \amp 0.5 \end{bmatrix}\begin{bmatrix} 0.8 \amp 0.1 \amp 0.2 \\ 0.2 \amp 0.6 \amp 0.3 \\ 0 \amp 0.3 \amp 0.5 \end{bmatrix} = \begin{bmatrix} 0.66 \amp 0.2 \amp 0.29 \\ 0.28 \amp 0.47 \amp 0.37 \\ 0.06 \amp 0.33 \amp 0.34 \end{bmatrix}.
\end{equation*}
Since every entry of \(P^2\) is positive, we have that \(P\) is regular. Therefore, Theorem 4.6 guarantees that \(P\) has a unique steady-state vector.
(b)
Determine what happens to the distribution of cars after a long time.
Solution.
Again, we need to find a probability vector in \(\Nul(P - I).\) Note that
\(\begin{eqnarray*} P - I \amp = \amp \begin{bmatrix} -0.2 \amp 0.1 \amp 0.2 \\ 0.2 \amp -0.4 \amp 0.3 \\ 0 \amp 0.3 \amp -0.5 \end{bmatrix} \\ \amp \sim \amp \begin{bmatrix} -2 \amp 1 \amp 2 \\ 2 \amp -4 \amp 3 \\ 0 \amp 3 \amp -5 \end{bmatrix} \\ \amp \sim \amp \begin{bmatrix} -2 \amp 1 \amp 2 \\ 0 \amp -3 \amp 5 \\ 0 \amp 3 \amp 5 \end{bmatrix} \\ \amp \sim \amp \begin{bmatrix} -2 \amp 1 \amp 2 \\ 0 \amp -3 \amp 5 \\ 0 \amp 0 \amp 0 \end{bmatrix}\end{eqnarray*}\)
Again, we have that \(P - I\) only has a single free variable, so \(\dim(\Nul(P - I)) = 1\) which means that \(P\) will have a unique steady-state vector. We start by finding some nonzero vector in \(\Nul(P - I)\text{.}\) Since \(x_3\) is a free variable, we set \(x_3 = t \in\mathbb{R}\text{.}\) Then the second row gives
\begin{equation*}
-3x_2 + 5x_3 = 0 \quad \implies \quad -3x_2 = -5t \quad \implies \quad x_2 = \frac{5}{3}t\text{.}
\end{equation*}
The first row gives
\begin{equation*}
-2x_1 + x_2 + 2x_3 = 0 \ \implies \ x_1 = -\frac{1}{2}\left(-\frac{5}{3}t - 2t\right) \ \implies \ x_1 = \frac{11}{6}t\text{.}
\end{equation*}
Letting \(t = 6\text{,}\) we see that
\begin{equation*}
\vec v = \begin{bmatrix} \frac{11}{6}t \\ \frac{5}{3}t \\ t \end{bmatrix} = \begin{bmatrix} \frac{11}{6}(6) \\ \frac{5}{3}(6) \\ 6 \end{bmatrix} = \begin{bmatrix} 11 \\ 10 \\ 6 \end{bmatrix} \in \Nul(P - I)\text{.}
\end{equation*}
Since the entries of \(\vec v\) add to 27, we have that
\begin{equation*}
\vec q = \frac{1}{27}\vec v = \begin{bmatrix}\frac{11}{27} \\ \frac{10}{27} \\ \frac{6}{27} \end{bmatrix}
\end{equation*}
is the unique steady-state vector of \(P\text{.}\) It follows that the limit vector \(\vec \ell\) is an appropriate multiple of \(\vec q\text{.}\) Since we started with a total of \(3(18) = 54\) cars, we have that
\begin{equation*}
\vec \ell = 54\vec q = \begin{bmatrix} 22 \\ 20 \\ 12 \end{bmatrix}\text{.}
\end{equation*}
Therefore, after a long time, Location A will have 22 cars, Location B will have 20 cars, and Location C will have 12 cars.
