Transition Matrices and Markov Chains · applications

Applications: Transition Matrices and Markov Chains

10 question types · Secondary 4 · each worked step by step with a figure that follows the steps

01

Tomorrow's Weather in a Seaside Town, and the Chance of Rain in Two Days

methodRead Each State's Arrows into Its Own Column of the Transition Matrix, Multiply Today's State Vector by the Matrix Once for Each Day, and Check by Adding the Chance of Every Path

A weather forecaster in a seaside town records each day as sunny or rainy. Her transition diagram shows that after a sunny day the next day is sunny with probability 0.7 and rainy with probability 0.3, and after a rainy day the next day is sunny with probability 0.4 and rainy with probability 0.6. The state vector is a column sr of the chances of sunny and rainy. Monday is sunny. (a) Write down the transition matrix T, and find the chance of rain on Tuesday. (b) Find the chance of rain on Wednesday.

sunrain0.70.30.40.6fromsunrainsun0.70.4rain0.30.6toeach column adds up to 10.7 + 0.3 = 1, 0.4 + 0.6 = 1
Each arrow carries the chance of tomorrow's weather after today's. The column for sunny holds 0.7 and 0.3, so T = 0.70.40.30.6.
The column for a sunny day holds 0.7 and 0.3, and the column for a rainy day holds 0.4 and 0.6: T = 0.70.40.30.6, with the rows and columns in the order sunny, rainy. Each column adds up to 1.
step 1 of 5

Each column of T holds the chances of where one state goes next, so each column adds up to 1. Multiplying the state vector by T moves it on by one day, and the chance of rain two days on is the sum of the chances of the two paths that end in rain.

  1. The column for a sunny day holds 0.7 and 0.3, and the column for a rainy day holds 0.4 and 0.6: T = 0.70.40.30.6, with the rows and columns in the order sunny, rainy. Each column adds up to 1.
  2. Monday is sunny, so the state vector is x0 = 10. Then Tuesday is x1 = Tx0 = 0.70.3, the first column of T.
  3. (a) T = 0.70.40.30.6, and the chance of rain on Tuesday is 0.3.
  4. Multiply by T again for Wednesday: x2 = Tx1 = 0.7 × 0.7 + 0.4 × 0.30.3 × 0.7 + 0.6 × 0.3 = 0.49 + 0.120.21 + 0.18 = 0.610.39.
  5. (b) The chance of rain on Wednesday is 0.39. Check by the paths from Monday: sunny, sunny, rainy has chance 0.7 × 0.3 = 0.21, and sunny, rainy, rainy has chance 0.3 × 0.6 = 0.18, so the chance is 0.21 + 0.18 = 0.39.

answer(a) T = 0.70.40.30.6, and the chance of rain on Tuesday is 0.3; (b) 0.39

techniqueTransition Diagrams · Transition Matrices

Common pitfalls

  • Putting the sunny day's chances along the first row instead of down the first column. Then T10 = 0.70.4, whose entries add up to 1.1, so it cannot be a state vector.
  • Squaring the chance of rain to get 0.3 × 0.3 = 0.09. That uses the chance of rain after a sunny day twice, but after a rainy Tuesday the chance of rain is 0.6, and rain on Wednesday can also follow a sunny Tuesday. The two paths give 0.18 + 0.21 = 0.39.
02

A Car-Hire Firm's Cars Returned to Three Depots, and How Many Each Depot Holds in the Long Run

methodWrite Each Depot's Returns Down Its Own Column, Multiply the Numbers of Cars by the Matrix for the Next Morning, and Solve for the Steady State with the Shares Adding Up to 1

A car-hire firm has 120 cars and three depots: the airport (A), the city center (C) and the harbor (H). Each car is hired for a day and returned the next morning. Of the cars hired from the airport, 70% come back to the airport, 20% to the city center and 10% to the harbor. Of those hired from the city center, 30% come back to the airport, 60% to the city center and 10% to the harbor. Of those hired from the harbor, 30% come back to the airport, 20% to the city center and 50% to the harbor. Take the state vector as a column of the numbers of cars at A, C and H. This morning each depot has 40 cars. (a) Write down the transition matrix T, and find the number of cars at each depot tomorrow morning. (b) Find the number of cars each depot holds in the long run, so that the firm knows how many parking spaces each depot needs.

