The Long-Run Steady State

Watching the split settle

Each year 0.2 of the city moves to the country and 0.3 of the country moves to the city, so the transition matrix is T = (0.8 0.3; 0.2 0.7), the city first. Start with all 1000 people in the city and multiply by T year after year.

After one year the city holds 0.8 × 1000 = 800 and the country 200. Then 0.8 × 800 + 0.3 × 200 = 700, then 0.8 × 700 + 0.3 × 300 = 650, then 0.8 × 650 + 0.3 × 350 = 625. The city's numbers drop by 200, 100, 50 and 25, each drop half the one before, so they are closing in on 600.

The city is 400, 200, 100, 50 and then 25 above 600: the gap halves every year.

The same chain, with A the country and B the city: 0.3 of A moves to B and 0.2 of B moves to A each year. It opens with everyone in the city. From any start, stepping time forward ends at 40% country and 60% city. The instrument writes the shares as a row $\pi$π and the matrix as P, so $\pi P=\pi$π P = π says the same as T s = s.

A split that T leaves alone

The split has settled when another year changes nothing: T times the split gives the same split back. Write the settled split as a column s. Then T s = s, which is the eigenvector equation $Av=\lambda v$A v = λ v with $\lambda =1$λ = 1. The long-run split is an eigenvector of T with eigenvalue 1.

Every transition matrix has 1 as an eigenvalue. Each column of T adds to 1, so each column of T − I adds to 0, and then the bottom row of T − I is minus the sum of the rows above it. So the determinant of T − I is 0, and 1 is an eigenvalue. Here T − I has rows (−0.2, 0.3) and (0.2, −0.3), and the second is minus the first.

Solving (T − I) s = 0

T s = s rearranges to T s − s = 0, that is (T − I) s = 0, exactly as for any other eigenvector. Take 1 off each entry of the main diagonal of T: 0.8 − 1 = −0.2 and 0.7 − 1 = −0.3.

With s = (x, y), the first row says −0.2x + 0.3y = 0, so 0.2x = 0.3y, which is 2x = 3y. The second row says 0.2x − 0.3y = 0, the same condition. So x : y = 3 : 2: in the long run there are 3 people in the city for every 2 in the country.

Subtracting I takes 1 off the two diagonal entries of T. The second row of T − I is minus the first, so both rows give 2x = 3y.

Scaling to the whole

An eigenvector fixes only a direction, so (3, 2), (6, 4) and (0.6, 0.4) all satisfy 2x = 3y. The steady state is the one whose entries add to the whole. For 1000 people, split 1000 in the ratio 3 : 2: there are 5 parts of 200, so the city gets 3 × 200 = 600 and the country 2 × 200 = 400. As shares that add to 1, the steady state is (0.6, 0.4).

Check it with T: the city gets 0.8 × 600 + 0.3 × 400 = 480 + 120 = 600, and the country gets 0.2 × 600 + 0.7 × 400 = 120 + 280 = 400. Nothing changes.

People still move every year, but the flows balance: 0.2 × 600 = 120 leave the city and 0.3 × 400 = 120 arrive from the country.

T times the steady state 600, 400 gives 600, 400 again.

Why every start ends there

T has a second eigenvalue, 0.5, with eigenvector (1, −1): T sends (1, −1) to (0.8 − 0.3, 0.2 − 0.7) = (0.5, −0.5). Any start is the steady state plus some multiple of (1, −1). Starting from everyone in the city, (1000, 0) = (600, 400) + 400(1, −1).

Each year leaves the steady part alone and halves the other part, so after n years the city holds $600+400\times 0.5^n$600 + 400 × 0.5ⁿ: 800, 700, 650, 625, exactly the table. As n grows, $0.5^n$0.5ⁿ shrinks toward 0, and the split ends at 600 and 400 whatever the start was.

This is what a regular chain guarantees: one steady state, and every other eigenvalue smaller than 1 in size, so every start settles there. Two kinds of chain behave differently. With a trap state, the steady state puts everyone in the trap. With two states that swap every step, T = (0 1; 1 0) leaves (0.5, 0.5) unchanged, but a start of (1, 0) goes to (0, 1) and back forever and never settles; its second eigenvalue is −1, which does not shrink.

PageRank

A search engine can rank web pages with a steady state. A reader on a page clicks one of its links at random, so a page with two links sends 0.5 along each. Take three pages: A links only to B, B links only to C, and C links to A and to B. With s = (a, b, c), T s = s gives a = 0.5c, then b = a + 0.5c, and c = b.

So c = b and a = 0.5c, and with a + b + c = 1, 0.5c + c + c = 1 gives c = 0.4. The steady state is (0.2, 0.4, 0.4): in the long run the reader is on B or C 0.4 of the time each and on A only 0.2 of the time, so B and C rank above A. Check the first row: 0.5 × 0.4 = 0.2. The full method also lets the reader jump to a random page now and then, which makes the chain regular.

Each arrow is a link, carrying the chance a reader follows it. A and B each have one link, which carries 1; C has two, which carry 0.5 each.

The usual mistakes

Solving T s = 0 instead of T s = s. T s = 0 asks for a split that becomes nobody at all, but T keeps the total: the entries of T s add to the same total as the entries of s. The steady state is what T leaves unchanged.

Stopping at the ratio. 2x = 3y gives a direction; the steady state also needs the entries to add to the whole, 600 and 400 out of 1000.

Swapping the ratio. 2x = 3y means x : y = 3 : 2, so the city, x, gets the larger share.

Reading the long run from one year, or from a column of T. After one year the city holds 800, which is still moving; only the steady state is left unchanged by T.

A machine, car-hire depots and three web pages

In the applications below, the steady state of a machine that works or breaks down gives the share of working days in a year. Then a car-hire firm's steady state across three depots, scaled to 120 cars, gives the parking spaces each depot needs. And the steady state of three linked pages ranks them by where a reader's clicks land.