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

A mouse is in a maze of five chambers joined by tunnels, as shown. At each chamber the mouse chooses one of the tunnels from that chamber at random, each equally likely, and runs along it. Write down the transition matrix for the mouse's walk.

• Degrees: A = 2, B = 3, C = 4, D = 2, E = 1
• 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 distances, in km, along the roads between five towns. A dash means there is no road.

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 (14), AC (9), BC (11), BE (10), CD (7), DE (12).
   • Write each weight on its edge.

2. (b) A traveller moves between the towns. At each town she chooses one of the roads from that town at random, each equally likely. Write down the transition matrix.

   • Degrees: A = 2, B = 3, C = 3, D = 2, 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 rumour is passed between four friends. Each person who hears it passes it on to one of their friends, chosen at random, each equally likely. The graph shows who is friends with whom. In the long run, find the proportion of times the rumour is with friend C. Give your answer to 3 significant figures.

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

A drone flies between four hubs along one-way air corridors, as shown. At each hub it chooses one of the corridors leaving that hub at random, each equally likely.

1. (a) Write down the transition matrix.

   • Arrows leaving: A = 2, B = 1, C = 2, D = 1
   • 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 A in the long run. Give your answer to 3 significant figures.

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

The directed graph shows the links between five pages of a school website. A visitor on a page clicks one of the links on it at random.

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

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

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

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

3. (c) A visitor starts on page A and keeps clicking links at random for a very long time. Which pages can the visitor be on in the long run?

   • Once the visitor reaches D they cannot leave D and E.
   • From A the visitor reaches the group sooner or later.
   • In the long run the visitor is only on D and E.

Five galleries of a museum are joined by doors. Every ten minutes a visitor walks through one of the doors of the gallery she is in, chosen at random, each equally likely, to the next gallery.

1. (a) Write down the transition matrix.

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

2. (b) Find the probability that the walker is at D after 5 moves, starting at A.

   • From the calculator: M^5, column A (start), row D (finish): 0.118

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.0833, 0.333, 0.25, 0.167, 0.167)
   • The largest is vertex B: the vertex with the most edges.

The directed graph shows the links between five pages on a school website. A visitor on a page clicks one of the links on it at random, each equally likely.

1. (a) Write down the transition matrix.

   • Arrows leaving: A = 2, B = 2, C = 2, D = 2, E = 1
   • 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.25, 0.3, 0.15, 0.2, 0.1)
   • Largest first: B = 0.3, A = 0.25, D = 0.2, C = 0.15, E = 0.1

The directed graph shows the links between four pages of an online shop. A visitor 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 leave the shop instead.

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

   • Arrows leaving: A = 1, B = 2, C = 1, 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 B after 3 steps.

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

The directed graph shows the links between four pages of a recipe site. A visitor 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 = 1, B = 2, C = 1, D = 2
   • From the calculator: M^50 has every column (0.3, 0.2, 0.1, 0.4)
   • Order: D = 0.4, A = 0.3, B = 0.2, C = 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.109, 0.0763, 0.0327, 0.131)

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

   • Order after 10 steps: D = 0.131, A = 0.109, B = 0.0763, C = 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.