ACH0.70.20.10.30.60.10.30.20.5fromACHA0.70.30.3C0.20.60.2H0.10.10.5toeach column adds up to 1A: 0.7 + 0.2 + 0.1 = 1
Each depot's arrows are its column of T = 0.70.30.30.20.60.20.10.10.5.
The column for each depot holds where its cars go: T = 0.70.30.30.20.60.20.10.10.5, with the rows and columns in the order A, C, H. Each column adds up to 1.
step 1 of 5

A steady state is a state vector that T leaves unchanged. Writing it as shares a, c and h that add up to 1 turns Tπ = π into equations that can be solved one at a time, and the shares of the 120 cars give the numbers at each depot.

  1. The column for each depot holds where its cars go: T = 0.70.30.30.20.60.20.10.10.5, with the rows and columns in the order A, C, H. Each column adds up to 1.
  2. (a) Tomorrow morning: T404040 = 28 + 12 + 128 + 24 + 84 + 4 + 20 = 524028: 52 cars at the airport, 40 in the city center and 28 at the harbor. Check: 52 + 40 + 28 = 120.
  3. For the long run, let the steady state be π = ach, with Tπ = π and a + c + h = 1. The third row gives 0.1a + 0.1c + 0.5h = h, so 0.1(a + c) = 0.5h. Since a + c = 1 − h, 0.1 − 0.1h = 0.5h, so 0.6h = 0.1 and h = 16.
  4. The first row gives 0.7a + 0.3c + 0.3h = a, so 0.3(c + h) = 0.3a and c + h = a. With a + c + h = 1, 2a = 1, so a = 12 and c = 12 − 16 = 13.
  5. (b) In the long run the depots hold 12 × 120 = 60, 13 × 120 = 40 and 16 × 120 = 20 cars. Check: T604020 = 42 + 12 + 612 + 24 + 46 + 4 + 10 = 604020.

answer(a) T = 0.70.30.30.20.60.20.10.10.5; tomorrow 52 cars at the airport, 40 in the city center and 28 at the harbor; (b) 60, 40 and 20 cars

techniqueThe Long-Run Steady State · Transition Matrices · Transition Diagrams

Common pitfalls

  • Solving Tπ = π without the condition a + c + h = 1. The three equations fix only the ratio a : c : h = 3 : 2 : 1, because any multiple of a steady state is also left unchanged; the condition that the shares add up to 1 picks out 12, 13 and 16.
  • Reading the long run from tomorrow's numbers, 52, 40 and 28. One morning moves the cars only part of the way: the airport goes on filling, to an average of 56.8 cars the morning after, and only the steady state, 60, is left unchanged by T.
03

Customers Switching Between Three Phone Networks Each Year, Followed for Two Years

methodBuild the Matrix with One Column for Each Network, Multiply the Customer Numbers by It Once for Each Year, and Compare the Numbers After Two Years with the Start

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.

PQR0.80.10.10.20.70.10.10.10.8fromPQRP0.80.20.1Q0.10.70.1R0.10.10.8tocolumns: 0.8 + 0.1 + 0.1 = 1, 0.2 + 0.7 + 0.1 = 1
One column of T = 0.80.20.10.10.70.10.10.10.8 for each network: where its customers are a year later.
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.
step 1 of 4

One column for each network holds the fractions of its customers that go to P, Q and R, so each column adds up to 1 and no customer is lost. Multiplying the column of customer numbers by T moves it on one year; doing it twice gives 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.
  2. (a) Next year: T800080004000 = 6400 + 1600 + 400800 + 5600 + 400800 + 800 + 3200 = 840068004800: 8400 customers on P, 6800 on Q and 4800 on R.
  3. Multiply by T again for two years' time: T840068004800 = 6720 + 1360 + 480840 + 4760 + 480840 + 680 + 3840 = 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.

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

techniqueTransition Matrices · Transition Diagrams

Common pitfalls

  • 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.
04

A Frog Hopping Between Three Lily Pads in a Row, and the Share of Time It Spends on the Middle Pad

methodDraw Each Pad's Hops as Arrows, Follow the Only Path to the Far Pad for the Two-Minute Chance, and Solve for the Steady State One Row at a Time

A frog sits on one of three lily pads in a row: the left pad L, the middle pad M and the right pad R. Each minute, a frog on an end pad stays where it is with probability 12 and hops to the middle pad with probability 12; a frog on the middle pad stays with probability 12 and hops to each end pad with probability 14. It cannot hop from one end pad straight to the other. The state vector is a column of the chances that the frog is on L, M and R. The frog starts on the left pad. (a) Write down the transition matrix T, and find the chance that the frog is on the right pad after two minutes. (b) Find the fraction of the time the frog spends on the middle pad in the long run.

