Free worked solutions · 2026 Edition

IB Maths HL Paper 3 Chapter 13: Networks and Markov chains worked solutions

Worked solutions to the investigations in Chapter 13 of Photon Guidebook: Mathematics HL Paper 3 for the IB Diploma (2026 Edition). Each solution shows every step with the mark it earns, the way an IB mark scheme does.

Chapter 13 of 18
9 practice questions
2 Going further
Free, no sign-up

Start with Investigations All 18 chapters

Investigations

The practice investigations of the chapter, each with its full worked solution and mark scheme.

Investigation 1

[16 marks]

This question asks you to find the cheapest set of paths that links all the shelters in a nature park.

The park has shelters A to G, marked in the diagram. The possible paths and their lengths, in hundreds of metres, are AB 4, AC 7, BC 3, BD 6, CD 5, CE 8, DE 2, DF 9, EF 7, EG 6 and FG 4.

(a) Draw the network, labelling every path with its length.

[2]

(b) Use Kruskal's algorithm to find a minimum spanning tree, listing the edges in the order they are chosen.

[4]

(c) State the total length of the spanning tree.

[1]

(d) Resurfacing costs 30 dollars per metre. Find the cost of resurfacing only the paths in your tree.

[2]

(e) The path DE is closed. Find the new minimum spanning tree and the increase in cost.

[4]

(f) Explain why a minimum spanning tree is not a route a ranger could walk to visit every shelter.

[3]

Show solutionHide solution

(a) all seven shelters joined by the eleven paths [A1]; each path labelled with its length [A1].

(b) Kruskal: take the shortest remaining path that does not make a cycle [M1]; DE 2, BC 3 [A1]; AB 4 and FG 4, in either order [A1]; CD 5, then BD 6 is rejected (it makes a cycle), then EG 6 [A1].

(c) 2+3+4+4+5+6=24, that is 2400 m [A1].

(d) 2400\times30 [M1] =72\,000 dollars [A1].

(e) without DE, Kruskal gives BC 3, AB 4, FG 4, CD 5, EG 6, CE 8 [M1 A1]; total 30, that is 3000 m [A1]; the increase is 600 m, which costs 18 000 dollars [A1].

(f) a tree has no cycle, so some shelters are dead ends [R1]; a ranger who walks to a dead end has to come back along the same path [R1]; so a walking route repeats paths and is longer than the tree [R1].

Final answer

(b) DE 2, BC 3, AB 4, FG 4, CD 5, EG 6
(c) 24, that is 2400 m
(d) 72 000 dollars
(e) BC, AB, FG, CD, EG, CE: 3000 m, an increase of 600 m, 18 000 dollars
(f) a tree has dead ends, so a walk repeats paths.

Investigation 2

[16 marks]

This question asks you to model whether a coffee machine in a school office is working each day.

The machine is either working (W) or faulty (F) at the start of each day. If it is working today, it is working tomorrow with probability 0.92. If it is faulty today, it is repaired overnight with probability 0.6.

(a) Write down the transition matrix T, with columns for today's state.

[2]

(b) The machine is working on Monday. Find the probability that it is working on Wednesday.

[3]

(c) Find the steady-state probabilities of W and F.

[3]

(d) The school year has 190 days. Estimate the number of days on which the machine is faulty.

[2]

(e) Starting on a day it is working, find the expected number of days until the first day it is faulty, and justify your method.

[3]

After a service contract, the probability of a repair overnight rises to 0.9.

(f) Find the new long-run probability that the machine is faulty.

[1]

(g) Give one reason why a Markov chain may not describe the machine well.

[2]

Show solutionHide solution

(a) T=\begin{pmatrix}0.92&0.6\\0.08&0.4\end{pmatrix} [A1 A1], one mark for each column.

(b) T^2=T\cdot T [M1]; the entry in row W, column W is 0.92\times0.92+0.6\times0.08 [M1] =0.894 [A1].

(c) solve (T-I)\mathbf{s}=\mathbf{0} with s_W+s_F=1 [M1]; -0.08s_W+0.6s_F=0, so s_W=7.5s_F [A1]; s_W=\frac{15}{17}=0.882 and s_F=\frac{2}{17}=0.118 [A1].

(d) 190\times\frac{2}{17} [M1] =22.4, so about 22 days [A1].

(e) the machine is working each day, and fails the next day with probability 0.08 independently [R1]; so the number of days until the first fault has a geometric distribution with p=0.08 [M1]; expected value \frac{1}{0.08}=12.5 days [A1].

(f) \frac{0.08}{0.08+0.9}=0.0816 [A1].

(g) for example, a fault is more likely after a long run of working days (a worn part), so tomorrow depends on more than today [R1]; or a repair may depend on when the engineer visits, which is not constant [R1].

Final answer

