Markov matrices: eigenvalue 1 and steady states

Each year, people move between three towns by fixed shares. Watch the populations settle, then try any other start.

The steady state

Each year people move between three towns by fixed shares.

Year 0: the shares start at (1, 0, 0). The dotted lines mark the steady state, (0.45, 0.35, 0.2).

year

(1, 0, 0)

Describe this picture

Two panels. On the left, small grey bars for the starting shares of towns 1, 2 and 3. On the right, a large bar for each town’s share of all the people, with a dotted line at its steady share, and curved arrows between the towns whose thickness shows how many people move that way each year: solid arcs for moves to the right, dashed for moves to the left. Under each town, the share that leaves it each year and the share that arrives. Each year 80 % of town 1 stays, 10 % moves to town 2 and 10 % to town 3; town 2 keeps 70 % and sends 20 % to town 1 and 10 % to town 3; town 3 keeps 60 % and sends 10 % to town 1 and 30 % to town 2. Over 12 s everyone starts in town 1, and the bars step year by year through $(0.8,0.1,0.1)$ , $(0.67,0.18,0.15)$ , $(0.587,0.238,0.175)$ and on, settling on the dotted lines at $(0.45,0.35,0.20)$ . At the end each town still sends people out and takes people in, the two in balance. Readouts give the year and the shares. One control after the clip: drag the starting bars, or move them with the arrow keys in steps of 0.05; the other two are rescaled so the three add up to 1, and the bars land on the same steady state.

Shares that move

Write the yearly moves as a matrix. Column $q$ says where the people of town $q$ go, and entry $m_{pq}$ is the share moving from town $q$ to town $p$ :

\mathbf{M}=\begin{bmatrix}0.8&0.2&0.1\\0.1&0.7&0.3\\0.1&0.1&0.6\end{bmatrix}.

Let $\mathbf{u}_k$ hold the shares of the population in each town after $k$ years. Town $p$ next year collects $m_{pq}$ of each town $q$ , which is row $p$ of $\mathbf{M}$ times $\mathbf{u}_k$ . So one year is one matrix step, and $k$ years are a power:

\mathbf{u}_{k+1}=\mathbf{M}\mathbf{u}_k,\qquad \mathbf{u}_k=\mathbf{M}^k\mathbf{u}_0.

From $\mathbf{u}_0=(1,0,0)$ , everyone in town 1, the first steps are $(0.8,0.1,0.1)$ , then $(0.67,0.18,0.15)$ , then $(0.587,0.238,0.175)$ .

Why the columns add up to 1

Each column lists where one town’s people go, so it adds up to 1: nobody is created and nobody is lost. Then the total population never changes, because the total of $\mathbf{M}\mathbf{u}$ is

\begin{aligned} \sum_p\sum_q m_{pq}u_q&=\sum_q\Big(\sum_p m_{pq}\Big)u_q\\ &=\sum_q u_q. \end{aligned}

A Markov matrix is a square matrix with no negative entries whose columns each add up to 1. Many books write the transpose instead, with rows adding up to 1 and the vector on the left; this course keeps columns, so that $\mathbf{M}$ acts on $\mathbf{u}$ as every other matrix does.

The steady state

Where do the populations end up? At a vector that one more year leaves unchanged:

\mathbf{M}\mathbf{s}=\mathbf{s}.

That is an eigenvector with eigenvalue 1. Every Markov matrix has one. The columns of $\mathbf{M}$ add up to 1, so $\mathbf{M}^\top(1,1,1)=(1,1,1)$ : 1 is an eigenvalue of $\mathbf{M}^\top$ . And $\mathbf{M}$ and $\mathbf{M}^\top$ have the same eigenvalues, because a matrix and its transpose have the same determinant, so $\det(\mathbf{M}-\lambda\mathbf{I})=\det(\mathbf{M}^\top-\lambda\mathbf{I})$ .

To find $\mathbf{s}$ , solve $(\mathbf{M}-\mathbf{I})\,\mathbf{s}=\mathbf{0}$ as in The null space:

\mathbf{M}-\mathbf{I}=\begin{bmatrix}-0.2&0.2&0.1\\0.1&-0.3&0.3\\0.1&0.1&-0.4\end{bmatrix}.

Its null space is the line of $(9,7,4)$ ; check row 2: $0.9-2.1+1.2=0$ . Scale it to add up to 1: $\mathbf{s}=(0.45,\,0.35,\,0.20)$ .

Watch out

“Settled” does not mean nobody moves. At the steady state people still move every year, but each town gains as many as it loses. Town 1 loses $0.2\times0.45=0.09$ and gains $0.2\times0.35+0.1\times0.20=0.09$ . The arrows in the picture keep flowing; only the bars stand still.

How fast it settles

The other two eigenvalues decide the speed. The trace of $\mathbf{M}$ is 2.1 and its determinant 0.3. With one eigenvalue 1, the other two add up to 1.1 and multiply to 0.3, so they are 0.6 and 0.5. Their eigenvectors are $(1,-1,0)$ , since $\mathbf{M}(1,-1,0)=(0.6,-0.6,0)$ , and $(1,-2,1)$ , since $\mathbf{M}(1,-2,1)=(0.5,-1,0.5)$ . Their entries add up to 0: they move people around without changing the total.

Split the start along the three eigenvectors:

\begin{aligned} (1,0,0)&=\mathbf{s}+0.75\,(1,-1,0)\\ &\quad-0.2\,(1,-2,1). \end{aligned}

Then, by Diagonalisation and matrix powers, each year multiplies each piece by its eigenvalue:

