Markov Chains

If it’s sunny today, how likely is rain in three days? If customers switch phone companies every year, what share will each company have in the long run? A Markov chain models a system that moves between a few states in steps, where the chance of moving to each state depends only on the state it’s in now. Matrices make the calculations quick: one matrix multiplication moves the whole system forward one step.

Key ideas

States and transition diagrams

A Markov chain has a set of states (for example, “sunny” and “rainy”) and, at each step, moves from its current state to another state (or stays put) with fixed probabilities. These transition probabilities depend only on the current state, not on how the system got there.

A transition diagram shows the states as circles and each possible move as an arrow labelled with its probability. The probabilities on the arrows leaving each state add up to $1$.

A weather model: a sunny day is followed by a sunny day with probability $0.8$; a rainy day is followed by a sunny day with probability $0.4$.

The transition matrix

The transition matrix $T$ holds all the transition probabilities. This page uses the convention in the IB guide:

$T_{ij}$ is the probability of moving from state $j$ to state $i$.

So each column is a “from” state and each row is a “to” state, and each column adds up to $1$. For the weather diagram, with the states in the order sunny, rainy:

$$T = \begin{pmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{pmatrix} \qquad \begin{matrix} \text{columns: from S, from R} \\ \text{rows: to S, to R} \end{matrix}$$

Some textbooks and websites use the opposite convention (rows are “from” states and rows add to $1$). Their matrices are the transpose of these, and they multiply in the other order. Stick to the column convention in IB work, and label your states.

State matrices

A state matrix (column vector) $s_n$ gives the probability of being in each state after $n$ steps. The initial state matrix $s_0$ describes the start. For example, “it’s sunny today” is $s_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$, and “there’s a $30\%$ chance of rain today” is $s_0 = \begin{pmatrix} 0.7 \\ 0.3 \end{pmatrix}$. The entries of a state matrix add up to $1$. A state matrix can also hold numbers or proportions of a population (like the number of customers of each company) instead of probabilities.

To move one step forward, multiply by $T$ on the left: $s_1 = T s_0$, $s_2 = T s_1 = T^2 s_0$, and in general

$$s_n = T^n s_0$$

Powers of the transition matrix

The entries of $T^n$ are the probabilities of moving between states in exactly $n$ steps: $(T^n)_{ij}$ is the probability of being in state $i$ after $n$ steps, starting from state $j$. Use your GDC’s matrix functions to find powers.

Regular chains and the steady state

A Markov chain is regular if some power $T^k$ has all entries positive (greater than $0$). That means it’s possible to get from every state to every state in exactly $k$ steps.

For a regular chain, as $n$ gets large:

• $s_n$ settles down to a steady state $s$ that does not depend on the initial state $s_0$
• every column of $T^n$ gets closer and closer to $s$.

The steady state is the state matrix that doesn’t change when you multiply by $T$:

$$T s = s, \qquad \text{with the entries of } s \text{ adding to } 1$$

There are two ways to find it:

1. Repeated multiplication: compute $T^n$ for a large $n$ (like $T^{50}$) on your GDC. Each column is (approximately) the steady state.
2. Solving equations: write $Ts = s$ as a system of linear equations, replace one of them with “the entries add to $1$”, and solve. This gives exact answers. Exam questions say when exact values are required.

In the language of eigenvalues and eigenvectors, $Ts = s$ says that the steady state is an eigenvector of $T$ with eigenvalue $1$, scaled so its entries add to $1$.

Not every chain is regular. For $T = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, the system just flips between the two states forever, and the powers of $T$ alternate between $T$ and the identity matrix, so they never have all entries positive.

Worked examples

Example 1: Writing a transition matrix

Use the weather model in the diagram. It’s sunny on Monday.

• (a) Write the transition matrix $T$ and the initial state matrix $s_0$.
• (b) Find the probability that it is sunny on Tuesday, and on Wednesday.

Solution.

(a) With the states in the order sunny (S), rainy (R), the column for “from S” holds the probabilities $0.8$ (to S) and $0.2$ (to R):

$$T = \begin{pmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{pmatrix}, \qquad s_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$

Check: each column adds to $1$.

(b) Tuesday is one step later:

$$s_1 = T s_0 = \begin{pmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.8 \\ 0.2 \end{pmatrix}$$

Wednesday is two steps later:

$$s_2 = T s_1 = \begin{pmatrix} 0.8(0.8) + 0.4(0.2) \\ 0.2(0.8) + 0.6(0.2) \end{pmatrix} = \begin{pmatrix} 0.72 \\ 0.28 \end{pmatrix}$$

The probability that it is sunny is $0.8$ on Tuesday and $0.72$ on Wednesday.

Check with a tree: sunny on Wednesday happens by S → S → S or S → R → S, with probability $0.8 \times 0.8 + 0.2 \times 0.4 = 0.72$. ✓

Example 2: Powers of the transition matrix

For the same weather model:

• (a) Find $T^3$.
• (b) It is sunny today. Find the probability that it is rainy in $3$ days’ time.
• (c) A forecaster says there’s a $50\%$ chance of sun today. Find the probability that it is sunny in $3$ days’ time.

Solution.

(a) On a GDC (or by multiplying $T^2$ by $T$):

$$T^3 = \begin{pmatrix} 0.688 & 0.624 \\ 0.312 & 0.376 \end{pmatrix}$$

(b) Start in S (column $1$) and end in R (row $2$): $(T^3)_{21} = 0.312$.

(c) $s_0 = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}$, so

$$s_3 = T^3 s_0 = \begin{pmatrix} 0.688(0.5) + 0.624(0.5) \\ 0.312(0.5) + 0.376(0.5) \end{pmatrix} = \begin{pmatrix} 0.656 \\ 0.344 \end{pmatrix}$$

The probability that it is sunny in $3$ days is $0.656$.

Example 3: The steady state

For the weather model, find the long-term proportion of sunny days

• (a) by repeated multiplication
• (b) exactly, by solving a system of equations.

Solution.

(a) All entries of $T$ are already positive, so the chain is regular. A GDC gives

$$T^{20} \approx \begin{pmatrix} 0.667 & 0.667 \\ 0.333 & 0.333 \end{pmatrix}$$

Both columns are the same, so whatever the weather today, in the long run about $0.667$ of days are sunny.

(b) Let $s = \begin{pmatrix} x \\ y \end{pmatrix}$ with $Ts = s$:

$$\begin{aligned} 0.8x + 0.4y &= x \\ 0.2x + 0.6y &= y \end{aligned}$$

Both equations simplify to $0.4y = 0.2x$, that is, $x = 2y$. (For a $2 \times 2$ transition matrix the two equations always say the same thing, which is why you need the extra condition.) Now use $x + y = 1$:

$$2y + y = 1 \quad\Rightarrow\quad y = \frac{1}{3}, \quad x = \frac{2}{3}$$ $$s = \begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}$$

In the long run, $\dfrac{2}{3}$ of days are sunny. Check: $T s = \begin{pmatrix} 0.8 \cdot \frac{2}{3} + 0.4 \cdot \frac{1}{3} \\ 0.2 \cdot \frac{2}{3} + 0.6 \cdot \frac{1}{3} \end{pmatrix} = \begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}$. ✓

