Transition Matrices and Markov Chains

Stage 13 of 23 Strand 5 of 5 3 lessons

3 illustrated lessons, each teaching the why before the how.

Jump to a lesson

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’s people move to the country and 0.3 of the country’s move to the city.

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 to get next year’s: 550 and 450.

Two years later is T applied twice: T² times the start gives 575 and 425.

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

Now you

80 percent of the city stays. What goes under it in column 1?

In a transition matrix, which group of entries adds to 1?

The same matrix, drawn as labeled arrows.

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

C is the city and K the country. 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² does.

A state whose only arrow is a loop keeps everyone who arrives, so no power of T is all positive: the chain is not regular.

Now you

Two arrows leave P for other states, carrying 0.6 and 0.3. What must P’s loop carry?

When is a Markov chain called regular?

The split that stops moving, and PageRank.

The long-run split is the eigenvector for λ = 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 λ = 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.

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

PageRank is this vector for the matrix of links between web pages: the long-run share of visits to each page.

Now you

Split 600 in the steady ratio 2 : 1. How many are in the city?

Which equation does the long-run split satisfy?