LMR1/21/21/41/21/41/21/2fromLMRL1/21/40M1/21/21/2R01/41/2tono arrow from L straight to R: 0each column adds up to 1
Each hop is an arrow, and the columns of T = 1214012121201412 are the arrows out of L, M and R.
T = 1214012121201412, with the rows and columns in the order L, M, R. The 0 in each corner is a hop from one end pad straight to the other, which cannot happen.
step 1 of 5

The transition diagram shows every hop with its chance, and the columns of T are read off it. A path of two hops from L to R must pass through M, so its chance is a product. The steady state comes from Tπ = π one row at a time, with the three chances adding up to 1.

  1. T = 1214012121201412, with the rows and columns in the order L, M, R. The 0 in each corner is a hop from one end pad straight to the other, which cannot happen.
  2. After one minute the frog is on L or on M: x1 = T100 = 12120.
  3. (a) To be on R after two minutes, the frog must hop to M and then to R, so the chance is 12 × 14 = 18. Check with T: x2 = Tx1 = 381218.
  4. For the long run, let π = lmr. The first row of Tπ = π gives 12l + 14m = l, so m = 2l, and the third row gives m = 2r in the same way. Then l + 2l + l = 1, so l = 14, m = 12 and r = 14.
  5. (b) In the long run the frog spends half of its time on the middle pad. Check the middle row: 12 × 14 + 12 × 12 + 12 × 14 = 12.

answer(a) T = 1214012121201412, and the chance is 18 = 0.125; (b) half of the time, 12 = 0.5

techniqueTransition Diagrams · The Long-Run Steady State · Transition Matrices

Common pitfalls

  • Giving each pad a third of the time because there are three pads. The middle pad can be reached from both end pads, and the frog leaves it only half of the time, so it holds 12 of the time and each end pad 14.
  • Counting a path L, L, R in the two-minute chance. The frog cannot hop from L straight to R, and that entry of T is 0, so the only path is L, M, R, with chance 18.
05

A Student's Daily Choice of Bus, Bike or Walking, and the Share of Days for Each in the Long Run

methodWrite the Steady State with Shares That Add Up to 1, Start from the Row That Gives One Share at Once, Solve for the Other Two, and Turn the Shares into Days

Mei goes to school each day by bus, by bike or on foot, and her choice depends on how she went the day before. After a day on the bus she takes the bus again with probability 0.8, cycles with probability 0.1 and walks with probability 0.1. After a day on her bike she takes the bus with probability 0.2, cycles with probability 0.7 and walks with probability 0.1. After a day on foot she takes the bus with probability 0.6, cycles with probability 0.3 and walks with probability 0.1. The state vector is a column of the chances of bus, bike and walking. (a) Write down the transition matrix T, and find its steady state. (b) A school year has 200 days. In the long run, on about how many of them does Mei travel each way?

busbikewalk0.80.10.10.20.70.10.60.30.1frombusbikewalkbus0.80.20.6bike0.10.70.3walk0.10.10.1tosteady state: b + k + w = 1
The columns of T = 0.80.20.60.10.70.30.10.10.1 are the arrows out of bus, bike and walk.
T = 0.80.20.60.10.70.30.10.10.1, in the order bus, bike, walk, and each column adds up to 1. Let the steady state be π = bkw, with Tπ = π and b + k + w = 1.
step 1 of 5

The steady state π is the column of long-run shares of days, the one that T leaves unchanged. Each row of Tπ = π is an equation, and the condition that the shares add up to 1 completes them. The shares of 200 days give the numbers of days.

  1. T = 0.80.20.60.10.70.30.10.10.1, in the order bus, bike, walk, and each column adds up to 1. Let the steady state be π = bkw, with Tπ = π and b + k + w = 1.
  2. The third row of Tπ = π is 0.1b + 0.1k + 0.1w = w, that is 0.1(b + k + w) = w. Since b + k + w = 1, w = 0.1: whichever way she went the day before, she walks with probability 0.1.
  3. The first row gives 0.8b + 0.2k + 0.6 × 0.1 = b, so 0.2k + 0.06 = 0.2b and b = k + 0.3. With b + k = 1 − 0.1 = 0.9, 2k + 0.3 = 0.9, so k = 0.3 and b = 0.6.
  4. (a) The steady state is π = 0.60.30.1. Check the second row: 0.1 × 0.6 + 0.7 × 0.3 + 0.3 × 0.1 = 0.06 + 0.21 + 0.03 = 0.3.
  5. (b) Over 200 days Mei takes the bus on about 0.6 × 200 = 120 days, cycles on about 0.3 × 200 = 60 days and walks on about 0.1 × 200 = 20 days.

