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.
-
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?
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{?}\)
(b)
(c)
(d)
How many books does each library contain after \(n\) months?
(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{?}\)
Definition 4.3.
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{.}\)
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*}
Definition 4.5. Regular Stochastic Matrix.
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)
(b)
Determine what happens to the distribution of cars after a long time.
