Random walks and page rank Problem set B One question at a time

A robot cleaner moves between five rooms joined by doorways, as shown. In each room it chooses one of the doorways of that room at random, each equally likely, and goes through it. Write down the transition matrix for the robot's walk.

• Degrees: A = 2, B = 3, C = 1, D = 3, E = 3
• Column of a vertex: 1 ÷ its degree in every row it is joined to, 0 elsewhere.
• Columns are 'from', rows are 'to'. Each column adds to 1.

The table shows the lengths, in km, of the cycle paths between five villages. A dash means there is no path.

1. (a) Draw the weighted graph.

   • The table is symmetric, so read each edge once from the entries above the diagonal.
   • Draw A, B, C, D, E and join them: AB (8), AE (13), BC (6), BD (15), CD (9), DE (11).
   • Write each weight on its edge.

2. (b) A cyclist rides between the villages. At each village she chooses one of the paths from that village at random, each equally likely. Write down the transition matrix.

   • Degrees: A = 2, B = 3, C = 2, D = 3, E = 2. The weights do not matter: every edge at a vertex is equally likely.
   • Column = the vertex you leave: 1 ÷ degree in each row joined to it.

A frog jumps between four lily pads. From each pad it jumps to one of the pads joined to it by a line in the graph, chosen at random, each equally likely. In the long run, find the proportion of jumps that land on pad D. Give your answer to 3 significant figures.

• Degrees: A = 1, B = 2, C = 2, D = 3. Build M: column = from, each entry 1 ÷ degree.
• From the calculator: M^50 has every column (0.125, 0.25, 0.25, 0.375)
• Row D: 0.375
• Check: 3/8 = 0.375

A cyclist rides around four parks along one-way cycle tracks, as shown. At each park she chooses one of the tracks leaving that park at random, each equally likely.

1. (a) Write down the transition matrix.

   • Arrows leaving: A = 1, B = 1, C = 2, D = 2
   • Column = the vertex it leaves: 1 ÷ (arrows leaving) in each row it points to.
   • Each column adds to 1.

2. (b) Find the proportion of time spent at vertex B in the long run. Give your answer to 3 significant figures.

   • From the calculator: M^50 has every column (0.25, 0.25, 0.167, 0.333)
   • Row B: 0.250

The directed graph shows the one-way streets between five junctions of a town. A driver at a junction takes one of the streets leaving it at random.

1. (a) Show that the graph is not strongly connected.

   • From C the arrows lead only to D.
   • From D the arrow leads only to E, and from E only back to C.
   • So from C you can only reach C, D and E, never A, and the graph is not strongly connected.

2. (b) Write down one new arrow that makes the graph strongly connected.

   • The group C, D, E has no street out.
   • A street from the group to the rest fixes it: E → A.
   • Check: from every junction you can now reach every other junction.

3. (c) A driver starts at junction A and keeps driving along the streets at random for a very long time. Which junctions can the driver be at in the long run?

   • Once the driver reaches C they cannot leave C, D and E.
   • From A the driver reaches the group sooner or later.
   • In the long run the driver is only at C, D and E.

Five islands are joined by ferries. Every day a tourist takes one of the ferries from the island she is on, chosen at random, each equally likely, to the next island.

1. (a) Write down the transition matrix.

   • Degrees: A = 2, B = 4, C = 1, D = 2, E = 3
   • Column = from: 1 ÷ degree in each row joined to it.

2. (b) Find the probability that the walker is at E after 6 moves, starting at B.

   • From the calculator: M^6, column B (start), row E (finish): 0.266

3. (c) The walk continues for a very long time. At which vertex is the walker found most often?

   • M^50 has every column (0.167, 0.333, 0.0833, 0.167, 0.25)
   • The largest is vertex B: the vertex with the most edges.

The directed graph shows the links between five blog posts. A reader on a post clicks one of the links on it at random, each equally likely.

1. (a) Write down the transition matrix.

   • Arrows leaving: A = 1, B = 2, C = 2, D = 2, E = 2
   • Column = the page you are on: 1 ÷ links on that page in each row it links to.

2. (b) Rank the pages from the most to the least important.

   • From the calculator: M^50 has every column (0.267, 0.2, 0.333, 0.0667, 0.133)
   • Largest first: C = 0.333, A = 0.267, B = 0.2, E = 0.133, D = 0.0667

The directed graph shows the links between four pages of a news site. A reader on a page clicks one of its links at random, each equally likely, but at each step there is a probability of 0.1 that they close the site instead.

1. (a) Add a state End. Write down the new transition matrix.

   • Arrows leaving: A = 1, B = 1, C = 2, D = 2
   • Each page column: 0.1 in the End row, and 0.9 ÷ (links) in each row it links to.
   • End column: 1 in the End row, 0 elsewhere.

2. (b) A person starts on page A. Find the probability that they are on page A after 3 steps.

   • From the calculator: N^3, column A, row A: 0.3645 (0.365 to 3 significant figures)

The directed graph shows the links between four pages of a travel blog. A reader on a page clicks one of its links at random, each equally likely.

1. (a) Use the long-run probabilities to rank the four pages.

   • Arrows leaving: A = 2, B = 1, C = 2, D = 1
   • From the calculator: M^50 has every column (0.2, 0.1, 0.4, 0.3)
   • Order: C = 0.4, D = 0.3, A = 0.2, B = 0.1

2. (b) In a second model, at each step the person stops with probability 0.1. A person starts on page A. Find the probability of being on each page after 10 steps in this model.

   • Build the 5 × 5 matrix N: 0.9 × the old column entries, 0.1 into End, End to End = 1.
   • From the calculator: N^10, column A, rows A to D: (0.0654, 0.0327, 0.153, 0.0981)

3. (c) Does the second model change the order of the pages? Explain.

   • Order after 10 steps: C = 0.153, D = 0.0981, A = 0.0654, B = 0.0327
   • Every step multiplies the page probabilities by 0.9, so every page is scaled by the same factor 0.9^10 and the order cannot change.