5.11.2 Markov chains

In this lesson

Markov chains: states, the Markov property, and a transition matrix whose rows add up to 1
Probabilities $k$ steps ahead from the matrix power $P^k$ , and the distribution after $k$ steps as a row vector times $P^k$
The stationary distribution $\boldsymbol{\pi}P = \boldsymbol{\pi}$ : by linear equations, and as the eigenvector of $P^\top$ with eigenvalue 1
How fast a chain settles, from its second eigenvalue, and when it never settles: a chain that swings, and one with two ends
Absorbing states: the expected time until absorption, and which absorbing state is reached

You need conditional and total probability from lesson 5.1.3 and the rating table of case study 5.1.6. You also need eigenvectors from lesson 3.6.1 and matrix powers from lesson 3.6.2. The random walks of lesson 5.11.1 come back as examples.

States and a transition matrix

A Markov chain is a process $X_0, X_1, X_2, \ldots$ that moves between a list of states. The chance of each next state depends only on the state now, not on how the chain got there. That is the Markov property, and the same chances apply at every step.

Take tomorrow's weather as sunny, cloudy or rainy, with these chances given today's:

today, tomorrow	sunny	cloudy	rainy
sunny	0.7	0.2	0.1
cloudy	0.3	0.4	0.3
rainy	0.2	0.3	0.5

The numbers are invented. Each entry is a conditional probability (lesson 5.1.3). The table is laid out like case study 5.1.6's rating table: rows are the state now, columns the state one step later.

Rule: Transition matrix

\begin{gathered} p_{ij} = P(X_{n+1} = j \mid X_n = i) \\[4pt] p_{ij} \ge 0, \quad \textstyle\sum_j p_{ij} = 1 \end{gathered}

$P$ has one row and one column per state. Tomorrow's state is one of the states, so each row adds up to 1. The columns need not.

The weather chain as a diagram. Each arrow is a move with its chance, written near the state it leaves. The arrows leaving a state, its loop included, add up to 1.

The random walk of lesson 5.11.1 is a Markov chain too. Its states are the whole numbers, and from $k$ it moves to $k + 1$ or $k - 1$ , whatever its path so far.

Two steps ahead

To go from sunny to rainy in two days, the chain passes through some state tomorrow. The law of total probability (lesson 5.1.3) adds over the three:

0.7 \times 0.1 + 0.2 \times 0.3 + 0.1 \times 0.5 = 0.18

That is row sunny of $P$ dotted with column rainy: entry (sunny, rainy) of $P^2$ . Case study 5.1.6 found two-year default chances the same way, and $k$ steps work like $k$ years there.

Rule: k steps ahead

P(X_{n+k} = j \mid X_n = i) = (P^k)_{ij}

Entry $(i, j)$ of the matrix power $P^k$ (lesson 3.6.2). The rows of $P^k$ add up to 1 as well.

Try it The first line checks the table: entries at least 0, rows adding up to 1. P[0] @ P[:, 2] is the two-day sum above, and P @ P gives every two-day chance at once. Its first row ends in 0.18.

