Markov Chains & Steady States - Linear Algebra

1. A Markov chain has a transition matrix $P$ and an initial state vector $\vec{x}_0 = \begin{pmatrix} 0.2 \\ 0.8 \end{pmatrix}$. The steady-state vector is found to be $\vec{q} = \begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}$. Which statement correctly describes the system's evolution?
   Answer: The state vector $\vec{x}_k$ will approach $\begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}$ as $k$ becomes large, regardless of the initial state. For a regular Markov chain, the sequence of state vectors $\vec{x}_k = P^k\vec{x}_0$ converges to the unique steady-state vector $\vec{q}$ for any initial probability vector $\vec{x}_0$. The fact that $\vec{x}_0$ is different from $\vec{q}$ simply means the system is not initially in equilibrium, but it will approach it over time.
2. A direct justification for why any $n \times n$ column-stochastic matrix $P$ must have an eigenvalue of $\lambda = 1$ is that:
   Answer: the columns of the matrix $P-I$ sum to the zero vector, implying they are linearly dependent. An eigenvalue $\lambda$ exists if and only if the matrix $(P-\lambda I)$ is singular, meaning its determinant is zero. For $\lambda=1$, we consider $P-I$. The columns of $P$ each sum to 1. When we subtract the identity matrix $I$, we are subtracting 1 from each diagonal element. This means that for each column of $P-I$, the sum of its elements becomes $1-1=0$. If the elements of each column vector sum to zero, the sum of the row vectors of $(P-I)$ is the zero vector, meaning the rows (and columns) are linearly dependent. A matrix with linearly dependent columns is singular, so $\det(P-I)=0$, proving that $\lambda=1$ is an eigenvalue.
3. In the long-term equilibrium, approximately how many mice will be in group A?
   Answer: 300 Let state 1 be group A and state 2 be group B. From group A, 80% stay and 20% go to B. From group B, 70% stay and 30% go to A. The transition matrix is $P = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}$. To find the steady state $\vec{q}$, we solve $(P-I)\vec{q}=\vec{0}$, which is $-0.2q_1 + 0.3q_2 = 0$, or $2q_1 = 3q_2$. An eigenvector is $\begin{pmatrix} 3 \\ 2 \end{pmatrix}$. Normalizing gives $\vec{q} = \begin{pmatrix} 3/5 \\ 2/5 \end{pmatrix} = \begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}$. The long-term proportion of mice in group A is 0.6. With 500 mice in total, the number in group A will be $0.6 \times 500 = 300$.
4. A system has three states. The transition matrix is given by $P = \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$. What is the most accurate description of state 2?
   Answer: State 2 is an absorbing state. When analyzing Markov chains, you need to examine how states behave by looking at the transition probabilities in the matrix. Each row represents transitions from one state, and each column represents transitions to a state. Looking at the transition matrix $P = \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$, focus on row 2 (the second row), which shows transitions from state 2. The probabilities are [0, 1, 0], meaning if you're in state 2, there's a 100% probability of staying in state 2 and 0% probability of moving to any other state. This defines an absorbing state – once you enter it, you cannot leave. Now examining the column for state 2 reveals that no other state can transition to state 2 (both entries are 0). This means state 2 can only be reached if the system starts there. Let's check each option: A is correct because state 2 has probability 1 of transitioning to itself. B is wrong because transient states eventually lead elsewhere – state 2 never leaves itself, making it absorbing, not transient. C is incorrect because the system cannot reach state 2 from states 1 or 3 (the transition probabilities are zero). D is wrong because states 1 and 3 only transition between each other with probability 0.5 each – state 2 is completely isolated from this cycle. Study tip: For Markov chain problems, always check the diagonal entries first. A probability of 1 on the diagonal immediately signals an absorbing state, while examining entire rows and columns reveals the complete state behavior.