answer(a) T = 0.80.20.60.10.70.30.10.10.1, with steady state π = 0.60.30.1; (b) about 120 days by bus, 60 by bike and 20 on foot

techniqueThe Long-Run Steady State · Transition Matrices

Common pitfalls

  • Taking the first column, 0.8, 0.1 and 0.1, as the long-run shares of days. That column is only the next day's chances after a day on the bus; the long-run shares must be left unchanged by T, and T0.80.10.1 = 0.720.180.1 is not.
  • Solving the rows of Tπ = π and leaving out b + k + w = 1. The rows on their own give only b = 2k and k = 3w, a ratio of 6 : 3 : 1; the condition that the shares add up to 1 is what gives 0.6, 0.3 and 0.1.
06

A Library Book That Is on the Shelf, on Loan or Lost, Followed Week by Week

methodDraw Lost as a State with a Loop of Probability 1 and No Arrow Out, Step the State Vector On Week by Week, and Solve for the Steady State

Each week a library book is on the shelf, on loan or lost. A book on the shelf stays there with probability 0.4 and is borrowed with probability 0.6. A book on loan is returned to the shelf with probability 0.7, is still on loan the next week with probability 0.2, and is lost with probability 0.1. A lost book is never found. The state vector is a column of the chances of shelf, loan and lost. This week the book is on the shelf. (a) Write down the transition matrix T, and find the chance that the book is lost by the end of the third week. (b) Find the steady state, and explain what happens to the book in the long run.

shelfloanlost0.40.60.70.20.11fromshelfloanlostshelf0.40.70loan0.60.20lost00.11tolost → lost: 1, and no arrow out
T = 0.40.700.60.2000.11. The lost state has a loop of 1 and no arrow out: it is absorbing.
T = 0.40.700.60.2000.11, in the order shelf, loan, lost. The third column is 001: a lost book stays lost, so the lost state is absorbing.
step 1 of 5

A state that cannot be left is called absorbing: its column in T has a 1 on the diagonal and 0 elsewhere. The chance of being in it can only rise week by week, and solving Tπ = π shows where all the chance ends up.

  1. T = 0.40.700.60.2000.11, in the order shelf, loan, lost. The third column is 001: a lost book stays lost, so the lost state is absorbing.
  2. Step the state on from x0 = 100: x1 = 0.40.60 and x2 = 0.16 + 0.420.24 + 0.120.06 = 0.580.360.06.
  3. (a) In week three the chance of lost is the chance already lost plus the chance lost from loan: 0.06 + 0.1 × 0.36 = 0.06 + 0.036 = 0.096. The chance that the book is lost by the end of the third week is 0.096.
  4. For a steady state π = snx, the first row gives 0.4s + 0.7n = s, so 0.7n = 0.6s, and the second row gives 0.6s + 0.2n = n, so 0.6s = 0.8n. Then 0.7n = 0.8n, so n = 0, then s = 0, and x = 1.
  5. (b) The only steady state is 001. Each week on loan carries a chance of 0.1 of being lost, and a lost book never comes back, so the chance of lost can only rise: 0, 0.06, 0.096, … towards 1. In the long run the book is lost.

answer(a) T = 0.40.700.60.2000.11, and the chance is 0.096; (b) the steady state is 001: a lost book never returns, so in the long run the book is lost

techniqueThe Long-Run Steady State · Transition Diagrams · Transition Matrices

Common pitfalls

  • Adding the chances of lost in weeks one, two and three, 0 + 0.06 + 0.096. The lost state keeps its chance from one week to the next, so 0.096 already includes the 0.06 lost by week two; added again, it is counted twice.
  • Expecting a steady state with the book spread over all three states, as in a chain with no absorbing state. There is no arrow out of the lost state, so every steady state has all its chance there: 001.
07

A Factory Machine That Works or Breaks Down Each Day, and the Share of Days It Works in the Long Run

methodStep On Two Days from a Broken Machine for the Short-Term Chance, Then Solve for the Steady State to Find the Long-Run Share of Working Days