(a) T=\begin{pmatrix}0.92&0.6\\0.08&0.4\end{pmatrix}
(b) 0.894
(c) (0.882,\ 0.118)
(d) about 22 days
(e) 12.5 days
(f) 0.0816.

Investigation 3

[20 marks]

This question asks you to find the shortest route that travels along every cycle path in a park.

A park has junctions P, Q, R, S, T and U joined by cycle paths with lengths in metres: PQ 300, QR 250, RS 400, ST 200, TU 350, UP 150, QT 500 and PS 450.

(a) Find the total length of the paths.

[1]

(b) Write down the degree of each junction and explain why a route along every path that returns to its start must repeat some paths.

[3]

(c) Find the shortest distance between each pair of odd junctions.

[4]

(d) Hence find the length of the shortest route that travels every path and returns to its start.

[4]

(e) An inspector, Mr Reyes, may start and finish at different junctions. Find where he should start and finish and the length of his shortest route.

[4]

(f) A new path QS of length 600 m is built. Find the new shortest closed route.

[4]

Show solutionHide solution

(a) 300+250+400+200+350+150+500+450=2600 m [A1].

(b) degrees P 3, Q 3, R 2, S 3, T 3, U 2 [A1]; a closed route uses an even number of path-ends at every junction, because each visit enters and leaves [R1]; four junctions have odd degree, so some paths must be repeated [R1].

(c) list all six pairs of P, Q, S, T [M1]; PQ 300 and ST 200 [A1]; PS 450 and QT 500 [A1]; PT 500 (by P, U, T) and QS 650 (by Q, R, S) [A1].

(d) the three pairings are PQ with ST, PS with QT, PT with QS [M1]; totals 500, 950 and 1150 [A1]; the least is 500 [M1]; so the length is 2600+500=3100 m [A1].

(e) he repeats the shortest path between one pair of odd junctions and starts and ends at the other pair [M1]; the shortest repeat is ST, 200 [A1]; he starts at P and finishes at Q (or the reverse) [A1]; length 2600+200=2800 m [A1].

(f) Q and S now have degree 4, so only P and T are odd [M1]; the total is 3200 m [A1]; the shortest path from P to T is 500 m [M1]; the closed route is 3200+500=3700 m [A1].

Final answer

(a) 2600 m
(b) degrees 3, 3, 2, 3, 3, 2
(c) PQ 300, PS 450, PT 500, QS 650, QT 500, ST 200
(d) 3100 m
(e) repeat ST, start P finish Q, 2800 m
(f) odd junctions P and T only: 3700 m.

Investigation 4

[20 marks]

This question asks you to bound the length of a delivery tour for a drone company.

A drone company has five depots, A to E. The table shows the flight time, in minutes, between each pair of depots.

\begin{array}{|c|r|r|r|r|r|}\hline & A & B & C & D & E\\\hline A & - & 12 & 23 & 7 & 19\\\hline B & 12 & - & 20 & 17 & 18\\\hline C & 23 & 20 & - & 27 & 25\\\hline D & 7 & 17 & 27 & - & 8\\\hline E & 19 & 18 & 25 & 8 & -\\\hline\end{array}

(a) Use Kruskal's algorithm to find a minimum spanning tree. List the edges in the order they are chosen and state the total weight.

[4]

A drone must start at A, visit every other depot exactly once and return to A.

(b) Use the nearest neighbour algorithm from A to find an upper bound on the total flight time.

[3]

(c) Delete vertex C to find a lower bound on the total flight time.

[4]

(d) State what your answers show about the shortest total flight time.

[1]

(e) Find a tour of length 72 minutes and state what you can now say about the shortest total flight time.

[3]

Each minute of flight costs 0.35 dollars, and each depot stop costs 2 dollars for a battery swap.

(f) Find the cost of the tour in (e), counting five stops.

[2]

(g) Depot C closes. Find the shortest tour of A, B, D and E, starting and ending at A.

[3]

Show solutionHide solution

(a) order the edges by weight and add each one that makes no cycle [M1]; AD 7, DE 8, AB 12 [A1]; then BD 17, BE 18 and AE 19 are rejected (cycles) and BC 20 is added [A1]; total 7+8+12+20=47 minutes [A1].

(b) from A the nearest is D (7); from D, E (8); from E, B (18) [M1]; then C (20) and back to A (23): A, D, E, B, C, A [A1]; 7+8+18+20+23=76 minutes [A1].

(c) delete C; the minimum spanning tree of A, B, D, E is AD 7, DE 8, AB 12 [M1], weight 27 [A1]; add the two shortest edges at C, BC 20 and AC 23 [M1]; lower bound 27+43=70 minutes [A1].

(d) the shortest total flight time is between 70 and 76 minutes [R1].