import numpy as np P = np.array([ [0.7, 0.2, 0.1], # sunny today [0.3, 0.4, 0.3], # cloudy today [0.2, 0.3, 0.5], # rainy today ]) print(np.allclose(P.sum(axis=1), 1), (P >= 0).all()) print(round(P[0] @ P[:, 2], 4)) print(np.round(P @ P, 4))

⌘/Ctrl + Enter runs the cell

The distribution after $k$ steps

Often the state now is itself uncertain. Write its chances as a row vector $\mathbf{s}_0$ , such as $(1, 0, 0)$ for "sunny today". By total probability, tomorrow's chances are $\mathbf{s}_1 = \mathbf{s}_0P$ , as for case study 5.1.6's loan book.

Rule: Distribution after k steps

\begin{gathered} \mathbf{s}_{k + 1} = \mathbf{s}_k P \\[4pt] \mathbf{s}_k = \mathbf{s}_0 P^k \end{gathered}

$\mathbf{s}_k$ is a row vector: entry $j$ is $P(X_k = j)$ , and the entries add up to 1. It multiplies $P$ from the left.

From a sunny day and from a rainy one:

days $k$	$\mathbf{s}_k$ from sunny	$\mathbf{s}_k$ from rainy
1	$(0.7, 0.2, 0.1)$	$(0.2, 0.3, 0.5)$
2	$(0.57, 0.25, 0.18)$	$(0.33, 0.31, 0.36)$
3	$(0.51, 0.268, 0.222)$	$(0.396, 0.298, 0.306)$
5	$(0.4685, 0.2794, 0.2521)$	$(0.4429, 0.2862, 0.2708)$
10	$(0.4568, 0.2825, 0.2607)$	$(0.4562, 0.2827, 0.2611)$
20	$(0.4565, 0.2826, 0.2609)$	$(0.4565, 0.2826, 0.2609)$

After a few weeks the start is forgotten: both columns reach $(0.4565, 0.2826, 0.2609)$ . Those are also the long-run shares of days. In one seeded run of 50,000 days, 46.06% are sunny, 28.21% cloudy and 25.73% rainy. That is a law of large numbers for chains, like lesson 5.7.2's for independent draws.

\mathbf{s}_0P^k

import numpy as np P = np.array([[0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]]) for start in ([1, 0, 0], [0, 0, 1]): s0 = np.array(start, dtype=float) for k in [1, 2, 3, 5, 10, 20]: print(k, np.round(s0 @ np.linalg.matrix_power(P, k), 4)) rng = np.random.default_rng(5124) running = np.cumsum(P, axis=1) state, days = 0, np.zeros(3) for u in rng.random(50_000): state = int((u > running[state]).sum()) days[state] += 1 print(np.round(days / days.sum(), 4))

⌘/Ctrl + Enter runs the cell

The stationary distribution

A distribution that one more step leaves unchanged is stationary. Started there, the chain stays there: every $\mathbf{s}_k$ is the same.

Rule: Stationary distribution

\begin{gathered} \boldsymbol{\pi} P = \boldsymbol{\pi} \\[4pt] \pi_j \ge 0, \quad \textstyle\sum_j \pi_j = 1 \end{gathered}

$\boldsymbol{\pi}$ is a row vector of probabilities that the step $P$ maps to itself. For the weather chain it is the vector both starts settled on.

By linear equations

Write $\pi_S$ , $\pi_C$ and $\pi_R$ for the stationary chances of sunny, cloudy and rainy. Then $\boldsymbol{\pi}P = \boldsymbol{\pi}$ says that each state's chance tomorrow, added up over where it comes from, equals its chance today:

\begin{aligned} \pi_S &= 0.7\pi_S + 0.3\pi_C + 0.2\pi_R \\ \pi_C &= 0.2\pi_S + 0.4\pi_C + 0.3\pi_R \\ \pi_R &= 0.1\pi_S + 0.3\pi_C + 0.5\pi_R \end{aligned}

The three equations add up to $\pi_S + \pi_C + \pi_R = \pi_S + \pi_C + \pi_R$ , because the rows of $P$ add up to 1. So one of them is redundant: replace it by $\pi_S + \pi_C + \pi_R = 1$ . Elimination (lesson 3.3.1) gives $\boldsymbol{\pi} = \left(\frac{21}{46}, \frac{13}{46}, \frac{6}{23}\right) = (0.4565, 0.2826, 0.2609)$ .

As an eigenvector

Transpose both sides: $P^\top\boldsymbol{\pi}^\top = \boldsymbol{\pi}^\top$ . So the column $\boldsymbol{\pi}^\top$ is an eigenvector of $P^\top$ with eigenvalue 1 (lesson 3.6.1), scaled so its entries add up to 1.

Rule: Stationary distribution as an eigenvector

\begin{gathered} P^\top \boldsymbol{\pi}^\top = 1 \cdot \boldsymbol{\pi}^\top \\[4pt] \text{scale to } \textstyle\sum_j \pi_j = 1 \end{gathered}

Every transition matrix has the eigenvalue 1, because its rows add up to 1: $P\mathbf{1} = \mathbf{1}$ . $P^\top$ has the same eigenvalues as $P$ . No eigenvalue is larger than 1 in size.

The weather chain's eigenvalues are 1, 0.4732 and 0.1268. As in lesson 3.6.2, the largest one takes over and the rest dies away. The distance from $\boldsymbol{\pi}$ shrinks by the factor 0.4732 a day in the long run, which is why three weeks were plenty.

(P^\top - I)\boldsymbol{\pi}^\top = \mathbf{0}

import numpy as np P = np.array([[0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]]) A = P.T - np.eye(3) A[-1] = 1 # the last equation becomes pi_S + pi_C + pi_R = 1 pi = np.linalg.solve(A, np.array([0.0, 0.0, 1.0])) print(np.round(pi, 4), np.round(pi * 46, 4)) print(np.round(pi @ P, 4)) values, V = np.linalg.eig(P.T) order = np.argsort(values.real)[::-1] values, V = values.real[order], V.real[:, order] print(np.round(values, 4), np.round(V[:, 0] / V[:, 0].sum(), 4)) values_P, V_P = np.linalg.eig(P) right = V_P.real[:, np.argmax(values_P.real)] print(np.round(right / right[0], 4))

⌘/Ctrl + Enter runs the cell

The two towns as a Markov chain

Lesson 3.6.2 followed the shares of people in two towns. Each year 10% of town A moves to B, and 20% of town B moves to A. Read those shares as probabilities for one person, and $M$ becomes a Markov chain.

Lesson 3.6.2's $M$ had its columns adding up to 1. A transition matrix has rows adding up to 1, so here $P = M^\top$ :

P = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}

The eigenvector of $\lambda = 1$ that lesson 3.6.2 found, $\left(\frac{2}{3}, \frac{1}{3}\right)$ , is the chain's stationary distribution: its long-run distribution. A person living in A today is still there, or back there, in 10 years with probability $\frac{2}{3} + \frac{1}{3}(0.7)^{10} = 0.6761$ . The other eigenvalue, 0.7, sets the speed, as there.

Rule: Two states

\begin{gathered} P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix} \\[4pt] \boldsymbol{\pi} = \left(\frac{b}{a + b},\ \frac{a}{a + b}\right) \\[4pt] \lambda_2 = 1 - a - b \end{gathered}

