The Markov Property & Transition Matrices
A sequence of trials form a **Markov Chain** if the conditional probability of future states depends ONLY on the current state, and not on the past history (the *memoryless property*):
In standard IB notation where state probability vectors are written as row vectors $\mathbf{s}_n$:
Regular Chains & Steady-State Distribution
A Markov chain is **regular** if there exists some positive integer power $k$ such that all elements in $\mathbf{T}^k$ are strictly positive ($T^k_{ij} > 0$).
For a regular Markov chain, as $n \to \infty$, the state distribution converges to a unique **steady-state distribution vector** $\mathbf{\pi}$ independent of the initial state:
Solving on GDC: Replace one redundant linear equation from $\mathbf{\pi}(\mathbf{T} - \mathbf{I}) = \mathbf{0}$ with the normalization condition $\pi_1 + \pi_2 + \dots + \pi_k = 1$, and solve using matrix inverse $\mathbf{A}^{-1}\mathbf{b}$ or rref.
Absorbing Markov Chains
A state is **absorbing** if once entered, the process never leaves it ($T_{ii} = 1$). A chain is an absorbing chain if it has at least one absorbing state, and from any state it is possible to reach an absorbing state.
A customer either buys Brand A or Brand B each month. If a customer buys Brand A, the probability they buy Brand A next month is $0.7$. If they buy Brand B, the probability they switch to Brand A is $0.4$. Write down the transition matrix $\mathbf{T}$.
Solution:
From A: $P(A \to A) = 0.7$, $P(A \to B) = 1 - 0.7 = 0.3$. [A1]
From B: $P(B \to A) = 0.4$, $P(B \to B) = 1 - 0.4 = 0.6$. [A1]
$\mathbf{T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$. [A1]
Initially, $60\%$ of customers buy Brand A and $40\%$ buy Brand B. Using $\mathbf{T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$, find the market share of each brand after 2 months.
Solution:
Initial state: $\mathbf{s}_0 = [0.6, 0.4]$. [A1]
$\mathbf{s}_2 = \mathbf{s}_0 \mathbf{T}^2$. [M1]
$\mathbf{T}^2 = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = \begin{pmatrix} 0.49 + 0.12 & 0.21 + 0.18 \\ 0.28 + 0.24 & 0.12 + 0.36 \end{pmatrix} = \begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{pmatrix}$. [A1]
$\mathbf{s}_2 = [0.6(0.61) + 0.4(0.52), 0.6(0.39) + 0.4(0.48)] = [0.366 + 0.208, 0.234 + 0.192] = [0.574, 0.426]$. [A1]
Brand A: $57.4\%$, Brand B: $42.6\%$.
Find the long-term steady-state market share $\mathbf{\pi} = [\pi_A, \pi_B]$ for the transition matrix $\mathbf{T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$.
Solution:
Set $\mathbf{\pi} \mathbf{T} = \mathbf{\pi}$: $[\pi_A, \pi_B] \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = [\pi_A, \pi_B]$. [M1]
$0.7\pi_A + 0.4\pi_B = \pi_A \implies 0.4\pi_B = 0.3\pi_A \implies \pi_B = \frac{3}{4}\pi_A$. [A1]
Normalization condition: $\pi_A + \pi_B = 1$. [M1]
$\pi_A + \frac{3}{4}\pi_A = 1 \implies \frac{7}{4}\pi_A = 1 \implies \pi_A = \frac{4}{7} \approx 0.5714$. [A1]
$\pi_B = \frac{3}{7} \approx 0.4286$. [A1]
Brand A has $\frac{4}{7} \approx 57.1\%$ and Brand B has $\frac{3}{7} \approx 42.9\%$.
Explain why the transition matrix $\mathbf{T} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ does NOT represent a regular Markov chain.
Solution:
Powers of $\mathbf{T}$: $\mathbf{T}^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, $\mathbf{T}^3 = \mathbf{T}$, $\mathbf{T}^4 = \mathbf{I}$, etc. [M1]
For any power $k \ge 1$, $\mathbf{T}^k$ will always contain zero elements (it oscillates periodically between $\mathbf{T}$ and $\mathbf{I}$). [R1]
Because there is no power $k$ where all entries are strictly positive, the chain is not regular (it is periodic). [A1]
A board game has 3 states: 1 (Start), 2 (Middle), and 3 (Finish). State 3 is an absorbing state. The transition matrix is:
$$\mathbf{T} = \begin{pmatrix} 0.2 & 0.5 & 0.3 \\ 0 & 0.4 & 0.6 \\ 0 & 0 & 1 \end{pmatrix}$$Find the fundamental matrix $\mathbf{N} = (\mathbf{I} - \mathbf{Q})^{-1}$ for transient states $\{1, 2\}$, and calculate the expected number of turns to finish starting from State 1.
Solution:
The transient submatrix is $\mathbf{Q} = \begin{pmatrix} 0.2 & 0.5 \\ 0 & 0.4 \end{pmatrix}$. [A1]
$\mathbf{I} - \mathbf{Q} = \begin{pmatrix} 0.8 & -0.5 \\ 0 & 0.6 \end{pmatrix}$. [M1]
$\det(\mathbf{I} - \mathbf{Q}) = 0.8(0.6) - 0 = 0.48$.
$\mathbf{N} = (\mathbf{I} - \mathbf{Q})^{-1} = \frac{1}{0.48} \begin{pmatrix} 0.6 & 0.5 \\ 0 & 0.8 \end{pmatrix} = \begin{pmatrix} 1.25 & 1.0417 \\ 0 & 1.6667 \end{pmatrix}$. [A2]
Expected turns starting from State 1: sum of row 1 in $\mathbf{N} = 1.25 + 1.0417 \approx 2.29\text{ turns}$. [A1]
A weather model in a mountain village has 3 states: Sunny ($S$), Rainy ($R$), and Snowy ($W$). The transition matrix is:
$$\mathbf{T} = \begin{pmatrix} 0.6 & 0.3 & 0.1 \\ 0.2 & 0.5 & 0.3 \\ 0.1 & 0.4 & 0.5 \end{pmatrix}$$If Monday is Snowy, find the probability that Wednesday is Sunny.
Solution:
Initial state Monday Snowy: $\mathbf{s}_0 = [0, 0, 1]$. [A1]
Wednesday is 2 days later: $\mathbf{s}_2 = \mathbf{s}_0 \mathbf{T}^2$. [M1]
The probability of Sunny on Wednesday is the $(3, 1)$ element of $\mathbf{T}^2$: [M1]
Row 3 of $\mathbf{T}$ times Column 1 of $\mathbf{T}$: $0.1(0.6) + 0.4(0.2) + 0.5(0.1) = 0.06 + 0.08 + 0.05 = 0.19$. [A1]
Probability is $0.19$ (or $19\%$).
State the relationship between the eigenvalues of a stochastic transition matrix $\mathbf{T}$ and its steady-state distribution vector.
Solution:
Every stochastic matrix has a dominant eigenvalue of $\lambda = 1$. [R1]
The steady-state probability vector $\mathbf{\pi}$ is the left eigenvector of $\mathbf{T}$ corresponding to $\lambda = 1$: $\mathbf{\pi}\mathbf{T} = 1\mathbf{\pi}$. [A2]
All other eigenvalues satisfy $|\lambda_i| < 1$, ensuring decay of transient components over time. [R1]
In a Gambler's Ruin problem with states $0, 1, 2, 3$, states $0$ and $3$ are absorbing boundaries. The gambler starts with $1$ coin and bets $1$ coin each round with win probability $p = 0.5$. Write down the transition matrix in canonical form.
Solution:
Ordering states with absorbing states $\{0, 3\}$ first, transient states $\{1, 2\}$ second: [M1]
From 0: stays in 0 ($P=1$); From 3: stays in 3 ($P=1$).
From 1: goes to 0 with prob $0.5$, goes to 2 with prob $0.5$.
From 2: goes to 1 with prob $0.5$, goes to 3 with prob $0.5$. [A1]
Canonical matrix: $\mathbf{T} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0 & 0.5 \\ 0 & 0.5 & 0.5 & 0 \end{pmatrix}$ where $\mathbf{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, $\mathbf{R} = \begin{pmatrix} 0.5 & 0 \\ 0 & 0.5 \end{pmatrix}$, $\mathbf{Q} = \begin{pmatrix} 0 & 0.5 \\ 0.5 & 0 \end{pmatrix}$. [A2]
Using the Gambler's Ruin problem in Exercise 8, find the probability that the gambler starting with $1$ coin is eventually ruined (absorbed into state 0).
Solution:
$\mathbf{I} - \mathbf{Q} = \begin{pmatrix} 1 & -0.5 \\ -0.5 & 1 \end{pmatrix}$. $\det = 1 - 0.25 = 0.75$. [M1]
$\mathbf{N} = \frac{1}{0.75} \begin{pmatrix} 1 & 0.5 \\ 0.5 & 1 \end{pmatrix} = \begin{pmatrix} \frac{4}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{4}{3} \end{pmatrix}$. [A1]
Absorption probability matrix $\mathbf{B} = \mathbf{N}\mathbf{R} = \begin{pmatrix} \frac{4}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{4}{3} \end{pmatrix} \begin{pmatrix} 0.5 & 0 \\ 0 & 0.5 \end{pmatrix} = \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{2}{3} \end{pmatrix}$. [M1]
Starting with 1 coin (row 1), the probability of ruin (state 0) is $\frac{2}{3} \approx 66.7\%$. [A1]
Explain how Google's PageRank algorithm is fundamentally modeled as a regular Markov chain.
Solution:
Web pages are modeled as states, and hyperlinks represent directed transitions between states. [A1]
A random surfer moves from page to page following links with probability $d$ (damping factor $\approx 0.85$), and jumps to any random page with probability $1 - d$. [A1]
This damping factor ensures all entries in the transition matrix are non-zero, making the chain regular. [R1]
The PageRank score of each web page is simply its coordinate in the steady-state distribution vector $\mathbf{\pi}$. [A1]
Core Formulas (Topic 4 AHL)
| State Vector Transition | $$\mathbf{s}_n = \mathbf{s}_0 \mathbf{T}^n$$ |
| Steady-State System | $$\mathbf{\pi} \mathbf{T} = \mathbf{\pi} \quad \text{with} \quad \sum \pi_i = 1$$ |
| Canonical Absorbing Form | $$\mathbf{T} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{R} & \mathbf{Q} \end{pmatrix}$$ |
| Fundamental Matrix & Absorption | $$\mathbf{N} = (\mathbf{I} - \mathbf{Q})^{-1}, \qquad \mathbf{B} = \mathbf{N}\mathbf{R}$$ |
Top 5 IB Exam Traps to Avoid
- Trap 1: Row Vector vs Column Vector Conventions: IB AI HL uses row vectors ($\mathbf{s}_{n+1} = \mathbf{s}_n \mathbf{T}$), meaning rows of $\mathbf{T}$ sum to 1. Do not transpose the matrix unless the question explicitly asks for column vector convention.
- Trap 2: Forgetting the normalization equation: $\mathbf{\pi}(\mathbf{T} - \mathbf{I}) = \mathbf{0}$ has infinite solutions! You must include $\pi_1 + \dots + \pi_k = 1$ to obtain the unique probability distribution.
- Trap 3: Regularity misconception: Having no zeros in $\mathbf{T}$ is not required; regularity only requires that *some power* $\mathbf{T}^k$ has all positive entries.
- Trap 4: Incorrect canonical partition: Ensure absorbing states are placed at the top/left of the matrix when extracting $\mathbf{Q}$ and $\mathbf{R}$.
- Trap 5: Calculation of expected steps: The expected steps from transient state $i$ to absorption is the sum of row $i$ in $\mathbf{N}$, not the determinant or diagonal element.
5-Question Concept Check
Score: - / 51. In an IB standard row-stochastic transition matrix $\mathbf{T}$, each row must sum to:
2. What is an absorbing state in a Markov chain?
3. What is the fundamental matrix $\mathbf{N}$ for an absorbing Markov chain with transient matrix $\mathbf{Q}$?
4. What dominant eigenvalue is guaranteed for every stochastic matrix?
5. If $\mathbf{T} = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix}$, what is the steady-state vector?