(e) for example A, B, C, E, D, A [M1]: 12+20+25+8+7=72 [A1]; so the shortest time is between 70 and 72 minutes [R1].

(f) 72\times0.35+5\times2 [M1] =35.20 dollars [A1].

(g) the three different tours are ABDEA, ABEDA and ADBEA [M1]; lengths 12+17+8+19=56, 12+18+8+7=45 and 7+17+18+19=61 [A1]; the shortest is ABEDA, 45 minutes [A1].

Final answer

(a) AD, DE, AB, BC: 47
(b) A, D, E, B, C, A: 76
(c) 70
(d) between 70 and 76 minutes
(e) A, B, C, E, D, A: 72, between 70 and 72
(f) 35.20 dollars
(g) A, B, E, D, A: 45 minutes.

Investigation 5

[22 marks]

This question asks you to count routes between the rooms of a museum, and to follow a guard who moves at random.

A museum has five rooms, numbered 1 to 5. Doorways join the rooms 1 and 2, 1 and 3, 2 and 3, 2 and 4, 3 and 4, 3 and 5, and 4 and 5.

(a) Write down the number of doorways in each room.

[2]

(b) Write down the adjacency matrix A, with rooms in numerical order.

[2]

(c) Find A^2 and explain the meaning of the entry in row 1, column 1.

[3]

(d) Find the number of walks of length 3 from room 1 to room 5.

[2]

(e) Find the trace of A^3 and use it to find the number of triangles of rooms, that is, sets of three rooms each joined to the other two.

[3]

At the end of each hour a guard moves to one of the neighbouring rooms, each equally likely. Let M be the transition matrix, with columns for the room she is leaving.

(f) Write down the first column of M and the third column of M.

[2]

(g) The guard starts in room 1. Find the probability that she is in room 3 after two moves.

[3]

(h) Show that the steady-state vector is \frac{1}{14}(2,3,4,3,2)^{\mathsf T}.

[4]

(i) Explain why the guard spends the most time in room 3.

[1]

Show solutionHide solution

(a) rooms 1 to 5 have 2, 3, 4, 3, 2 doorways [A1 A1], one mark for any three correct and one for all five.

(b) A=\begin{pmatrix}0&1&1&0&0\\1&0&1&1&0\\1&1&0&1&1\\0&1&1&0&1\\0&0&1&1&0\end{pmatrix} [A1 A1], one mark for any four correct rows and one for all five.

(c) A^2=\begin{pmatrix}2&1&1&2&1\\1&3&2&1&2\\1&2&4&2&1\\2&1&2&3&1\\1&2&1&1&2\end{pmatrix} [A1]; the entry is the number of walks of length 2 from room 1 back to room 1 [R1]; it is 2, the number of doorways in room 1 [A1].

(d) the entry in row 1, column 5 of A^3 [M1] is 3 [A1].

(e) the diagonal of A^3 is 2, 4, 6, 4, 2, so the trace is 18 [A1]; each triangle gives 6 closed walks of length 3 (3 starting rooms, 2 directions) [R1]; so there are 18\div6=3 triangles [A1].

(f) first column (0,\frac12,\frac12,0,0)^{\mathsf T} [A1]; third column (\frac14,\frac14,0,\frac14,\frac14)^{\mathsf T} [A1].

(g) from room 1 she moves to room 2 or room 3, each with probability \frac12, and only a move from room 2 reaches room 3, with probability \frac13 [M1 M1]; the probability is \frac12\times\frac13=\frac16 [A1].

(h) let \mathbf{s}=\frac{1}{14}(d_1,\dots,d_5)^{\mathsf T}, where d_j is the degree of room j [M1]; the entry of M\mathbf{s} in row i is \sum_j\frac{A_{ij}}{d_j}\times\frac{d_j}{14} [M1]; this is \frac{1}{14}\sum_jA_{ij}=\frac{d_i}{14} [A1]; so M\mathbf{s}=\mathbf{s}, and the entries add to \frac{14}{14}=1 [R1].

(i) room 3 has the most doorways, so a random walker enters it most often [R1].

Final answer

(a) 2,3,4,3,2
(c) the entry is 2, the walks of length 2 from room 1 to itself
(d) 3
(e) trace 18, so 3 triangles
(g) \frac16
(h) M\mathbf{s}=\mathbf{s} for \mathbf{s}=\frac1{14}(2,3,4,3,2)^{\mathsf T}.

Investigation 6

[24 marks]

This question asks you to model the weather at a mountain observatory as a Markov chain.

Each day at the observatory is clear (C), cloudy (L) or rainy (R). The diagram shows the probabilities for tomorrow's weather, given today's.

(a) Write down the transition matrix T, with columns for today's weather.

[2]

(b) Monday is clear. Find the probability that Wednesday is clear, and the probabilities of clear, cloudy and rainy weather on Thursday.