$a$ is the chance of leaving state 1 and $b$ of leaving state 2, with $a + b > 0$ . The long run favours the state that is harder to leave. The gap to $\boldsymbol{\pi}$ is multiplied by $\lambda_2$ at each step.

a = 0.1

import numpy as np P = np.array([[0.9, 0.1], [0.2, 0.8]]) a, b = P[0, 1], P[1, 0] print(round(b / (a + b), 4), round(a / (a + b), 4), round(1 - a - b, 4)) print(np.round(np.array([0.5, 0.5]) @ np.linalg.matrix_power(P, 10), 4)) print(np.round(np.array([1.0, 0.0]) @ np.linalg.matrix_power(P, 10), 4), round(2 / 3 + 0.7**10 / 3, 4)) M = np.array([[0.9, 0.2], [0.1, 0.8]]) print(np.array_equal(P, M.T))

⌘/Ctrl + Enter runs the cell

When the long run does not settle

A stationary distribution always exists for a chain with finitely many states, but the chain need not settle on it. Two cases break the weather chain's behaviour.

A chain that swings. $F = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ moves to the other state every step. $\left(\frac{1}{2}, \frac{1}{2}\right)$ is stationary, but from state 1 the distribution goes $(0, 1)$ , $(1, 0)$ , $(0, 1)$ , … for ever. Its eigenvalues are 1 and $-1$ : the second has size 1 and never dies away.
A chain with two ends. The walk of lesson 5.11.1 between 0 and 4 stops at either end. From 1 it ends at 0 with probability 0.75 and at 4 with 0.25; from 3 the other way round. Every $(1 - w, 0, 0, 0, w)$ is stationary, so the long run depends on the start.

Rule: When a chain settles

\begin{gathered} \text{some } P^k \text{ has every entry} > 0 \\[4pt] \Rightarrow\ \mathbf{s}_k \to \boldsymbol{\pi} \text{ from every start} \end{gathered}

Such a chain is called regular, and its $\boldsymbol{\pi}$ is unique (stated here, not proved). The weather chain is regular with $k = 1$ . Neither the swinging chain nor the chain with two ends is.

\left(\frac{1}{2}, \frac{1}{2}\right)F

import numpy as np F = np.array([[0.0, 1.0], [1.0, 0.0]]) s = np.array([1.0, 0.0]) for k in range(1, 5): s = s @ F print(k, s) print(np.array([0.5, 0.5]) @ F, np.round(np.sort(np.linalg.eigvals(F).real), 4)) G = np.zeros((5, 5)) G[0, 0] = G[4, 4] = 1 # the walk stops at 0 and at 4 for i in range(1, 4): G[i, i - 1] = G[i, i + 1] = 0.5 print(np.round(np.linalg.matrix_power(G, 60), 4)) for w in [0.0, 0.3, 1.0]: pi = np.array([1 - w, 0, 0, 0, w]) print(w, np.allclose(pi @ G, pi))