Example 4: Brand switching

A town has three phone companies, A, B and C. Each year:

• A keeps $85\%$ of its customers, loses $10\%$ to B and $5\%$ to C
• B keeps $75\%$, loses $15\%$ to A and $10\%$ to C
• C keeps $80\%$, loses $10\%$ to A and $10\%$ to B.

This year, the market shares are A $40\%$, B $35\%$, C $25\%$, and there are $20\,000$ customers in total.

• (a) Write the transition matrix.
• (b) Find the market shares in $2$ years.
• (c) Find the long-term number of customers of each company.

Solution.

(a) Each column is a “from” company (order A, B, C):

$$T = \begin{pmatrix} 0.85 & 0.15 & 0.10 \\ 0.10 & 0.75 & 0.10 \\ 0.05 & 0.10 & 0.80 \end{pmatrix}$$

Check: each column adds to $1$.

(b) $s_0 = \begin{pmatrix} 0.40 \\ 0.35 \\ 0.25 \end{pmatrix}$, and a GDC gives

$$s_2 = T^2 s_0 = \begin{pmatrix} 0.4295 \\ 0.312875 \\ 0.257625 \end{pmatrix}$$

In $2$ years: A $43.0\%$, B $31.3\%$, C $25.8\%$ (to 3 s.f.).

