Random walks and page rank Problem set A

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.

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

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.

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

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

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.
2. (b) Find the probability that the walker is at D after 5 moves, starting at A.
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 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.
2. (b) Rank the pages from the most to the least important.

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

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