⌘/Ctrl + Enter runs the cell

Absorbing states

A state that the chain never leaves, with $p_{ii} = 1$ , is absorbing. Default in case study 5.1.6's rating table is one. There, after 100 years, column D of $P^{100}$ was above 0.95 for every rating.

The long run is therefore dull: the only stationary distribution is $(0, 0, 0, 1)$ , everyone in default. The useful questions are how long absorption takes and, when there are several absorbing states, which one comes first.

How long until absorption

Let $Q$ hold the moves among the states that are not absorbing: for the rating table, the top-left $3 \times 3$ block, A, B and C. Let $t_i$ be the expected number of steps to absorption from state $i$ .

Condition on the first step, as in lesson 5.11.1's gambler's ruin. One step is taken, and then the chain is in state $j$ with chance $q_{ij}$ , an entry of $Q$ , or absorbed:

\begin{gathered} t_i = 1 + \textstyle\sum_j q_{ij}\,t_j \\[4pt] (I - Q)\,\mathbf{t} = \mathbf{1} \end{gathered}

Rule: Time to absorption

\mathbf{t} = (I - Q)^{-1}\,\mathbf{1}

$Q$ holds the moves among the non-absorbing states and $\mathbf{1}$ is a column of ones. Entry $(i, j)$ of $(I - Q)^{-1}$ , the fundamental matrix, is the expected number of visits to $j$ from $i$ ; its row sums are the times $t_i$ .

For the rating table, the expected time to default is 36.80 years from A, 29.71 from B and 20.21 from C. In 20,000 seeded B borrowers it was 29.36, and the last one defaulted in year 266.

The rate in the long run

Case study 5.1.6 found the chance of default in each year, given none before: rising for A and B, falling for C. In the long run all three settle on one rate. The survivors' mix of ratings settles, and from then on survival falls by the same factor each year: the largest eigenvalue of $Q$ , $\lambda_1 = 0.9666$ .

Default in year $k$ for borrowers still standing, by starting rating. Whatever the start, the rate settles on $1 - \lambda_1 = 3.34\%$ , set by the largest eigenvalue of the block $Q$ .

\mathbf{t}

import numpy as np P = np.array([[0.90, 0.08, 0.015, 0.005], [0.05, 0.85, 0.08, 0.02], [0.01, 0.09, 0.80, 0.10], [0.00, 0.00, 0.00, 1.00]]) Q = P[:3, :3] # moves among A, B and C print(np.round(np.linalg.solve(np.eye(3) - Q, np.ones(3)), 2)) lam1 = np.max(np.linalg.eigvals(Q).real) print(round(lam1, 4), round(1 - lam1, 4)) cum = np.array([np.linalg.matrix_power(P, k)[:3, 3] for k in range(51)]) print(np.round((cum[50] - cum[49]) / (1 - cum[49]), 4)) print(np.round(np.linalg.matrix_power(P, 100)[:3, 3], 4)) rng = np.random.default_rng(5125) running = np.cumsum(P, axis=1) rating = np.full(20_000, 1) default_year = np.zeros(20_000) year = 0 while (rating != 3).any(): year += 1 rating = (rng.random(20_000)[:, None] > running[rating]).sum(axis=1) default_year[(rating == 3) & (default_year == 0)] = year print(round(default_year.mean(), 2), year)

⌘/Ctrl + Enter runs the cell

Which absorbing state

With two absorbing states, let $h_i$ be the chance of ending in the chosen one, say the top, from state $i$ . The first step gives $h_i = u_i + \sum_j q_{ij}h_j$ , where $u_i$ is the chance of moving straight into the top.

Rule: Chance of each end

\mathbf{h} = (I - Q)^{-1}\,\mathbf{u}

$\mathbf{u}$ holds the one-step chances of entering the chosen absorbing state from each non-absorbing state. It is lesson 5.11.1's first-step analysis, written with matrices.

For the walk between 0 and 4, $Q$ is the middle $3 \times 3$ block of G, and only state 3 can step straight to 4: $\mathbf{u} = (0, 0, 0.5)$ . Then $\mathbf{h} = (0.25, 0.5, 0.75)$ and $\mathbf{t} = (3, 4, 3)$ : lesson 5.11.1's $\frac{a}{b}$ and $a(b - a)$ with $b = 4$ .

