Random walks and page rank Problem set B

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.

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

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.

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.
2. (b) Find the proportion of time spent at vertex B in the long run. Give your answer to 3 significant figures.

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.
2. (b) Write down one new arrow that makes the graph strongly connected.
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?

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.
2. (b) Find the probability that the walker is at E after 6 moves, starting at B.
3. (c) The walk continues for a very long time. At which vertex is the walker found most often?

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.
2. (b) Rank the pages from the most to the least important.

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.
2. (b) A person starts on page A. Find the probability that they are on page A after 3 steps.

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.
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.
3. (c) Does the second model change the order of the pages? Explain.