(c) Every entry of $T$ is positive, so the chain is regular and has a steady state $s = \begin{pmatrix} a \\ b \\ c \end{pmatrix}$. From $Ts = s$, the first two equations are

$$\begin{aligned} 0.85a + 0.15b + 0.10c &= a &&\Rightarrow\; -0.15a + 0.15b + 0.10c = 0 \\ 0.10a + 0.75b + 0.10c &= b &&\Rightarrow\; 0.10a - 0.25b + 0.10c = 0 \end{aligned}$$

Replace the third with $a + b + c = 1$ and solve the system on a GDC:

$$a = \frac{16}{35} \approx 0.457, \qquad b = \frac{2}{7} \approx 0.286, \qquad c = \frac{9}{35} \approx 0.257$$

(Repeated multiplication agrees: every column of $T^{50}$ is $0.457, 0.286, 0.257$ to 3 s.f.)

Long-term customers, using the exact fractions:

$$\text{A: } \frac{16}{35} \times 20\,000 \approx 9143, \qquad \text{B: } \frac{2}{7} \times 20\,000 \approx 5714, \qquad \text{C: } \frac{9}{35} \times 20\,000 \approx 5143$$

(to the nearest customer; check: $9143 + 5714 + 5143 = 20\,000$).

Common mistakes

Putting the probabilities in rows instead of columns. In the IB convention, $T_{ij}$ is the probability of going from $j$ to $i$, so each column adds to $1$. If your rows add to $1$ and your columns don’t, you’ve built the transpose.

Multiplying in the wrong order. It’s $s_{n} = T^n s_0$, with the state matrix on the right. $s_0 T$ isn’t even defined for a column vector $s_0$.

Computing T to the power n incorrectly. $T^3$ means $T \times T \times T$ as matrices, not cubing each entry. Use your GDC’s matrix power.

Forgetting the “adds to 1” equation. The equations from $Ts = s$ alone always have infinitely many solutions (any multiple of $s$ works). You need $x + y = 1$ (or $a + b + c = 1$) to pin down the steady state.

Assuming every chain has a steady state that ignores the start. That’s guaranteed for regular chains. Check that some power of $T$ has all entries positive.

Giving long-term numbers as unrounded decimals. If the state matrix counts people or objects, round the final answers sensibly (like $9143$ customers) and check that they add to the total.

Practice

1. (Warm-up) Using the IB column convention, which of these could be transition matrices? Explain.

$$A = \begin{pmatrix} 0.3 & 0.6 \\ 0.7 & 0.4 \end{pmatrix}, \quad B = \begin{pmatrix} 0.5 & 0.5 \\ 0.4 & 0.6 \end{pmatrix}, \quad C = \begin{pmatrix} 1.2 & 0 \\ -0.2 & 1 \end{pmatrix}$$

Solution

$A$: yes. All entries are between $0$ and $1$, and each column adds to $1$ ($0.3 + 0.7 = 1$, $0.6 + 0.4 = 1$).

$B$: no. Its columns add to $0.9$ and $1.1$. (Its rows add to $1$, so it would be a transition matrix in the other, row convention; its transpose is a valid IB transition matrix.)

$C$: no. Entries are probabilities, so they can’t be negative or greater than $1$.

2. (Warm-up) If Ana goes to the gym one day, the probability that she goes the next day is $0.7$. If she doesn’t go one day, the probability that she goes the next day is $0.4$. Today there’s a $50\%$ chance she goes.

• (a) Write the transition matrix, with states in the order “gym”, “no gym”.
• (b) Find the probability that she goes to the gym tomorrow.

Solution

(a)