Try it The chances of ending at 4 and the expected number of steps, from 1, 2 and 3, then the fundamental matrix. Its rows add up to 3, 4 and 3.

import numpy as np G = np.zeros((5, 5)) G[0, 0] = G[4, 4] = 1 for i in range(1, 4): G[i, i - 1] = G[i, i + 1] = 0.5 Q = G[1:4, 1:4] # moves among 1, 2 and 3 u = G[1:4, 4] # one step straight to 4 print(np.round(np.linalg.solve(np.eye(3) - Q, u), 4)) print(np.round(np.linalg.solve(np.eye(3) - Q, np.ones(3)), 4)) print(np.round(np.linalg.inv(np.eye(3) - Q), 4))

⌘/Ctrl + Enter runs the cell

Case study 5.11.4 prices options on a binomial tree, where the stock price itself moves as a Markov chain from node to node.

Common mistakes

Rows, then a row vector on the left. With rows adding up to 1, the next distribution is $\mathbf{s}P$ , not $P\mathbf{s}$ . Lesson 3.6.2's layout is the transpose: check which way a table adds up.
A matrix power is not a power of each entry. $P^k$ is matrix_power(P, k); P**k raises each entry.
The eigenvector of $P^\top$ , not of $P$ . For eigenvalue 1, $P$ itself gives $(1, 1, 1)$ : it only says the rows add up to 1.
Scale to add up to 1. An eigenvector can come out with any length and either sign; dividing by its sum fixes both.
Stationary is not always the long run. A swinging chain never settles, and with two absorbing states the end depends on the start.
The Markov property is an assumption. Real ratings show momentum (case study 5.1.6's desk notes), which a single matrix cannot capture.

Markov chains

0 of 11 correct

1.
A row of a transition matrix reads $(0.5, 0.3, p)$ . Find $p$
2.
$P = \begin{pmatrix} 0.6 & 0.4 \\ 0.1 & 0.9 \end{pmatrix}$ . Starting in state 1, find the chance of being in state 1 after 2 steps
3.
The same $P$ , with $\mathbf{s}_0 = (0.5, 0.5)$ . Find the first entry of $\mathbf{s}_1$
4.
The same $P$ : find $\pi_1$ , the stationary chance of state 1
5.
The same $P$ : by what factor does the gap to $\boldsymbol{\pi}$ shrink at each step?
6.
$\boldsymbol{\pi} = (0.5, 0.3, 0.2)$ is the stationary distribution of a regular chain. In a long run of 1,000 steps, about how many are spent in state 2?
7.
A transition matrix has eigenvalues 1, 0.6 and $-0.2$ . In the long run, by what factor does the gap to $\boldsymbol{\pi}$ shrink per step?
8.
$F = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ , starting in state 1. Find the chance of being in state 1 after 7 steps
9.
A borrower defaults with chance 0.04 each year and otherwise keeps its rating. Find the expected number of years until default
10.
A fair walk on 0, 1, 2, 3 stops at 0 and 3, so $Q = \begin{pmatrix} 0 & 0.5 \\ 0.5 & 0 \end{pmatrix}$ for states 1 and 2. Find the expected number of steps from 1
11.
The same walk: find the chance that it ends at 3, starting from 1

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

p_{ij} = P(X_{n+1} = j \mid X_n = i)

Markov chains

States and a transition matrix

Rule: Transition matrix

Two steps ahead

Rule: k steps ahead

The distribution after $k$ steps

Rule: Distribution after k steps

The stationary distribution

Rule: Stationary distribution

By linear equations

As an eigenvector

Rule: Stationary distribution as an eigenvector

The two towns as a Markov chain

Rule: Two states

When the long run does not settle

Rule: When a chain settles

Absorbing states

How long until absorption

Rule: Time to absorption

The rate in the long run

Which absorbing state

Rule: Chance of each end

Common mistakes

Markov chains

Summary card

Free further reading

States and a transition matrix

Rule: Transition matrix

Two steps ahead

Rule: k steps ahead

The distribution after kkk steps

Rule: Distribution after k steps

The stationary distribution

Rule: Stationary distribution

By linear equations

As an eigenvector

Rule: Stationary distribution as an eigenvector

The two towns as a Markov chain

Rule: Two states

When the long run does not settle

Rule: When a chain settles

Absorbing states

How long until absorption

Rule: Time to absorption

The rate in the long run

Which absorbing state

Rule: Chance of each end

Common mistakes

Summary card

Free further reading

The distribution after $k$ steps