\begin{aligned} \mathbf{u}_k&=\mathbf{s}\\ &\quad+0.75\,(0.6)^k\,(1,-1,0)\\ &\quad-0.2\,(0.5)^k\,(1,-2,1). \end{aligned}

The steady part stays, and the other two pieces fade. The slower one shrinks by 0.6 each year, so the distance to $\mathbf{s}$ shrinks by about that factor. After 10 years the shares are $(0.454,\,0.346,\,0.200)$ , within 0.005 of $\mathbf{s}$ .

Pieces

Each share is the steady share plus two pieces that shrink every year.

One row per town, one bar per year. Each bar is the steady share plus two pieces.

Describe this picture

Three rows of bars, one row per town, and in each row one bar for each year $k=0$ to 10, appearing from left to right. Every bar starts with a grey part as tall as the town’s steady share, $(0.45,0.35,0.20)$ , also marked by a dotted line across the row. On top of it sit two coloured pieces, $0.75\,(0.6)^k\,(1,-1,0)$ and $-0.2\,(0.5)^k\,(1,-2,1)$ , drawn upward when positive and downward when negative, and a short line marks the total. The pieces shrink from year to year until they can’t be seen and only the steady part is left. There is no control.

When it does not settle

Two things can go wrong.

It swings forever. $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ swaps two towns every year. Its eigenvalues are 1 and $-1$ , and the $-1$ piece never fades: from $(1,0)$ the population jumps to $(0,1)$ and back, forever.
It never mixes. For the identity matrix nobody moves, every vector is steady, and the end state is wherever you start.

When every entry of $\mathbf{M}$ is positive, as for the three towns, neither can happen. Then every other eigenvalue is smaller than 1 in size, and every start whose shares add to 1 ends at the same $\mathbf{s}$ . Drag the starting bars in the first picture to see it.

Worked example

1. Three towns. Trace 2.1 and determinant $0.8(0.42-0.03)-0.2(0.06-0.03)+0.1(0.01-0.07)=0.312-0.006-0.006=0.30$ , so the eigenvalues are 1, 0.6 and 0.5. Steady state $(0.45,0.35,0.20)$ . By the formula, year 3 is $(0.45+0.162-0.025,\;0.35-0.162+0.05,\;0.20-0.025)=(0.587,0.238,0.175)$ , the same as multiplying three times.

2. Two brands. Each month 90 % of brand 1’s buyers stay and 10 % switch; 80 % of brand 2’s stay and 20 % switch: $\mathbf{M}=\begin{bmatrix}0.9&0.2\\0.1&0.8\end{bmatrix}$ . The steady state is $(\tfrac23,\tfrac13)$ , the other eigenvalue is $\mathrm{tr}-1=0.7$ , and from $(1,0)$

\mathbf{u}_k=\big(\tfrac23,\tfrac13\big)+\tfrac13\,(0.7)^k\,(1,-1).

For $k=1$ this gives $(0.9,0.1)$ , as one step should.

3. A swap. $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ has eigenvalues 1 and $-1$ , and $(1,0)$ alternates forever.

Try these before you read the answers.

In this course, do the columns or the rows of a Markov matrix add up to 1? The columns.
Is 1 always an eigenvalue of a Markov matrix? Yes: $(1,\dots,1)$ is an eigenvector of its transpose.
The eigenvalues are 1, 0.6 and 0.5. By what factor does the distance to the steady state shrink each step? About 0.6.
Start everyone in town 3 instead. Does the end state change? No: it is still $(0.45,0.35,0.20)$ .

Where you’ll meet this

Market shares and populations. Any model where fixed shares move between a few states each period, such as customers between brands or animals between habitats, is a Markov matrix, and its steady state is the long-run split.

Ranking web pages. One way to rank pages imagines a reader clicking links at random. The chance of being on each page is a vector, one click is a huge Markov matrix, and the steady state is the ranking. It is found by multiplying by the matrix again and again until the vector stops changing.

Where this leads · Markov chains

Markov chains, in the probability and statistics course, reads the same matrices as chances: the weather tomorrow given the weather today. It uses the same column convention, and its $n$ -step chances are the matrix powers of this page.

Reference card

Quantity	Formula	Notes
Markov matrix	$m_{pq}\ge0$ , $\sum_pm_{pq}=1$	$m_{pq}$ : share from $q$ to $p$ ; columns add to 1
One step	$\mathbf{u}_{k+1}=\mathbf{M}\mathbf{u}_k$	the total stays the same
$k$ steps	$\mathbf{u}_k=\mathbf{M}^k\mathbf{u}_0$	a matrix power
Steady state	$\mathbf{M}\mathbf{s}=\mathbf{s}$ , $\sum_ps_p=1$	the eigenvector for $\lambda=1$
Always there	$\lambda=1$	$(1,\dots,1)$ is an eigenvector of $\mathbf{M}^\top$
Speed	error shrinks like $\lvert\lambda_2\rvert^k$	$\lambda_2$ : the next largest in size
Positive entries	every start reaches the same $\mathbf{s}$	the other eigenvalues are smaller than 1 in size

Markov matrices

The steady state

Shares that move

Why the columns add up to 1

The steady state

How fast it settles

Pieces

When it does not settle

Worked example

Where you’ll meet this

Reference card

Keep reading with a free account.

Are you 13 or over?

Where to go next.

Account

Subjects

Site

Look

Markov matrices

First, the picture

Shares that move

Why the columns add up to 1

The steady state

How fast it settles

When it does not settle

Worked example

Where you’ll meet this

Reference card