Markov Chains: Transition Matrices - Finite Mathematics

A Markov chain has the transition matrix $T = \begin{pmatrix} 1 & 0.5 & 0 \\ 0 & 0 & 0.5 \\ 0 & 0.5 & 0.5 \end{pmatrix}$ . Which statement accurately describes the long-term behavior of this system?
Answer: The probability of being in State 1 will approach 1, regardless of the initial state (assuming it's a valid probability vector). The matrix represents an absorbing Markov chain because the entry $T_{11}=1$ , meaning that once the system enters State 1, it never leaves. States 2 and 3 are transient states. We need to determine if the absorbing state is reachable from the transient states. From State 2, there is a probability of 0.5 to move to State 1 ( $T_{12}=0.5$ ). From State 3, the system can move to State 2 ( $T_{23}=0.5$ ), and from State 2 it can move to State 1. Since the single absorbing state is reachable from all other states, the system will eventually be absorbed into State 1 with probability 1. This means that as time goes on, the probability of being in State 1 approaches 1, while the probabilities of being in States 2 and 3 approach 0. This outcome is independent of the initial state vector $S_0$ (as long as there is some non-zero probability of not being in State 1 initially). (A) is false because this is not a regular chain, and the probabilities for the transient states will go to zero. (B) is false because there is a path from the (2,3) subsystem to State 1. (C) is false because there is only one absorbing state, leading to a single long-term outcome, not multiple possibilities.
A Markov process has transition matrix $T$ and the state vector at time $k$ is $S_k$ . Which of the following is a necessary property of any state vector $S_k$ for all $k \ge 0$ ? I. The sum of the components of $S_k$ is 1. II. All components of $S_k$ are non-negative. III. $T S_k = S_k$ .
Answer: I and II only A state vector, by definition, represents the probability distribution of the system across its possible states at a certain time. I. As a probability distribution, the sum of the probabilities of all possible outcomes must be 1. Therefore, the sum of the components of $S_k$ must be 1. This is a necessary property. II. Since each component of $S_k$ is a probability, its value must be between 0 and 1, inclusive. Therefore, all components must be non-negative. This is a necessary property. III. The equation $T S_k = S_k$ is the condition for a steady-state (or equilibrium) vector. It means that once the system reaches this state, it will remain there. However, this is not true for a general state vector $S_k$ at an arbitrary time step $k$ . The system is typically evolving towards the steady state, so $S_{k+1} = T S_k \ne S_k$ in general. Therefore, this is not a necessary property of any state vector. Thus, only properties I and II are necessary for any state vector $S_k$ .
A Markov chain has transition matrix $Q$ where state 3 is absorbing. The fundamental matrix is $N = (I - Q_t)^{-1} = \begin{bmatrix} 2.5 & 1.0 \\ 0.5 & 1.5 \end{bmatrix}$ , where $Q_t$ contains transitions between transient states 1 and 2. Starting from state 1, what is the expected number of times the system will visit state 2 before absorption?
Answer: 1.0 When you encounter Markov chain problems with absorbing states, you're working with the fundamental matrix $N = (I - Q_t)^{-1}$ , which contains crucial information about expected visits between transient states before absorption occurs. The key insight is understanding what each entry in the fundamental matrix represents. The entry $N_{ij}$ tells you the expected number of times the system will visit state $j$ , given that it starts in state $i$ . Since we're starting from state 1 and want to know expected visits to state 2, we need $N_{12}$ . Looking at the given fundamental matrix $N = \begin{bmatrix} 2.5 & 1.0 \\ 0.5 & 1.5 \end{bmatrix}$ , the entry in row 1, column 2 is $N_{12} = 1.0$ . This directly gives us the expected number of visits to state 2 starting from state 1. Choice A (2.5) represents $N_{11}$ , the expected number of times we'll visit state 1 starting from state 1. Choice C (2.5) is the same incorrect interpretation. Choice D (0.5) represents $N_{21}$ , the expected visits to state 1 starting from state 2, which isn't what we're asked. These are common mix-ups when students confuse row and column positions or misinterpret which state is the starting point versus the destination. The correct answer is B) 1.0. Study tip: Always identify the starting state (determines the row) and target state (determines the column) clearly before reading values from the fundamental matrix. The notation $N_{ij}$ means "starting from $i$ , visiting $j$ ."
On Monday morning, there are 100 cars at the Airport, 50 Downtown, and 50 at the Suburban location. Assuming every car is rented and returned each day, what is the expected number of cars at the Downtown location on Wednesday morning (after two days)?
Answer: $64.5$ First, construct the transition matrix $T$ where $T_{ij}$ is the probability of moving from location $j$ to location $i$ . The states are A, D, S. The columns represent the starting location (From) and rows represent the return location (To). $T = \begin{pmatrix} 0.5 & 0.1 & 0.1 \\ 0.3 & 0.6 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{pmatrix}$ The initial distribution of cars is a vector $N_0 = \begin{pmatrix} 100 \\ 50 \\ 50 \end{pmatrix}$ . The distribution on Tuesday morning ( $N_1$ ) is $T N_0$ : $N_1 = \begin{pmatrix} 0.5 & 0.1 & 0.1 \\ 0.3 & 0.6 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{pmatrix} \begin{pmatrix} 100 \\ 50 \\ 50 \end{pmatrix} = \begin{pmatrix} 50+5+5 \\ 30+30+5 \\ 20+15+40 \end{pmatrix} = \begin{pmatrix} 60 \\ 65 \\ 75 \end{pmatrix}$ The distribution on Wednesday morning ( $N_2$ ) is $T N_1$ : $N_2 = \begin{pmatrix} 0.5 & 0.1 & 0.1 \\ 0.3 & 0.6 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{pmatrix} \begin{pmatrix} 60 \\ 65 \\ 75 \end{pmatrix}$ We only need the number of cars at the Downtown location, which is the second component of $N_2$ : $N_{2,D} = (0.3)(60) + (0.6)(65) + (0.1)(75) = 18 + 39 + 7.5 = 64.5$ (A) results from transposing the transition matrix. (C) is the expected number of cars at the Downtown location after only one day ( $N_{1,D}$ ). (D) results from a conceptual error in applying the matrix, for instance using the second column of T on $N_1$ : $0.1(60)+0.6(65)+0.3(75)=6+39+22.5=67.5$ .
Let $T$ be the transition matrix for the income groups. What is the correct interpretation of the entry in the third row and first column of the matrix $T^2$ , denoted $(T^2)_{31}$ ?
Answer: The probability that a family in the low-income group will be in the high-income group after two years. The matrix $T^k$ represents the transition probabilities after $k$ steps. The entry $(T^k)_{ij}$ gives the probability of moving from state $j$ to state $i$ in $k$ steps. In this context, the states are 1=Low-income, 2=Middle-income, and 3=High-income. Therefore, $(T^2)_{31}$ represents the probability of transitioning from state 1 (Low-income) to state 3 (High-income) in exactly two steps (two years). (B) is the interpretation of $(T^2)_{13}$ . (C) describes $(T_{31})^2$ , which is not the same as $(T^2)_{31}$ . (D) describes a first-passage time probability, which is a different concept and not what an entry of $T^2$ represents.
Let $T$ be the transition matrix for a regular Markov chain. Which of the following statements is NOT always true?
Answer: The matrix $T$ cannot have any zero entries. A Markov chain is regular if some power of its transition matrix, $T^k$ , has all positive entries. This does not mean that $T$ itself must have all positive entries. For example, the matrix $T = \begin{pmatrix} 0.5 & 1 \\ 0.5 & 0 \end{pmatrix}$ is regular because $T^2 = \begin{pmatrix} 0.75 & 0.5 \\ 0.25 & 0.5 \end{pmatrix}$ has all positive entries, yet $T$ contains a zero. Therefore, the statement that $T$ cannot have any zero entries is not always true. (A), (B), and (D) are all fundamental properties of regular Markov chains. A regular Markov chain is guaranteed to have a unique steady-state vector $S$ . The system will always converge to this vector $S$ regardless of the initial state. The limit of $T^n$ as $n \to \infty$ is a matrix where each column is the steady-state vector $S$ , hence all columns are identical.
Let $P$ be the transition matrix for a Markov chain with three states. $P = \begin{pmatrix} 0.5 & x & 0.2 \\ y & 0.2 & 0.3 \\ 0.2 & 0.5 & z \end{pmatrix}$ If the initial state vector is $S_0 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$ , and the state vector after one step is $S_1 = \begin{pmatrix} 0.3 \\ 0.2 \\ 0.5 \end{pmatrix}$ , what is the value of $y$ ?
Answer: $0.3$ There are two key properties to use. First, for a matrix to be a transition matrix, the sum of the entries in each column must be 1. Second, the state vector after one step is given by $S_1 = P S_0$ . Let's first use the second property with the given vectors: $S_1 = P S_0 \implies \begin{pmatrix} 0.3 \\ 0.2 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 & x & 0.2 \\ y & 0.2 & 0.3 \\ 0.2 & 0.5 & z \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$ The product on the right side is simply the second column of $P$ : $\begin{pmatrix} 0.3 \\ 0.2 \\ 0.5 \end{pmatrix} = \begin{pmatrix} x \\ 0.2 \\ 0.5 \end{pmatrix}$ This tells us that $x=0.3$ and confirms the values of the other entries in the second column. However, it does not give us the value of $y$ . To find $y$ , we must use the first property: the columns of $P$ must sum to 1. Looking at the first column, we have: $0.5 + y + 0.2 = 1$ $y + 0.7 = 1$ $y = 0.3$ Thus, the value of $y$ is $0.3$ . The information about $S_0$ and $S_1$ is not needed to find $y$ but is required to confirm $P$ is a valid transition matrix for the process described. (B) is incorrect; this would result if one assumed the rows sum to 1. (C) is a calculation error, e.g., $1-0.2=0.8$ . (D) is incorrect because the column-sum property allows $y$ to be determined.
A company's inventory system follows a Markov chain with states representing stock levels: Low (L), Medium (M), High (H). The long-run proportions are 30% Low, 50% Medium, 20% High. If the system currently has the distribution [0.4, 0.4, 0.2], what can be concluded about the transition matrix?
Answer: The current distribution will converge to [0.3, 0.5, 0.2] regardless of the specific transition probabilities For any irreducible finite Markov chain, the steady-state distribution is unique and the system will converge to it from any starting distribution, regardless of the specific transition probabilities (as long as they define an irreducible chain). Choice B is incorrect because zero entries are not required for this steady state. Choice C is wrong because High is already at steady state (0.2 = 0.2), but this doesn't mean it's 'closer' in any meaningful sense. Choice D is incorrect because steady-state proportions don't determine which diagonal entries are largest.
Consider the transition matrix $M = \begin{bmatrix} 0.8 & 0.2 & 0 \\ 0.1 & 0.7 & 0.2 \\ 0 & 0.3 & 0.7 \end{bmatrix}$ . Which statement about this Markov chain is correct?
Answer: The chain is irreducible because every state can eventually reach every other state The chain is irreducible because from state 1 you can reach state 2 (directly), from state 2 you can reach state 3 (directly), and from state 3 you can reach state 2 then state 1. All states communicate with each other. Choice A confuses high self-transition probability with absorption (absorbing states have probability 1 of staying). Choice B confuses direct reachability with eventual reachability. Choice D is wrong because state 1 can reach states 2 and 3, so they don't form a separate closed class.
The system is defined as "excited" if the particle is measured in the high-energy state for two consecutive time steps. Otherwise, the system is "not excited". In the long run, what is the probability that the system is "not excited"?
Answer: $77/80$ First, let's find the steady-state probabilities for the particle being in state H or L. The transition matrix for the particle (with states H, L) is: $T_{particle} = \begin{pmatrix} P(H|H) & P(H|L) \\ P(L|H) & P(L|L) \end{pmatrix} = \begin{pmatrix} 0.3 & 0.1 \\ 0.7 & 0.9 \end{pmatrix}$ Let the steady-state vector be $S = \begin{pmatrix} h \\ l \end{pmatrix}$ . We solve $TS=S$ . From the first row: $0.3h + 0.1l = h \implies 0.1l = 0.7h \implies l = 7h$ . Since $h+l=1$ , we have $h+7h=1 \implies 8h=1 \implies h=1/8$ . Then $l=7/8$ . So, in the long run, the particle is in state H with probability $1/8$ . The system is "excited" if it is in state H at time $t$ and time $t+1$ . The long-term probability of this is $P(H_{t+1} \text{ and } H_t) = P(H_{t+1}|H_t) \times P(H_t)$ . In the steady state, $P(H_t) = h = 1/8$ . The conditional probability $P(H_{t+1}|H_t)$ is given as 0.3. So, the probability of being "excited" is $0.3 \times (1/8) = 3/80$ . The question asks for the probability of being "not excited", which is $1 - P("excited") = 1 - 3/80 = 77/80$ . (A) is the probability of being "excited". (B) is the long-term probability of being in state H. (C) is the long-term probability of being in state L.
A two-state Markov chain has the transition matrix $T = \begin{pmatrix} p & 0.3 \\ 1-p & 0.7 \end{pmatrix}$ . If the system starts in State 1, its state vector is $S_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ . After two steps, the state vector is $S_2 = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix}$ . Given that $0 \le p \le 1$ , what is the value of $p$ ?
Answer: $0.5$ The state vector after two steps is given by $S_2 = T^2 S_0$ . First, we compute $T^2$ : $T^2 = \begin{pmatrix} p & 0.3 \\ 1-p & 0.7 \end{pmatrix} \begin{pmatrix} p & 0.3 \\ 1-p & 0.7 \end{pmatrix} = \begin{pmatrix} p^2 + 0.3(1-p) & 0.3p + 0.21 \\ p(1-p) + 0.7(1-p) & 0.3(1-p) + 0.49 \end{pmatrix} = \begin{pmatrix} p^2 - 0.3p + 0.3 & 0.3p + 0.21 \\ -p^2 + 0.3p + 0.7 & -0.3p + 0.79 \end{pmatrix}$ Now, we calculate $S_2$ : $S_2 = T^2 S_0 = \begin{pmatrix} p^2 - 0.3p + 0.3 & 0.3p + 0.21 \\ -p^2 + 0.3p + 0.7 & -0.3p + 0.79 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} p^2 - 0.3p + 0.3 \\ -p^2 + 0.3p + 0.7 \end{pmatrix}$ We are given that $S_2 = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix}$ . Equating the first components gives the equation: $p^2 - 0.3p + 0.3 = 0.4$ . This simplifies to the quadratic equation $p^2 - 0.3p - 0.1 = 0$ . We can solve this by factoring: $(p-0.5)(p+0.2) = 0$ . The solutions are $p=0.5$ and $p=-0.2$ . Since $p$ must be a probability, $0 \le p \le 1$ , so we must have $p=0.5$ .
A Markov chain models website user behavior with states: Browse (B), Purchase (P), and Exit (E). The transition probabilities from Browse are: 60% stay in Browse, 25% go to Purchase, 15% Exit. From Purchase: 40% return to Browse, 20% stay in Purchase, 40% Exit. Exit is absorbing. If a user starts browsing, what is the probability they will eventually make at least one purchase before exiting?
Answer: 0.625 This requires setting up absorption probabilities. Let p be the probability of eventually purchasing starting from Browse. Then p = 0.25 + 0.60p (direct purchase plus staying in Browse then eventually purchasing). Solving: p = 0.25 + 0.60p, so 0.40p = 0.25, thus p = 0.625. Choice B incorrectly calculates the one-step probability. Choice C uses the wrong absorption formula. Choice D makes an error in the recursive equation setup.
A three-state Markov chain has the property that $P^{10} = \begin{bmatrix} 0.5 & 0.3 & 0.2 \\ 0.5 & 0.3 & 0.2 \\ 0.5 & 0.3 & 0.2 \end{bmatrix}$ . Starting with state vector $\begin{bmatrix} 0.2 \\ 0.6 \\ 0.2 \end{bmatrix}$ , what will be the state vector after 12 steps?
Answer: $\begin{bmatrix} 0.5 \\ 0.3 \\ 0.2 \end{bmatrix}$ When you encounter a Markov chain problem involving multiple steps, the key insight is understanding how matrix powers work and recognizing patterns in transition matrices. To find the state vector after 12 steps, you need to compute $P^{12} \cdot \mathbf{v}_0$ , where $\mathbf{v}_0$ is your initial state vector. Since $P^{12} = P^{10} \cdot P^2$ , you can use the given $P^{10}$ matrix. However, notice something crucial about $P^{10}$ : all three rows are identical, each being $[0.5, 0.3, 0.2]$ . This means the Markov chain has reached its steady state by step 10. When a transition matrix has identical rows, multiplying it by any state vector always produces the same result—the steady-state vector. Let's verify: $P^{10} \cdot \begin{bmatrix} 0.2 \\ 0.6 \\ 0.2 \end{bmatrix} = \begin{bmatrix} 0.5 \\ 0.3 \\ 0.2 \end{bmatrix}$ Since the system is already at steady state after 10 steps, $P^{12} = P^{10} \cdot P^2$ will also have identical rows (steady state is absorbing), giving the same result. Choice A $\begin{bmatrix} 0.4 \\ 0.4 \\ 0.2 \end{bmatrix}$ incorrectly assumes some averaging with the initial vector. Choice B $\begin{bmatrix} 0.2 \\ 0.6 \\ 0.2 \end{bmatrix}$ mistakenly thinks the system returns to the initial state. Choice C $\begin{bmatrix} 0.35 \\ 0.45 \\ 0.20 \end{bmatrix}$ appears to blend initial and steady states incorrectly. The answer is D: $\begin{bmatrix} 0.5 \\ 0.3 \\ 0.2 \end{bmatrix}$ . Study tip: When you see identical rows in a transition matrix power, the system has reached steady state—any further steps maintain that same distribution.
A two-state Markov process has a transition matrix $T$ . Its steady-state vector is $S=\begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}$ . When the system starts in the state $S_0=\begin{pmatrix} 1/3 \\ 2/3 \end{pmatrix}$ , the next state is $S_1=\begin{pmatrix} 1/2 \\ 1/2 \end{pmatrix}$ . Which of the following is the transition matrix $T$ ?
Answer: $\begin{pmatrix} 5/6 & 1/3 \\ 1/6 & 2/3 \end{pmatrix}$ Let the transition matrix be $T = \begin{pmatrix} a & b \\ 1-a & 1-b \end{pmatrix}$ . We are given two conditions: $TS=S$ and $TS_0=S_1$ . We can use these to form a system of equations for $a$ and $b$ . 1. From $TS=S$ : $\begin{pmatrix} a & b \\ 1-a & 1-b \end{pmatrix} \begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix} = \begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}$ The first row gives the equation: $a(2/3) + b(1/3) = 2/3$ , which simplifies to $2a+b=2$ . 2. From $TS_0=S_1$ : $\begin{pmatrix} a & b \\ 1-a & 1-b \end{pmatrix} \begin{pmatrix} 1/3 \\ 2/3 \end{pmatrix} = \begin{pmatrix} 1/2 \\ 1/2 \end{pmatrix}$ The first row gives the equation: $a(1/3) + b(2/3) = 1/2$ , which simplifies to $a+2b=3/2$ , or $2a+4b=3$ . Now we solve the system: (i) $2a+b=2$ (ii) $2a+4b=3$ Subtracting (i) from (ii) gives $3b=1$ , so $b=1/3$ . Substituting $b=1/3$ into (i) gives $2a + 1/3 = 2$ , so $2a=5/3$ , and $a=5/6$ . The matrix is $T = \begin{pmatrix} 5/6 & 1/3 \\ 1-5/6 & 1-1/3 \end{pmatrix} = \begin{pmatrix} 5/6 & 1/3 \\ 1/6 & 2/3 \end{pmatrix}$ . This matches option C. (A) has a steady state of $[1/2, 1/2]^T$ . (B) has a steady state of $[1/2, 1/2]^T$ . (D) has a steady state of $[1, 0]^T$ .

Start this quiz