A machine in a bottling factory is either working or broken at the start of each day. If it is working today, it is working tomorrow with probability 0.9 and broken with probability 0.1. If it is broken today, it is repaired and working tomorrow with probability 0.6, and still broken with probability 0.4. The state vector is a column of the chances of working and broken. The machine is broken on Monday. (a) Find the chance that it is working on Wednesday. (b) Find the fraction of days on which the machine works in the long run, and the number of working days in a year of 350 days.

worksbroken0.90.10.60.4fromworksbrokenworks0.90.6broken0.10.4to0.9 + 0.1 = 1, 0.6 + 0.4 = 1
T = 0.90.60.10.4, with the columns in the order working, broken.
The column for working holds 0.9 and 0.1, and the column for broken holds 0.6 and 0.4: T = 0.90.60.10.4.
step 1 of 5

Two multiplications by T carry Monday's state vector to Wednesday. For the long run, the steady state is the pair of shares that T leaves unchanged: as many machines go from working to broken each day as come back.

  1. The column for working holds 0.9 and 0.1, and the column for broken holds 0.6 and 0.4: T = 0.90.60.10.4.
  2. Monday is 01, so Tuesday is the second column, 0.60.4. Wednesday is T0.60.4 = 0.54 + 0.240.06 + 0.16 = 0.780.22.
  3. (a) The chance that the machine is working on Wednesday is 0.78: repaired on Tuesday and still working, 0.6 × 0.9 = 0.54, or still broken on Tuesday and repaired on Wednesday, 0.4 × 0.6 = 0.24.
  4. For the steady state π = wb, the first row of Tπ = π gives 0.9w + 0.6b = w, so 0.6b = 0.1w and w = 6b. With w + b = 1, 7b = 1, so b = 17 and w = 67.
  5. (b) In the long run the machine works on 67 of the days: 67 × 350 = 300 working days in the year, and 50 days broken. Check: the first entry of T6717 is 5.4 + 0.67 = 67.

answer(a) 0.78; (b) 67 of the days: 300 working days out of 350

techniqueThe Long-Run Steady State · Transition Matrices

Common pitfalls

  • Working out 0.6 × 0.9 = 0.54 alone for Wednesday. That is only the path in which the machine is repaired on Tuesday; it can also stay broken on Tuesday and be repaired on Wednesday, 0.4 × 0.6 = 0.24, so the chance is 0.54 + 0.24 = 0.78.
  • Taking the long-run share of working days as 0.9, the chance of working after a working day. The machine is sometimes broken, and a broken day is followed by a working day only 0.6 of the time, so the share is 67 ≈ 0.857, a little below 0.9.
08

Three Pages of a Website Linked to One Another, and a Ranking by Where Visitors' Clicks Land

methodShare Each Page's Column Equally Between Its Links, Add the Two-Click Paths Back to the Start, and Rank the Pages by the Steady State

A small website has three pages: Home (H), News (N) and Shop (S). Home links to News and to Shop, News links to Home and to Shop, and Shop links only to Home. A visitor on a page clicks one of its links, each with the same chance. The state vector is a column of the chances that the visitor is on H, N and S. (a) Write down the transition matrix T, and find the chance that a visitor who starts on Home is back on Home after two clicks. (b) Find the fraction of clicks that land on each page in the long run, and rank the pages.

HomeNewsShop1/21/21/21/21fromHomeNewsShopHome01/21News1/200Shop1/21/20totwo links: 1/2 each; one link: 1
Each page shares its column equally between its links: T = 0121120012120.
Home has two links, so its column holds 12 for News and 12 for Shop; News also has two links; Shop has one, to Home. So T = 0121120012120, in the order H, N, S.
step 1 of 5

Each page's column shares a chance of 1 equally between the pages it links to. A two-click chance is the sum over the paths, and the long-run fractions are the steady state, found from Tπ = π with the fractions adding up to 1. Ranking pages this way is how a search engine's PageRank begins.

  1. Home has two links, so its column holds 12 for News and 12 for Shop; News also has two links; Shop has one, to Home. So T = 0121120012120, in the order H, N, S.
  2. (a) Two clicks from Home back to Home go through News, with chance 12 × 12 = 14, or through Shop, with chance 12 × 1 = 12. The chance is 14 + 12 = 34.
  3. For the long run, let π = hns. The second row of Tπ = π gives n = 12h, and the third row gives s = 12h + 12n = 12h + 14h = 34h.
  4. With h + n + s = 1: h + 12h + 34h = 94h = 1, so h = 49, n = 29 and s = 39 = 13.
  5. (b) In the long run 49 of the clicks land on Home, 13 on Shop and 29 on News, so the ranking is Home, Shop, News. Check the first row: 12 × 29 + 1 × 13 = 19 + 39 = 49.

