Math Core

A Markov chain models a system that hops between a fixed list of states (sunny or rainy, brand A or brand B, city or suburb) with fixed probabilities for each hop. The state of the whole system after $k$ steps is $P^k$ times the starting state, and the question "what happens in the long run?" turns out to be an eigenvector question: the long-run distribution is an eigenvector of $P$ for the eigenvalue $1$ .

Probability vectors and stochastic matrices

Definition

Probability vector and stochastic matrix

A probability vector is a vector with nonnegative entries that add up to $1$ .

A stochastic matrix is a square matrix whose columns are all probability vectors.

Think of entry $p_{ij}$ of a stochastic matrix $P$ as the probability of moving to state $i$ from state $j$ in one step. Column $j$ lists where state $j$ goes, so it must add up to $1$ .

For example, suppose each year $90\%$ of city residents stay in the city and $10\%$ move to the suburbs, while $20\%$ of suburban residents move to the city and $80\%$ stay. With state 1 = city and state 2 = suburbs,

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

The chain

A Markov chain is a sequence of probability vectors $\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots$ together with a stochastic matrix $P$ such that

\mathbf{x}_{k+1} = P\mathbf{x}_k \qquad (k = 0, 1, 2, \dots).

The vector $\mathbf{x}_k$ is the state vector after $k$ steps: its entries are the fractions of the population (or the probabilities) in each state. Unrolling the recursion gives $\mathbf{x}_k = P^k\mathbf{x}_0$ . Multiplying a probability vector by a stochastic matrix always gives another probability vector, so every $\mathbf{x}_k$ is a probability vector.

Worked example: Following the chain

In the city–suburb model, everyone starts in the city: $\mathbf{x}_0 = (1, 0)$ . Find $\mathbf{x}_1$ and $\mathbf{x}_2$ .

\mathbf{x}_1 = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0.9 \\ 0.1 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}\begin{bmatrix} 0.9 \\ 0.1 \end{bmatrix} = \begin{bmatrix} 0.83 \\ 0.17 \end{bmatrix}.

After two years, $83\%$ live in the city and $17\%$ in the suburbs. Keep going and you get $\mathbf{x}_3 \approx (0.781, 0.219)$ , $\mathbf{x}_4 \approx (0.747, 0.253)$ , and the numbers settle down toward $(2/3, 1/3)$ .

Steady-state vectors

If the chain settles down to some vector $\mathbf{q}$ , then applying $P$ must leave $\mathbf{q}$ unchanged.

Definition

Steady-state vector

A steady-state vector (or equilibrium vector) for a stochastic matrix $P$ is a probability vector $\mathbf{q}$ with

P\mathbf{q} = \mathbf{q}.

In the language of this unit, $\mathbf{q}$ is an eigenvector of $P$ with eigenvalue $1$ , scaled so its entries add up to $1$ . Every stochastic matrix has $1$ as an eigenvalue: the rows of $P^T$ add up to $1$ , so $P^T(1, 1, \dots, 1) = (1, 1, \dots, 1)$ , and $P$ and $P^T$ have the same eigenvalues.

To find $\mathbf{q}$ :

Solve $(P - I)\mathbf{x} = \mathbf{0}$ and pick any nonzero solution.
Divide it by the sum of its entries.

Worked example: A 2 × 2 steady state

Find the steady-state vector of $P = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}$ .

$P - I = \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix}$ . Both rows say $x_1 = 2x_2$ , so $(2, 1)$ is a solution. Its entries add up to $3$ , so

\mathbf{q} = \begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix}.

Check: $0.9 \cdot \tfrac{2}{3} + 0.2 \cdot \tfrac{1}{3} = \tfrac{1.8 + 0.2}{3} = \tfrac{2}{3}$ . In the long run, two thirds of the population lives in the city.

Worked example: A 3 × 3 steady state