5. Based on the study, which matrix $P$ correctly represents the monthly transition of customers, where the next month's state vector $\vec{x}_{k+1}$ is given by $P\vec{x}_k$?
   Answer: $P = \begin{pmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{pmatrix}$ The transition matrix $P$ should have columns that represent the movement 'from' a state. The first column describes customers starting with QuickEat: 70% stay with QuickEat (row 1) and 30% switch to GoGrub (row 2). So, the first column is $\begin{pmatrix} 0.7 \\ 0.3 \end{pmatrix}$. The second column describes customers starting with GoGrub: 20% switch to QuickEat (row 1) and 80% stay with GoGrub (row 2). So, the second column is $\begin{pmatrix} 0.2 \\ 0.8 \end{pmatrix}$. Combining these gives the correct matrix $P = \begin{pmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{pmatrix}$.
6. A system's state is described by the vector $\vec{x}_k$ at time $k$, and it evolves according to $\vec{x}_{k+1} = P\vec{x}_k$ with $P = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix}$. If the initial state is $\vec{x}_0 = \begin{pmatrix} 0.8 \\ 0.2 \end{pmatrix}$, what is the state vector $\vec{x}_2$?
   Answer: $\begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}$ This is a discrete dynamical system problem where you apply matrix multiplication iteratively to track how a state vector evolves over time. When you see $\vec{x}_{k+1} = P\vec{x}_k$, you're looking at a linear transformation that gets applied repeatedly. To find $\vec{x}_2$, you need to apply the transformation matrix $P$ twice. First, calculate $\vec{x}_1 = P\vec{x}_0$: $\vec{x}_1 = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix} \begin{pmatrix} 0.8 \\ 0.2 \end{pmatrix} = \begin{pmatrix} 0.5(0.8) + 0.5(0.2) \\ 0.5(0.8) + 0.5(0.2) \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}$ Then calculate $\vec{x}_2 = P\vec{x}_1$: $\vec{x}_2 = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix} \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}$ Choice A is correct. Notice that this matrix has identical rows, which means any vector gets transformed into $\begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}$ after one step and stays there. Choice B represents the initial state $\vec{x}_0$, suggesting the system doesn't change—a common misconception. Choice C looks like someone multiplied the initial vector by 0.5 element-wise rather than using proper matrix multiplication. Choice D appears to be an intermediate calculation error, possibly averaging incorrectly or stopping partway through the matrix multiplication. Study tip: With discrete systems, always compute step-by-step rather than trying shortcuts. Also, look for patterns—matrices with identical rows quickly converge to a fixed point, which can help you check your work.
7. If this trend continues, what will be the long-term percentage of residents who commute by car?
   Answer: $33.\bar{3}\%$ Let state 1 be car and state 2 be public transit. The transition matrix is $P = \begin{pmatrix} 0.90 & 0.05 \\ 0.10 & 0.95 \end{pmatrix}$. To find the steady-state vector $\vec{q}$, we solve $(P-I)\vec{q}=\vec{0}$. This gives $-0.10q_1 + 0.05q_2 = 0$, or $2q_1=q_2$. The eigenvector is of the form $\begin{pmatrix} k \\ 2k \end{pmatrix}$. Since $q_1+q_2=1$, we have $k+2k=1$, so $k=1/3$. The steady-state vector is $\vec{q} = \begin{pmatrix} 1/3 \\ 2/3 \end{pmatrix}$. The long-term percentage of car commuters is $q_1$, which is $1/3$ or $33.\bar{3}\%$.
8. A Markov process is described by the transition matrix $P = \begin{pmatrix} 0.5 & 0.25 \\ 0.5 & 0.75 \end{pmatrix}$. Which of the following vectors is the steady-state vector $\vec{q}$ for this process?
   Answer: $\vec{q} = \begin{pmatrix} 1/3 \\ 2/3 \end{pmatrix}$ A steady-state vector $\vec{q}$ must satisfy $P\vec{q} = \vec{q}$, which is equivalent to solving $(P-I)\vec{q} = \vec{0}$. Here, $P-I = \begin{pmatrix} -0.5 & 0.25 \\ 0.5 & -0.25 \end{pmatrix}$. This gives the equation $-0.5q_1 + 0.25q_2 = 0$, which simplifies to $2q_1 = q_2$. An eigenvector is thus of the form $\begin{pmatrix} k \\ 2k \end{pmatrix}$. For $\vec{q}$ to be a probability vector, its components must sum to 1. So, $k + 2k = 1$, which gives $3k=1$ or $k=1/3$. The steady-state vector is $\vec{q} = \begin{pmatrix} 1/3 \\ 2/3 \end{pmatrix}$.
9. The matrix $P = \begin{pmatrix} 1-a & b \\ a & 1-b \end{pmatrix}$ is the transition matrix for a regular Markov chain, with $0 < a < 1$ and $0 < b < 1$. What is the first component of the steady-state vector $\vec{q}$?
   Answer: $\frac{b}{a+b}$ To find the steady-state vector, we solve $(P-I)\vec{q} = \vec{0}$. The matrix $P-I$ is $\begin{pmatrix} -a & b \\ a & -b \end{pmatrix}$. The first row gives the equation $-aq_1 + bq_2 = 0$, which implies $aq_1 = bq_2$. A non-trivial solution is \vec{q} = \begin{pmatrix} b \\ a \end{pmatrix}}. To make this a probability vector, we normalize by dividing by the sum of the components, $a+b$. The normalized steady-state vector is $\vec{q} = \begin{pmatrix} b/(a+b) \\ a/(a+b) \end{pmatrix}$. The first component is $\frac{b}{a+b}$.
