Transition Matrices and Markov Chains

Transition Matrices #

Each column is where one group goes next.

A transition matrix holds the share moving from each state to each other, so its columns add to 1

Each year, 0.2 of the city moves out and 0.3 of the country moves in.

Take the labels away and those four numbers are a transition matrix T.

Column 1 is everyone who started in the city, so its entries have to add to 1.

Multiply T by this year’s split and the next year comes out: 550 and 450.

Two years on is T applied twice, which is $T^2$T² on the start: 575 and 425.

After n years the split is $T^n$Tⁿ times the start, and diagonalizing makes $T^n$Tⁿ easy to find.

Transition Diagrams #

The same matrix, drawn as labeled arrows.

A transition diagram is the same information as T, with one labeled arrow for each entry

Each arrow carries the share moving that way, and a loop carries the share that stays.

Row 1 collects the arrows arriving in the city: 0.8 stays, 0.3 comes from the country.

Everything leaving one state adds to 1: 0.8 + 0.2. That total is a column of T.

A chain is regular when some power of T has every entry positive — here $T^2$T² does.

A state whose only arrow loops back traps everyone, so no power of T can leave it: not regular.

The Long-Run Steady State #

The split that stops moving, and PageRank.

The long-run split is the eigenvector for $\lambda =1$λ = 1, scaled so its entries add to the whole

Start everyone in the city and the split settles: 800, 700, 650, 625.

A settled split is one T leaves alone, so it is an eigenvector with $\lambda =1$λ = 1.

So subtract I and solve (T − I) s = 0, exactly as for any other eigenvector.

Both rows give 2x = 3y, so the settled split is always 3 city to 2 country.

Share 1000 people in that ratio and T returns 600 and 400, unchanged.

PageRank is this vector for a page link matrix: where a wandering reader ends up.