Moves between two states
A region has two places to live, the city and the country. Each year 0.2 of the people in the city move to the country, so the other 0.8 stay. Each year 0.3 of the people in the country move to the city, so 0.7 stay. The city and the country are the two states, and these four shares are the chances of moving from each state to each state in one year.
Lay them out with one column for each starting state and one row for each state at the end of the year. The column "from city" holds 0.8 (to city) and 0.2 (to country); the column "from country" holds 0.3 (to city) and 0.7 (to country).
Each column is a starting place and each row is a place at the end of the year: 0.3 of the country moves to the city.
The transition matrix
Take the labels away and the four numbers, in the same places, form the transition matrix T = (0.8 0.3; 0.2 0.7). The order of the states must be the same for the rows and the columns: here the city comes first both times.
Column 1 follows everyone who started in the city. Each of them ends the year somewhere, either in the city or in the country, so 0.8 + 0.2 = 1. Column 2 follows everyone who started in the country, and 0.3 + 0.7 = 1. Every column of a transition matrix adds to 1, and every entry lies between 0 and 1.
The rows need not add to 1. Row 1 collects the people who end up in the city, from two different starting places, and 0.8 + 0.3 = 1.1.
The first column of T is everyone who started in the city: 0.8 stay and 0.2 move out, which adds to 1.
One year on
Write this year's split as a column, the city first: 500 in the city and 500 in the country. Multiply by T. Row 1 of T collects the people who end the year in the city: 0.8 × 500 = 400 who stayed, plus 0.3 × 500 = 150 who arrived from the country, 550 in all. Row 2 collects the country: 0.2 × 500 + 0.7 × 500 = 100 + 350 = 450.
The total is still 550 + 450 = 1000. Nobody is lost or added, because each column of T shares out one starting group completely.
The top row of T times the column 500, 500 gives the city next year: 0.8 × 500 + 0.3 × 500 = 550.
Two years on
The second year starts from 550 and 450, so multiply by T again: the city gets 0.8 × 550 + 0.3 × 450 = 440 + 135 = 575, and the country gets 0.2 × 550 + 0.7 × 450 = 110 + 315 = 425.
Two multiplications by T are one multiplication by , because T(T s) = (T T) s. Multiply T by itself: the top left entry is 0.8 × 0.8 + 0.3 × 0.2 = 0.64 + 0.06 = 0.7. That is the chance a city dweller is in the city two years later, by two routes: stay both years (0.8 × 0.8), or move out and come back (0.2 × 0.3). The other entries are 0.45, 0.3 and 0.55, so is the matrix (0.7 0.45; 0.3 0.55). Its columns still add to 1.
Check: times the column 500, 500 gives 0.7 × 500 + 0.45 × 500 = 575 and 0.3 × 500 + 0.55 × 500 = 425, the same as two single years.
T times T is the two-year transition matrix. Its top left entry, 0.7, is 0.64 for staying twice plus 0.06 for leaving and coming back.
After n years
After n years the split is times the start. Multiplying by T year after year works, but diagonalizing T gives every year at once. T has eigenvalue 1 with eigenvector (3, 2), since T sends (3, 2) to (2.4 + 0.6, 0.6 + 1.4) = (3, 2), and eigenvalue 0.5 with eigenvector (1, −1), since T sends (1, −1) to (0.8 − 0.3, 0.2 − 0.7) = (0.5, −0.5).
Write the start along these two directions: (500, 500) = 200(3, 2) − 100(1, −1). Each year leaves the first part unchanged and halves the second, so after n years the city holds and the country holds . At n = 1 that is 550 and 450, and at n = 2 it is 575 and 425. As n grows, shrinks toward 0 and the split closes in on 600 and 400.
Rows or columns
Some books write the split as a row and give each starting state a row of the matrix, so that the rows add to 1 and the row of shares multiplies the matrix from the left. The numbers are the same, transposed. Whichever way a question sets it up, the entries for one starting state add to 1.
The usual mistakes
Putting a share in the wrong place. The 0.3 that moves from the country to the city goes in the "from country" column and the "to city" row.
Expecting the rows to add to 1. A row collects arrivals from different starting states; it is each column that adds to 1.
Forgetting the arrivals. The city next year is not 0.8 × 500 = 400; the 150 who move in from the country count too.
Squaring each entry to find . The top left entry of is 0.7, not , because the route through the country adds 0.06.
Phone networks and a coffee cart
In the applications below, customers switch between three phone networks, so T is a 3 × 3 matrix whose columns each add to 1, and the customer numbers are multiplied by T once for each year. Then a coffee cart moves between the station and the park, and and give the chances two and four days ahead.
Worked example: Customers Switching Between Three Phone Networks Each Year, Followed for Two Years
Question A town's 20,000 phone customers use three networks, P, Q and R. Each year P keeps 80% of its customers and loses 10% to Q and 10% to R; Q keeps 70% and loses 20% to P and 10% to R; R keeps 80% and loses 10% to P and 10% to Q. Take the state vector as a column of the numbers of customers on P, Q and R. This year P and Q have 8000 customers each and R has 4000. (a) Write down the transition matrix T, and find the number of customers on each network next year. (b) Find the numbers in two years' time, and say which network gains the most customers over the two years.
1.T = 0.80.20.10.10.70.10.10.10.8, with the rows and columns in the order P, Q, R. The columns add up to 1: 0.8 + 0.1 + 0.1, 0.2 + 0.7 + 0.1 and 0.1 + 0.1 + 0.8.
One column of T = 0.80.20.10.10.70.10.10.10.8 for each network: where its customers are a year later. 2.(a) Next year: T800080004000 = 6400 + 1600 + 400800 + 5600 + 400800 + 800 + 3200 = 840068004800: 8400 customers on P, 6800 on Q and 4800 on R.
(a) Next year: 8400 customers on P, 6800 on Q and 4800 on R. The points are the numbers year by year. 3.Multiply by T again for two years' time: T840068004800 = 6720 + 1360 + 480840 + 4760 + 480840 + 680 + 3840 = 856060805360.
Two years on, T840068004800 = 856060805360. 4.(b) In two years' time P has 8560 customers, Q has 6080 and R has 5360. Against this year, P gains 560, Q loses 1920 and R gains 1360, so R gains the most. Check: 8560 + 6080 + 5360 = 20 000.
(b) Against this year, P gains 560, Q loses 1920 and R gains 1360: R gains the most.
Answer: (a) T = 0.80.20.10.10.70.10.10.10.8; next year 8400 on P, 6800 on Q and 4800 on R; (b) 8560, 6080 and 5360: R gains the most, 1360 customers
Common mistakes
- Adding the fractions across a row and expecting 1. A row collects the customers arriving at one network from all three, so row P adds up to 0.8 + 0.2 + 0.1 = 1.1; it is each column, the customers leaving one network, that must add up to 1.
- Finding the change in the first year and doubling it for two years. The second year starts from next year's numbers, 8400, 6800 and 4800, so Q loses 1200 customers in the first year but only 720 in the second.
More transition matrices and markov chains problems, worked step by step →
Worked example: A Coffee Cart Parked at the Station or the Park Each Day, and Why Its Long Run Does Not Depend on Where It Starts
Question A coffee cart is parked each day at the station or at the park. If it is at the station today, it is at the station tomorrow with probability 0.6 and at the park with probability 0.4. If it is at the park today, it is at the station tomorrow with probability 0.2 and at the park with probability 0.8. The state vector is a column of the chances of station and park. (a) Find T2, and the chance that a cart at the station today is at the station in two days' time. (b) Find T4 and the steady state, and explain why, in the long run, the share of days at the station does not depend on where the cart starts.
1.T = 0.60.20.40.8, in the order station, park. Its first column is where a cart at the station goes, and its second is where a cart at the park goes.
T = 0.60.20.40.8: the first column is where a cart at the station goes, the second where a cart at the park goes. 2.T2 = T × T = 0.36 + 0.080.12 + 0.160.24 + 0.320.08 + 0.64 = 0.440.280.560.72. Each column still adds up to 1.
T2 = T × T = 0.440.280.560.72: the chances two days on. 3.(a) The first column of T2 is where a cart at the station is two days later: at the station with probability 0.44.
(a) The first column of T2: a cart at the station is there again two days later with probability 0.44. 4.T4 = T2 × T2 = 0.1936 + 0.15680.1232 + 0.20160.2464 + 0.40320.1568 + 0.5184 = 0.35040.32480.64960.6752. The top entries of the two columns differ by 0.16 in T2 and by only 0.0256 in T4.
T4 = T2 × T2 = 0.35040.32480.64960.6752: the two columns are closer together. 5.For the steady state π = sp, the first row of Tπ = π gives 0.6s + 0.2p = s, so 0.2p = 0.4s and p = 2s. With s + p = 1, s = 13 and p = 23.
The gold points start at the station and the green at the park. The first row of Tπ = π gives p = 2s, so s = 13, dashed. 6.(b) Both columns of Tn close in on 1323: their top entries are 0.44 and 0.28, then 0.3504 and 0.3248, either side of 13 ≈ 0.333. Whichever column the cart starts in, in the long run it is at the station on 13 of the days.
(b) Both columns of Tn close in on 13 and 23: in the long run the cart is at the station on 13 of the days, wherever it starts.
Answer: (a) T2 = 0.440.280.560.72, and the chance is 0.44; (b) T4 = 0.35040.32480.64960.6752, and the steady state is 1323; both columns of Tn approach it, so the cart is at the station on 13 of the days whichever place it starts at
Common mistakes
- Squaring each entry of T to get T2, so that the top left entry is 0.62 = 0.36. That counts only the path station, station, station; the path station, park, station adds 0.4 × 0.2 = 0.08, and T2 must be found by multiplying the matrices.
- Reading the long-run share from one column of T4 as if it had settled. The entry 0.3504 is still moving: the gap between the columns shrinks by a factor of 0.4 each day, and only the steady state, 13, is left unchanged by T.
More transition matrices and markov chains problems, worked step by step →