10. Which of the following matrices cannot be a transition matrix for a regular Markov chain?
    Answer: $\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ A regular Markov chain is one for which some power of the transition matrix, $P^k$, has all positive entries. This guarantees convergence to a unique steady-state vector regardless of the initial state. Matrix (D) describes a system with two states that trade places and a third state that is absorbing. If the system starts in state 1 or 2, it will oscillate between them ($P^2$ will have zeros) and never reach state 3. If it starts in state 3, it stays there. The long-term behavior depends on the initial state, so the chain is not regular. Matrix (A) and (B) are regular because they are positive. Matrix (C) is also regular as $P^2$ will have all positive entries in the top-left $2 \times 2$ block and probability will eventually leak into the third state from there.
11. For a regular Markov chain with transition matrix $P$ and unique steady-state vector $\vec{q}$, what does the matrix power $P^k$ approach as $k \to \infty$?
    Answer: A matrix where every column is the steady-state vector $\vec{q}$. A key property of regular Markov chains is that as $k$ grows, the matrix $P^k$ converges to a matrix where every column is the unique steady-state vector $\vec{q}$. This means that for any initial state $\vec{x}_0$, the long-term state $P^k \vec{x}_0$ will approach $(\vec{q} \; \vec{q} \; \dots \; \vec{q})\vec{x}_0 = \vec{q} (\sum x_i) = \vec{q}$, since the components of $\vec{x}_0$ sum to 1.
12. Let $P$ be an $n \times n$ column-stochastic matrix (all entries non-negative, columns sum to 1). Which of the following statements about $P$ is not guaranteed to be true?
    Answer: The matrix $P$ has $n$ linearly independent eigenvectors. While many stochastic matrices are diagonalizable (meaning they have $n$ linearly independent eigenvectors), it is not a guaranteed property. For example, a matrix could have repeated eigenvalues where the geometric multiplicity is less than the algebraic multiplicity. Statements A, B, and D are always true for a column-stochastic matrix. Statement A is true because the columns of $(P-I)$ sum to the zero vector, making it singular. Statement B is a known property from the Perron-Frobenius theory for non-negative matrices. Statement D is true because the sum of the components of $P\vec{x}$ is $(\sum_i \sum_j P_{ij}x_j) = \sum_j (\sum_i P_{ij})x_j = \sum_j (1)x_j$, which is the sum of the components of $\vec{x}$.

Start this quiz