$$T = \begin{pmatrix} 0.7 & 0.4 \\ 0.3 & 0.6 \end{pmatrix}$$

(b)

$$s_1 = \begin{pmatrix} 0.7 & 0.4 \\ 0.3 & 0.6 \end{pmatrix}\begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.35 + 0.2 \\ 0.15 + 0.3 \end{pmatrix} = \begin{pmatrix} 0.55 \\ 0.45 \end{pmatrix}$$

The probability is $0.55$.

3. (Core) A student travels to school by bus (B), bicycle (C) or car (D). Each day:

• after taking the bus, she takes the bus again with probability $0.6$, cycles with probability $0.1$, and goes by car with probability $0.3$
• after cycling, she takes the bus with probability $0.2$, cycles with probability $0.7$, and goes by car with probability $0.1$
• after going by car, she takes the bus with probability $0.3$, cycles with probability $0.1$, and goes by car with probability $0.6$.

She cycled today. Find the probability of each way of travelling in $2$ days’ time.

Solution

With states in the order B, C, D:

$$T = \begin{pmatrix} 0.6 & 0.2 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.3 & 0.1 & 0.6 \end{pmatrix}, \qquad s_0 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$$

$s_1 = T s_0$ is the second column of $T$: $\begin{pmatrix} 0.2 \\ 0.7 \\ 0.1 \end{pmatrix}$. Then

$$s_2 = T s_1 = \begin{pmatrix} 0.6(0.2) + 0.2(0.7) + 0.3(0.1) \\ 0.1(0.2) + 0.7(0.7) + 0.1(0.1) \\ 0.3(0.2) + 0.1(0.7) + 0.6(0.1) \end{pmatrix} = \begin{pmatrix} 0.29 \\ 0.52 \\ 0.19 \end{pmatrix}$$

Bus $0.29$, bicycle $0.52$, car $0.19$. (Check: $0.29 + 0.52 + 0.19 = 1$.)

4. (Core) For the weather model $T = \begin{pmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{pmatrix}$ (order sunny, rainy), it is rainy today. Find the probability that it is sunny in $5$ days’ time.

Solution

On a GDC:

$$T^5 = \begin{pmatrix} 0.67008 & 0.65984 \\ 0.32992 & 0.34016 \end{pmatrix}$$

Start in R (column $2$), end in S (row $1$): $(T^5)_{12} = 0.65984 = 0.660$ (to 3 s.f.).

Notice that this is already close to the long-term value $\dfrac{2}{3}$ from Example 3.

5. (Core) A Markov chain has transition matrix $T = \begin{pmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{pmatrix}$. Find the exact steady-state matrix.

Solution

Let $s = \begin{pmatrix} x \\ y \end{pmatrix}$. From the first row of $Ts = s$:

$$0.7x + 0.2y = x \quad\Rightarrow\quad 0.2y = 0.3x \quad\Rightarrow\quad y = 1.5x$$

With $x + y = 1$: $x + 1.5x = 1$, so $x = 0.4$ and $y = 0.6$.

$$s = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix}$$

Check: $0.7(0.4) + 0.2(0.6) = 0.28 + 0.12 = 0.4$ ✓ and $0.3(0.4) + 0.8(0.6) = 0.12 + 0.48 = 0.6$ ✓.

6. (Core) A bike-share scheme has $300$ bikes at three stations, X, Y and Z. Each day, the bikes move according to

$$T = \begin{pmatrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.6 & 0.2 \\ 0.2 & 0.2 & 0.5 \end{pmatrix}$$

(order X, Y, Z; for example, $30\%$ of the bikes at X end the day at Y).

• (a) There are $100$ bikes at each station this morning. How many will be at each station tomorrow morning?
• (b) In the long run, about how many bikes will be at each station?

Solution

(a)

$$T\begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix} = \begin{pmatrix} 50 + 20 + 30 \\ 30 + 60 + 20 \\ 20 + 20 + 50 \end{pmatrix} = \begin{pmatrix} 100 \\ 110 \\ 90 \end{pmatrix}$$

X: $100$, Y: $110$, Z: $90$.

(b) Every entry of $T$ is positive, so the chain is regular. Solve $Ts = s$ with $a + b + c = 1$:

$$\begin{aligned} -0.5a + 0.2b + 0.3c &= 0 \\ 0.3a - 0.4b + 0.2c &= 0 \\ a + b + c &= 1 \end{aligned}$$

A GDC gives $a = \dfrac{16}{49}$, $b = \dfrac{19}{49}$, $c = \dfrac{2}{7}$. Multiplying by $300$: X $\approx 97.96$, Y $\approx 116.3$, Z $\approx 85.71$.

In the long run there will be about $98$ bikes at X, $116$ at Y and $86$ at Z.

7. (Core) Decide whether each transition matrix is regular. Explain.

$$A = \begin{pmatrix} 0 & 0.5 \\ 1 & 0.5 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0.3 \\ 0 & 0.7 \end{pmatrix}, \quad C = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$$

Solution

$A$: regular. $A^2 = \begin{pmatrix} 0.5 & 0.25 \\ 0.5 & 0.75 \end{pmatrix}$ has all entries positive.

$B$: not regular. Once the chain is in state $1$ it never leaves (column $1$ is $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$), so the bottom-left entry of every power $B^n$ is $0$. For example, $B^2 = \begin{pmatrix} 1 & 0.51 \\ 0 & 0.49 \end{pmatrix}$.

$C$: not regular. The chain moves around the cycle $1 \to 2 \to 3 \to 1$ with certainty. Its powers are $C^2 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$, $C^3 = I$, $C^4 = C$, and so on, and each of these has zeros.

8. (Challenge) A two-state Markov chain has transition matrix $T = \begin{pmatrix} 1 - a & 0.3 \\ a & 0.7 \end{pmatrix}$, where $0 \lt a \lt 1$. Its steady state is $\begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}$. Find $a$.