[4]

(c) Show that 1 is an eigenvalue of T and find the steady-state vector.

[4]

(d) Find the other two eigenvalues of T.

[3]

(e) Estimate the number of rainy days in a year of 365 days.

[2]

Let m_C and m_L be the expected numbers of days until the first rainy day, starting from a clear day and from a cloudy day.

(f) Explain why m_C=1+0.6m_C+0.3m_L, and write down the equation for m_L.

[3]

(g) Solve the equations and interpret m_L.

[3]

(h) Describe what happens to T^n as n becomes large, and explain it using your eigenvalues.

[3]

Show solutionHide solution

(a) T=\begin{pmatrix}0.6&0.3&0.2\\0.3&0.4&0.4\\0.1&0.3&0.4\end{pmatrix} [A1 A1], one mark for any two columns correct.

(b) (T^2)_{CC}=0.6\times0.6+0.3\times0.3+0.2\times0.1 [M1] =0.47 [A1]; Thursday's column is the first column of T^3 [M1]: clear 0.422, cloudy 0.353, rainy 0.225 [A1].

(c) each column of T-I sums to 0, so \det(T-I)=0 [R1]; solve (T-I)\mathbf{s}=\mathbf{0} with the entries summing to 1 [M1]; \mathbf{s}=\frac{1}{61}(24,22,15) [A1]; =(0.393,0.361,0.246) [A1].

(d) the sum of the eigenvalues is the trace, 1.4, and their product is \det T=0.01 [M1], so the other two satisfy \lambda^2-0.4\lambda+0.01=0 [A1]; \lambda=0.373 and 0.0268 [A1].

(e) 365\times\frac{15}{61} [M1] =89.8, about 90 rainy days [A1].

(f) each day adds 1 [R1]; from a clear day, tomorrow is clear with probability 0.6 and cloudy with probability 0.3, and in each case the expected remaining wait starts again; rain ends the wait and adds nothing [R1]; m_L=1+0.3m_C+0.4m_L [A1].

(g) 0.4m_C-0.3m_L=1 and -0.3m_C+0.6m_L=1 [M1]; m_C=6 and m_L=\frac{14}{3}=4.67 [A1]; after a cloudy day the observatory expects to wait about 4.67 days for the first rain [R1].

(h) every column of T^n tends to the steady-state vector, so T^n tends to a matrix whose three columns are all (0.393,0.361,0.246)^{\mathsf T} [A1]; the eigenvalue 1 gives a fixed part [R1]; the other eigenvalues have modulus less than 1, so their powers tend to 0 [R1].

Final answer

(b) 0.47; Thursday (0.422,0.353,0.225)
(c) \frac1{61}(24,22,15)
(d) 0.373 and 0.0268
(e) about 90
(g) m_C=6, m_L=4.67 days.

Investigation 7

[26 marks]

This question asks you to combine a Markov chain with counting walks in a network of stations.

A shared e-scooter ends each day at station N or station S. If it ends a day at N, the next day it ends at N with probability 0.8; if it ends a day at S, the next day it ends at N with probability 0.3.

(a) Write down the transition matrix T and find the probability that a scooter at N on Monday is at N on Thursday.

[4]

(b) Find the eigenvalues and eigenvectors of T, and write T=PDP^{-1}.

[5]

(c) Hence show that the probability that a scooter at N on day 0 is at N on day n is 0.6+0.4(0.5)^n.

[4]

(d) Interpret the value 0.6 in context.

[1]

The scooter company now has four stations N, S, E and W. Single streets join N to S, N to E, N to W, S to E and E to W.

(e) Draw the network and write down its adjacency matrix A, in the order N, S, E, W.

[2]

(f) Find A^3 and state the number of walks of length 3 from N to S.

[3]

(g) Find the number of walks of length 4 that start and end at W.

[2]

(h) Explain why the Markov model of (a) to (d) would need a larger matrix for the new network, and state two assumptions it would need.

[5]

Show solutionHide solution

(a) T=\begin{pmatrix}0.8&0.3\\0.2&0.7\end{pmatrix} [A1]; T^2=\begin{pmatrix}0.7&0.45\\0.3&0.55\end{pmatrix} [M1]; T^3=T^2T [M1]; the entry in row N, column N is 0.7\times0.8+0.45\times0.2=0.65 [A1].

(b) \det(T-\lambda I)=\lambda^2-1.5\lambda+0.5=0 [M1]; \lambda=1 and \lambda=0.5 [A1]; for \lambda=1 an eigenvector is (3,2)^{\mathsf T} [A1]; for \lambda=0.5 it is (1,-1)^{\mathsf T} [A1]; T=PDP^{-1} with P=\begin{pmatrix}3&1\\2&-1\end{pmatrix} and D=\begin{pmatrix}1&0\\0&0.5\end{pmatrix} [A1].