answer(a) T = 0121120012120, and the chance is 34 = 0.75; (b) Home 49, Shop 13, News 29: Home first, then Shop, then News

techniqueThe Long-Run Steady State · Transition Diagrams · Transition Matrices

Common pitfalls

  • Ranking the pages by how many links each one has, which puts Home and News level. A page's rank depends on the links that point to it and on the rank of the pages they come from: Shop receives links from both Home and News, and ranks above News.
  • Putting a 1 for every link, so that Home's column holds 1 and 1. The visitor follows only one link, so the chances in each column must add up to 1, and each of Home's two links gets 12.
09

A Student Who Hands In Homework on Time or Late, and a Missing Chance Found from Her Long-Run Record

methodWrite the Unknown Chance into the Matrix, Put the Known Long-Run Shares in as the Steady State, and Solve One Row of T Times the Steady State Equals Itself for the Unknown

Each week Priya hands in her homework on time or late. If she is on time one week, she is on time the next week with probability 0.9. If she is late one week, she is on time the next week with probability p. Her teacher's records over many weeks show that she is on time in 45 of the weeks. The state vector is a column of the chances of on time and late. (a) Write down the transition matrix T in terms of p, and find p. (b) Priya is late this week. Find the chance that she is on time in two weeks' time.

on timelate0.90.1p1 − pfromon timelateon time0.9plate0.11 − ptolong run: on time in 4/5 of the weeks
The unknown chance p goes on the arrow from late to on time: T = 0.9p0.11 − p.
The column for on time holds 0.9 and 0.1, and the column for late holds p and 1 − p: T = 0.9p0.11 − p.
step 1 of 5

A record over many weeks is the steady state of the chain, so it must be left unchanged by T. With one entry of T unknown, one row of Tπ = π is an equation for it.

  1. The column for on time holds 0.9 and 0.1, and the column for late holds p and 1 − p: T = 0.9p0.11 − p.
  2. The long-run record is the steady state, π = 0.80.2, so Tπ = π. The first row gives 0.9 × 0.8 + 0.2p = 0.8, so 0.72 + 0.2p = 0.8, 0.2p = 0.08 and p = 0.4.
  3. (a) T = 0.9p0.11 − p with p = 0.4. Check: each week 0.1 × 0.8 = 0.08 of the chance moves from on time to late and 0.4 × 0.2 = 0.08 moves back, so the shares stay as they are.
  4. This week is late, 01, so next week is 0.40.6, and the first entry for the week after is 0.9 × 0.4 + 0.4 × 0.6 = 0.36 + 0.24 = 0.6.
  5. (b) The chance that Priya is on time in two weeks' time is 0.6: on time next week and again the week after, 0.36, or late next week and then on time, 0.24.

answer(a) T = 0.9p0.11 − p with p = 0.4; (b) 0.6

techniqueThe Long-Run Steady State · Transition Matrices

Common pitfalls

  • Setting p = 0.8 because she is on time in 45 of the weeks. The 45 is a long-run share over all weeks; p is the chance of being on time after a late week only, and it has to be found from Tπ = π.
  • Giving next week's chance, 0.4, for part (b). Two weeks' time is two steps on, so the state vector is multiplied by T twice, which gives 0.6.
10

A Coffee Cart Parked at the Station or the Park Each Day, and Why Its Long Run Does Not Depend on Where It Starts

methodSquare the Transition Matrix for Two Days Ahead, Square Again for Four, and Watch Both Columns Close In on the Steady State

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.

stationpark0.60.40.20.8fromstationparkstation0.60.2park0.40.8tocolumn 1: from the station, column 2: from the park
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.
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.
step 1 of 6

The columns of Tn are where a cart that starts at each place is n days later. Multiplying T by itself gives T2, and squaring T2 gives T4. As n grows the two columns close in on the same column, the steady state, so the starting place is forgotten.

  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.
  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.
  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.
  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.
  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.
  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.

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

techniqueTransition Matrices · The Long-Run Steady State

Common pitfalls

  • 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.
Mr. Chalk Read the guide