Solution

The steady state satisfies $Ts = s$. The first row gives

$$\begin{aligned} (1 - a)(0.6) + 0.3(0.4) &= 0.6 \\ 0.6 - 0.6a + 0.12 &= 0.6 \\ 0.6a &= 0.12 \\ a &= 0.2 \end{aligned}$$

Check with the second row: $0.2(0.6) + 0.7(0.4) = 0.12 + 0.28 = 0.4$. ✓

9. (Challenge) For the weather model $T = \begin{pmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{pmatrix}$:

• (a) Find the eigenvalues of $T$.
• (b) Show that $\begin{pmatrix} 2 \\ 1 \end{pmatrix}$ is an eigenvector for the eigenvalue $1$, and explain how it gives the steady state.
• (c) Use the other eigenvalue to explain why the columns of $T^n$ get close to the steady state quickly.

Solution

(a) Solve $\det(T - \lambda I) = 0$:

$$\begin{aligned} (0.8 - \lambda)(0.6 - \lambda) - (0.4)(0.2) &= 0 \\ \lambda^2 - 1.4\lambda + 0.48 - 0.08 &= 0 \\ \lambda^2 - 1.4\lambda + 0.4 &= 0 \\ (\lambda - 1)(\lambda - 0.4) &= 0 \end{aligned}$$

So $\lambda = 1$ or $\lambda = 0.4$.

(b)

$$T\begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 1.6 + 0.4 \\ 0.4 + 0.6 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \end{pmatrix} = 1 \begin{pmatrix} 2 \\ 1 \end{pmatrix}$$

so it is an eigenvector with eigenvalue $1$. Any multiple of it satisfies $Ts = s$; scaling so the entries add to $1$ (divide by $2 + 1 = 3$) gives the steady state $\begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}$, as in Example 3.

(c) Any initial state can be written as the steady state plus a multiple of the eigenvector for $\lambda = 0.4$. Each step multiplies that second part by $0.4$, so after $n$ steps it has been multiplied by $0.4^n$, which shrinks to $0$ fast (for example, $0.4^5 \approx 0.01$). What’s left is the steady state. That’s why $T^5$ in question 4 was already within about $0.01$ of $\dfrac{2}{3}$.