(c) T^n=PD^nP^{-1} [M1]; P^{-1}=\frac15\begin{pmatrix}1&1\\2&-3\end{pmatrix} [M1]; the top left entry of PD^nP^{-1} is \frac15\left(3\times1\times1+1\times0.5^n\times2\right) [A1]; =0.6+0.4(0.5)^n [A1].

(d) in the long run a scooter is at N on 60% of the nights, whichever station it started at [R1].

(e) the network drawn with the five streets [A1]; A=\begin{pmatrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{pmatrix} [A1].

(f) A^3=\begin{pmatrix}4&5&5&5\\5&2&5&2\\5&5&4&5\\5&2&5&2\end{pmatrix} [M1 A1]; there are 5 walks of length 3 from N to S [A1].

(g) the entry in row W, column W of A^4 [M1] is 10 [A1].

(h) four stations mean four states, so a 4\times4 matrix with 16 probabilities [R1]; each column must sum to 1 [R1]; the scooter can only move along streets, so the entries for pairs without a street are 0 [R1]; assumption: the probabilities depend only on tonight's station, not on earlier nights [R1]; assumption: the probabilities are the same every day, whatever the weather or day of the week [R1].

Final answer

(a) T=\begin{pmatrix}0.8&0.3\\0.2&0.7\end{pmatrix}, 0.65
(b) eigenvalues 1 and 0.5, eigenvectors (3,2) and (1,-1)
(d) 60% of nights at N
(f) 5 walks
(g) 10.

Investigation 8

[26 marks]

This question asks you to plan a delivery round when some pairs of towns have no direct road.

A courier serves six towns, A to F. The table shows the length, in kilometres, of the direct road between towns. A dash means there is no direct road.

\begin{array}{|c|r|r|r|r|r|r|}\hline & A & B & C & D & E & F\\\hline A & - & - & - & 28 & - & 27\\\hline B & - & - & 16 & 14 & 29 & 18\\\hline C & - & 16 & - & 11 & 9 & -\\\hline D & 28 & 14 & 11 & - & 7 & 25\\\hline E & - & 29 & 9 & 7 & - & 13\\\hline F & 27 & 18 & - & 25 & 13 & -\\\hline\end{array}

(a) For each pair of towns with no direct road, find the length of the shortest route between them.

[4]

Use the complete table of shortest distances in the rest of the question.

(b) Use Prim's algorithm, starting at A, to find a minimum spanning tree. Write down the edges in order and the total length.

[3]

(c) Use the nearest neighbour algorithm from A to find an upper bound for a round that visits every town and returns to A.

[3]

(d) Delete B to find a lower bound.

[4]

(e) Find a round of length 105 km, and state what you can now say about the shortest round.

[3]

(f) Explain what is wrong with the route in (c) as a trip on the roads, and why its length is still an upper bound.

[4]

The van uses 0.11 litres of fuel per kilometre, and fuel costs 1.60 dollars per litre.

(g) Find the fuel cost of the round in (e).

[3]

(h) Give two reasons why the shortest round in kilometres may not be the quickest.

[2]

Show solutionHide solution

(a) AB: A to D to B, 28+14=42 [A1]; AC: A to D to C, 28+11=39 [A1]; AE: A to D to E, 28+7=35 [A1]; CF: C to E to F, 9+13=22 [A1].

(b) from A the shortest edge is AF 27 [M1]; then FE 13, ED 7, EC 9 and DB 14 [A1]; total 27+13+7+9+14=70 km [A1].

(c) from A: F (27), E (13), D (7), C (11), B (16) [M1]; then back to A, 42 [A1]; route A, F, E, D, C, B, A, 27+13+7+11+16+42=116 km [A1].

(d) delete B; the minimum spanning tree of A, C, D, E, F is DE 7, CE 9, EF 13, AF 27 [M1], weight 56 [A1]; add the two shortest edges at B, BD 14 and BC 16 [M1]; lower bound 56+30=86 km [A1].

(e) for example A, D, E, C, B, F, A [M1]: 28+7+9+16+18+27=105 [A1]; so the shortest round is between 86 and 105 km [R1].

(f) the last leg from B to A uses 42 km, but there is no direct road [R1]; the van must go by D, so D is visited twice [R1]; the tour is still a closed route that visits every town, so its length is at least the shortest such route [R1]; and the length of the real trip on the roads is also 116 km, so it is a valid upper bound [A1].

(g) 105\times0.11=11.55 litres [M1]; cost 11.55\times1.6 [M1] =18.48 dollars [A1].

(h) for example, roads differ in speed limit and traffic [R1]; deliveries may have to be made at set times, so the order is fixed by the customers and not by distance [R1].

Final answer

(a) AB 42, AC 39, AE 35, CF 22
(b) AF, FE, ED, EC, DB: 70 km
(c) A, F, E, D, C, B, A: 116 km
(d) 86 km
(e) A, D, E, C, B, F, A: 105 km, between 86 and 105
(g) 18.48 dollars.

Investigation 9

[27 marks]

This question asks you to study a server before and after an upgrade, using a two-state Markov chain.

A school server is online (O) or offline (X) each day. Before the upgrade the daily probabilities are shown in the left diagram. At the end of day 5 the server is upgraded, and from then on the probabilities are those in the right diagram.

The server is online on day 0. Let T be the transition matrix before the upgrade, with columns for today's state.

(a) Show that the eigenvalues of T are 1 and 0.4, and find P and D with T=PDP^{-1}.

[5]

(b) Hence show that the probability that the server is online on day n (up to day 5) is \frac56+\frac16(0.4)^n.

[4]

(c) Find the smallest value of n for which this probability is within 0.001 of its limit.

[3]

(d) Find the probability that the server is online on day 5.

[3]

Let U be the transition matrix after the upgrade.

(e) Find the probability that the server is online on day 8.

[4]

(f) Find the long-run probability of being offline before and after the upgrade, and the expected number of offline days in 1000 days saved by the upgrade.

[3]

(g) Explain why the probabilities for days 0 to 8 are not given by a single power of one transition matrix.

[2]

(h) Before the upgrade, find the expected length of an offline spell, and justify your answer.

[3]

Show solutionHide solution

(a) T=\begin{pmatrix}0.9&0.5\\0.1&0.5\end{pmatrix}; \det(T-\lambda I)=\lambda^2-1.4\lambda+0.4=(\lambda-1)(\lambda-0.4) [M1 A1]; eigenvector (5,1)^{\mathsf T} for \lambda=1 [A1] and (1,-1)^{\mathsf T} for \lambda=0.4 [A1]; P=\begin{pmatrix}5&1\\1&-1\end{pmatrix}, D=\begin{pmatrix}1&0\\0&0.4\end{pmatrix} [A1].

(b) T^n=PD^nP^{-1} [M1]; P^{-1}=\frac16\begin{pmatrix}1&1\\1&-5\end{pmatrix} [M1]; the top left entry is \frac16\left(5\times1\times1+1\times0.4^n\times1\right) [A1]; =\frac56+\frac16(0.4)^n [A1].

(c) the limit is \frac56, so solve \frac16(0.4)^n<0.001 [M1]; (0.4)^n<0.006, so n>\frac{\ln0.006}{\ln0.4}=5.58 [M1]; n=6 [A1].

(d) \frac56+\frac16(0.4)^5 [M1 M1] =0.835 [A1].

(e) the distribution on day 5 is (0.835,0.165) [M1]; on day 6 the online probability is 0.95\times0.835+0.7\times0.165=0.909 [M1]; on day 7 it is 0.927 [A1]; on day 8 it is 0.932 [A1].

(f) before: \frac{0.1}{0.1+0.5}=\frac16 offline; after: \frac{0.05}{0.05+0.7}=\frac1{15} [A1]; in 1000 days 166.7-66.7 [M1] =100 days saved [A1].

(g) the matrix changes at the end of day 5 [R1], so days 6 to 8 use U and not T, and T^8 would give the wrong answer [R1].

(h) an offline day is followed by another offline day with probability 0.5, independently each day [R1]; the length of the spell has a geometric distribution with p=0.5 [M1]; the expected length is \frac1{0.5}=2 days [A1].

Final answer

(a) P=\begin{pmatrix}5&1\\1&-1\end{pmatrix}, D=\mathrm{diag}(1,0.4)
(c) n=6
(d) 0.835
(e) 0.932
(f) \frac16 and \frac1{15}, 100 days saved
(h) 2 days.

Going further

Beyond the syllabus: the worked examples and investigations of the chapter's Going further pages.

Investigation

[28 marks]

Worked investigation 1: A ferry round six islands.

This question asks you to plan a ferry route that visits six islands and returns to its start, and to bound its length.

The table shows the sailing distances, in kilometres, between six islands A to F.

\begin{array}{|c|r|r|r|r|r|r|}\hline & A & B & C & D & E & F\\\hline A & - & 19 & 10 & 14 & 8 & 7\\\hline B & 19 & - & 9 & 6 & 19 & 26\\\hline C & 10 & 9 & - & 4 & 11 & 17\\\hline D & 14 & 6 & 4 & - & 13 & 21\\\hline E & 8 & 19 & 11 & 13 & - & 12\\\hline F & 7 & 26 & 17 & 21 & 12 & -\\\hline\end{array}

(a) Use Prim's algorithm, starting at A, to find a minimum spanning tree. State the order in which the edges are added and the total weight.

[4]

(b) A cable company wants to link all six islands. Explain what your answer to (a) tells the company.

[1]

The ferry must visit every island exactly once and return to A.

(c) Starting at A, apply the nearest neighbour algorithm to obtain an upper bound on the total sailing distance.

[3]

(d) Delete vertex A to obtain a lower bound on the total sailing distance.

[4]

(e) Deleting vertex B gives a lower bound of 44. Explain which of the two lower bounds is more useful.

[1]

(f) Find a route of length 57 km, and explain what can be said about the optimal route.

[3]

The ferry operator, Mrs Wu, carries 40 passengers on the 57 km route. Each passenger pays 6 dollars for every island visited plus 0.45 dollars per kilometre, and fuel costs 9.50 dollars per kilometre.

(g) Find Mrs Wu's profit for one trip, before other costs.

[3]

(h) Island F's harbour closes for repairs, so the ferry visits only A to E. Find the shortest route that visits A to E and returns to A.

[5]

(i) Explain why a lower bound found by deleting a vertex is always at most the length of the optimal route.

[4]

Show solutionHide solution

(a) from \{\mathrm{A}\} the shortest edge is \mathrm{AF}=7; add it. Then from \{\mathrm{A},\mathrm{F}\} add \mathrm{AE}=8 [M1]

then \mathrm{AC}=10 (the edge \mathrm{EC}=11 is longer), then \mathrm{CD}=4, then \mathrm{DB}=6 [A1]

order of addition: \mathrm{AF},\ \mathrm{AE},\ \mathrm{AC},\ \mathrm{CD},\ \mathrm{DB} [A1]

total weight 7+8+10+4+6=35 km [A1]

(b) the least total length of cable that links all six islands is 35 km [R1]

(c) from A the nearest island is F (7); from F, E (12); from E, C (11); from C, D (4); from D, B (6) [M1]

then back from B to A, 19: route \mathrm{A\text{-}F\text{-}E\text{-}C\text{-}D\text{-}B\text{-}A} [A1]

7+12+11+4+6+19=59 km, an upper bound [A1]

(d) delete A; the minimum spanning tree of B, C, D, E, F uses \mathrm{DC}=4,\ \mathrm{BD}=6,\ \mathrm{CE}=11,\ \mathrm{EF}=12 [M1]

weight 4+6+11+12=33 km [A1]

add the two shortest edges at A: \mathrm{AF}=7 and \mathrm{AE}=8 [M1]

lower bound 33+7+8=48 km [A1]

(e) the bound 48 is larger than 44, so it is the more useful: the optimal route lies between the larger lower bound and the smaller upper bound [R1]

(f) e.g. \mathrm{A\text{-}C\text{-}B\text{-}D\text{-}E\text{-}F\text{-}A} visits every island once [M1]

10+9+6+13+12+7=57 km [A1]

the optimal route L satisfies 48\le L\le57; the upper bound improves from 59 to 57 [R1]

(g) revenue per passenger 6\times6+0.45\times57=36+25.65=61.65 dollars [M1]

revenue 40\times61.65=2466 dollars [A1]

fuel 9.50\times57=541.50 dollars, so profit 2466-541.50=1924.50 dollars [A1]

(h) with five islands there are \frac{4!}{2}=12 different tours, each counted once when a tour and its reverse are the same [M1]

lengths: ABCDEA 53, ABCEDA 66, ABDCEA 48, ABDECA 59, ABECDA 67, ABEDCA 65, ACBDEA 46, ACBEDA 65, ACDBEA 47, ACEBDA 60, ADBCEA 48, ADCBEA 54 [A1]

the smallest length is 46 km; the next smallest is 47 km [M1]

shortest route length 46 km [A1]

route \mathrm{A\text{-}C\text{-}B\text{-}D\text{-}E\text{-}A} (10+9+6+13+8), or its reverse [A1]

(i) let T be an optimal tour; remove vertex A and its two tour edges [R1]

what remains is a path through the other five vertices; a path is a spanning tree of them, so its length is at least the minimum spanning tree weight [R1]

the two removed edges are different edges at A, so their total is at least the sum of the two shortest edges at A [R1]

adding the two inequalities, T\ge (MST of the rest) + (two shortest edges at A), which is the lower bound; this holds for any deleted vertex [R1]

Final answer

(a) AF, AE, AC, CD, DB: 35 km
(c) A-F-E-C-D-B-A: 59 km
(d) 48 km
(f) A-C-B-D-E-F-A: 57 km, so 48\le L\le57
(g) 1924.50 dollars
(h) A-C-B-D-E-A: 46 km.

Investigation

[26 marks]

Worked investigation 2: Bike, bus or walk.

This question asks you to model how commuters change their way of travelling from one day to the next.

A town has 120 commuters, each of whom cycles (B), takes the bus (U) or walks (W) each day. From one day to the next: of those who cycled, 70% cycle again, 20% take the bus and 10% walk; of those who took the bus, 25% cycle, 60% take the bus and 15% walk; of those who walked, 20% cycle, 35% take the bus and 45% walk.

(a) Draw a transition diagram and write down the transition matrix T, with columns for today's choice and rows for tomorrow's.

[3]

(b) On Monday 40 cycle, 60 take the bus and 20 walk. Find the expected numbers on Tuesday and on Wednesday.

[3]

(c) Find the probability that a commuter who cycles on Monday also cycles on Wednesday.

[2]

(d) Show that \lambda=1 is an eigenvalue of T and find the other two eigenvalues.

[4]

(e) Find the steady-state vector and interpret it for the 120 commuters.

[4]

(f) Explain, using the eigenvalues, why the numbers settle down quickly.

[2]

(g) For a commuter who cycles today, let m_B be the expected number of days until the first day they walk, and define m_U similarly. Explain why m_B=1+0.7m_B+0.2m_U and m_U=1+0.25m_B+0.6m_U.

[3]

(h) Solve these equations and interpret m_B.

[3]

(i) Give one reason why the transition probabilities might not stay constant.

[2]

Show solutionHide solution

(a) a diagram with three states B, U, W and nine labelled arrows, the probabilities leaving each state adding to 1 (Figure 13.10) [M1]

first column (from B): 0.7,\ 0.2,\ 0.1 [A1]

T=\begin{pmatrix}0.7&0.25&0.2\\0.2&0.6&0.35\\0.1&0.15&0.45\end{pmatrix} [A1]

(b) \mathbf{s}_1=T\mathbf{s}_0 with \mathbf{s}_0=(40,60,20)^{\mathsf T} [M1]

Tuesday: (47,\ 51,\ 22) [A1]

Wednesday: \mathbf{s}_2=T\mathbf{s}_1=(50.05,\ 47.7,\ 22.25), about (50.1,\ 47.7,\ 22.3) [A1]

(c) (T^2)_{BB}=0.7\times0.7+0.25\times0.2+0.2\times0.1 [M1]

0.49+0.05+0.02=0.56 [A1]

(d) \det(T-\lambda I)=0 [M1]

each column of T-I adds to 0, so its rows are linearly dependent and \det(T-I)=0: \lambda=1 [A1]

the characteristic polynomial factorises as -(\lambda-1)\left(\lambda^2-0.75\lambda+0.1325\right) [M1]

\lambda=0.465 or 0.285 (exactly \frac38\pm\frac{\sqrt{13}}{40}) [A1]

(e) solve (T-I)\mathbf{s}=\mathbf{0} with s_B+s_U+s_W=1 [M1]

\mathbf{s}=\dfrac{1}{153}(67,\ 58,\ 28)=(0.438,\ 0.379,\ 0.183) [A1]

120\mathbf{s}=(52.5,\ 45.5,\ 22.0) [A1]

in the long run about 52 or 53 commuters cycle, 45 or 46 take the bus and 22 walk on a typical day [R1]

(f) the other eigenvalues have modulus less than 1: 0.465 and 0.285 [R1]

so 0.465^n is below 0.03 after five days, and \mathbf{s}_n is close to the steady state [R1]

(g) each day contributes 1 to the waiting time, so the equation begins m_B=1+\dots [R1]

with probability 0.7 the person cycles again, and with probability 0.2 takes the bus: the remaining expected wait is again m_B or m_U [R1]

with probability 0.1 they walk, the wait ends and adds nothing; the equation for m_U is the same argument with the bus row of probabilities [R1]

(h) rearrange: 0.3m_B-0.2m_U=1 and -0.25m_B+0.4m_U=1 [M1]

m_B=\dfrac{60}{7}=8.57 and m_U=\dfrac{55}{7}=7.86 [A1]

a commuter who cycles today is expected to wait about 8.57 days before the first day they walk [R1]

(i) the probabilities probably depend on the weather or the season, which changes through the year [R1]

so one fixed matrix cannot describe both a wet month and a dry month; a model with a different matrix for each season would be needed [R1]

Final answer

(a) T=\begin{pmatrix}0.7&0.25&0.2\\0.2&0.6&0.35\\0.1&0.15&0.45\end{pmatrix}
(b) (47,51,22) and (50.1,47.7,22.3)
(c) 0.56
(d) 0.465, 0.285
(e) \frac1{153}(67,58,28), about (52.5,45.5,22.0)
(h) m_B=8.57, m_U=7.86 days.

From the book

Photon Guidebook: Mathematics HL Paper 3 for the IB Diploma

Chapter 13 teaches networks and markov chains: how the IB builds this kind of Paper 3 question, the techniques, marked worked investigations, and practice investigations like these.

About the book