Find the steady-state vector of $P = \begin{bmatrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.8 & 0.3 \\ 0.2 & 0 & 0.4 \end{bmatrix}$ .

First check that each column adds up to $1$ : $0.5 + 0.3 + 0.2$ , $0.2 + 0.8 + 0$ , $0.3 + 0.3 + 0.4$ . Now solve $(P - I)\mathbf{x} = \mathbf{0}$ :

\begin{aligned} -0.5x_1 + 0.2x_2 + 0.3x_3 &= 0 \\ 0.3x_1 - 0.2x_2 + 0.3x_3 &= 0 \\ 0.2x_1 + 0x_2 - 0.6x_3 &= 0 \end{aligned}

The third equation gives $x_1 = 3x_3$ . Substituting into the first: $-1.5x_3 + 0.2x_2 + 0.3x_3 = 0$ , so $x_2 = 6x_3$ . (The second equation checks: $0.9x_3 - 1.2x_3 + 0.3x_3 = 0$ .) Taking $x_3 = 1$ gives $(3, 6, 1)$ , whose entries add up to $10$ :

\mathbf{q} = \begin{bmatrix} 0.3 \\ 0.6 \\ 0.1 \end{bmatrix}.

Why the chain converges

Definition

Regular stochastic matrix

A stochastic matrix $P$ is regular if some power $P^k$ has all entries strictly positive.

The matrix in the $3 \times 3$ example has a zero entry, but $P^2$ does not (its $(3, 2)$ entry is $0.2 \cdot 0.2 + 0 \cdot 0.8 + 0.4 \cdot 0 = 0.04$ ), so it is regular.

Convergence theorem

If $P$ is a regular stochastic matrix, then $P$ has a unique steady-state vector $\mathbf{q}$ , and for every starting probability vector $\mathbf{x}_0$ , the chain $\mathbf{x}_k = P^k\mathbf{x}_0$ converges to $\mathbf{q}$ .

Eigenvectors show why. For the city–suburb matrix, the trace is $1.7$ , so the eigenvalues are $1$ and $0.7$ . An eigenvector for $0.7$ is $(1, -1)$ . Write the starting vector in the eigenvector basis:

\mathbf{x}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix} + \frac{1}{3}\begin{bmatrix} 1 \\ -1 \end{bmatrix} \quad\Longrightarrow\quad \mathbf{x}_k = \begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix} + \frac{1}{3}(0.7)^k\begin{bmatrix} 1 \\ -1 \end{bmatrix}.

The eigenvalue- $1$ part never changes, and the other part shrinks by a factor of $0.7$ every step, so $\mathbf{x}_k \to \mathbf{q}$ . The graph shows the city fraction $\tfrac{2}{3} + \tfrac{1}{3}(0.7)^k$ approaching $\tfrac{2}{3}$ .

The fraction of people in the city after k years. The gap to the steady state 2/3 shrinks by the second eigenvalue, 0.7, each year.Open in grapher →

Tip

For a $2 \times 2$ stochastic matrix $\begin{bmatrix} 1 - a & b \\ a & 1 - b \end{bmatrix}$ , the eigenvalues are $1$ and $1 - a - b$ (from the trace), and the steady state is $\mathbf{q} = \dfrac{1}{a + b}\begin{bmatrix} b \\ a \end{bmatrix}$ . The closer the second eigenvalue is to $0$ , the faster the chain converges.

Common mistake

Without regularity, the chain need not settle down. For $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ , the steady state is $(0.5, 0.5)$ , but starting from $(1, 0)$ the chain jumps back and forth between $(1, 0)$ and $(0, 1)$ forever. Every power of $P$ has zeros, so $P$ is not regular. (Its other eigenvalue is $-1$ , which never shrinks.) Also remember that in this course the columns of $P$ add up to $1$ ; some books use rows instead and multiply on the other side.

Practice

Practice 1

Which matrix is stochastic?

Practice 2

Let $P = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7 \end{bmatrix}$ and $\mathbf{x}_0 = (0.5, 0.5)$ . Find $\mathbf{x}_1 = P\mathbf{x}_0$ .

Enter a point like (2, -3)

Practice 3

Find the steady-state vector of $P = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7 \end{bmatrix}$ .

Enter a point like (2, -3)

Practice 4

The matrix $P = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7 \end{bmatrix}$ has $1$ as an eigenvalue. Find its other eigenvalue.

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

In a town, if a day is sunny, the next day is sunny with probability $0.8$ . If a day is rainy, the next day is sunny with probability $0.4$ . Today is sunny. What is the probability that the day after tomorrow is sunny?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

In the weather model of the previous problem, what fraction of days are sunny in the long run?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

Find the steady-state vector of $P = \begin{bmatrix} 0.7 & 0.1 & 0.2 \\ 0.2 & 0.8 & 0.2 \\ 0.1 & 0.1 & 0.6 \end{bmatrix}$ .

Enter a point like (2, -3)

Practice 8

Which stochastic matrix is not regular?