AHL 1.7 Random walks, transition matrices and page rank · AI HL · AHL 1: Graph Theory

AHL 1.7

Random walks, transition matrices and page rank

AHL 1.7

Random walks, transition matrices and page rank

By the end of this section

Key points

The transition matrix

In a random walk you move along one of the edges at your vertex, each equally likely. The probability of an edge is 1 ÷ the number of edges you can take from that vertex.
In a transition matrix the columns are the vertices you leave and the rows are the vertices you reach. This is the other way round from an adjacency table.
Each column adds to 1. In an undirected graph count the degree. In a directed graph count only the arrows leaving the vertex.
A vertex with no loop has 0 on the diagonal.

Powers and the long run

The entry in row j, column i of \(M^n\) is the probability of being at vertex j after n moves, starting at vertex i.
For a very long walk, take a high power such as \(M^{50}\). All the columns become the same: the entries are the long-run proportions of time at each vertex.
Use decimals on the calculator. Check that \(M^{51}\) gives the same entries to 3 significant figures.
In an undirected graph the long-run proportion at a vertex is its degree ÷ the sum of the degrees. This is a check, not the method for a directed graph.

Web pages and a stop state

Pages are vertices and links are arrows. A random surfer clicks a link at random. The page with the largest long-run proportion ranks first.
To model stopping, add an End state. Each page column has 0.1 in the End row and 0.9 shared across its links. The End column has 1 in the End row.
Each step multiplies the probabilities of the pages by 0.9, so the order of the pages after n steps does not change.
Compare models by writing the order of the pages from each and saying what is the same and what is different.

Strongly connected graphs

A directed graph is strongly connected if you can get from every vertex to every other vertex by following the arrows.
The long-run proportions need a strongly connected graph. A vertex with no arrow out has a column that cannot add to 1. A group of vertices with no arrow out of the group traps the walk.
To check, list the vertices you can reach from each vertex. Every list must contain all the vertices.
To repair a graph, add an arrow from the trapped vertex or group back to the rest.

On the calculator

Entering a transition matrix

Enter the matrix with the vertices in the same order for the rows and the columns.
Check each column adds to 1.
Use decimals: they are faster for high powers than fractions.

Screenshot and video to come

Matrix powers

Type the matrix to a power: M^4 for 4 moves.
Read the entry with row = where you finish and column = where you start.

Screenshot and video to come

The long-run proportion

Raise M to a high power, such as 50.
Check M^51 gives the same numbers to 3 significant figures.
Read any column: they are all the same. The entry in the row of a vertex is its long-run proportion.

Screenshot and video to come

Explore: a random walk on web pages

A robot sits on a page and follows one of its links, each link equally likely. Choose the start page, then press Next step and watch the probabilities settle.

Pages

Start on page

Bars: where the robot is after step . Dashed lines: the steady state.

Transition matrix M. Columns are the page you leave, rows are the page you reach. Each column adds to 1.

The last six steps

Steady state, ranked

Choose a start page, then press Next step.

Before you press anything: starting on A, which page will the robot most likely be on after one step? Press Next step to check.
Change the start page and press 10 steps. What changes about the bars, and what does not?
The steady state does not depend on the start. Why is that a good way to rank pages?
Look at the matrix and the ranking. Which page has the most links pointing at it? Is it the one that ranks first?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.

A transition matrix for a random walk

A beetle walks on the graph. At each vertex it chooses one of the edges at that vertex at random, with each edge equally likely, and walks along it to the next vertex. Write down the transition matrix M. The columns are the vertex it leaves.

Working

Count the edges
Degrees: A = 3, B = 3, C = 2, D = 4, E = 2

The beetle leaves a vertex along one of its edges. Each is equally likely, so each has probability 1 divided by the degree.
Fill each column
Column C: 1/2 in each row joined to C, 0 in the others

Column = the vertex it leaves. Row = the vertex it reaches. There are no loops, so the diagonal is 0.
The matrix
M = \(\begin{pmatrix}0 & \frac{1}{3} & 0 & \frac{1}{4} & \frac{1}{2} \\ \frac{1}{3} & 0 & \frac{1}{2} & \frac{1}{4} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{1}{4} & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{3} & 0 & 0 & \frac{1}{4} & 0\end{pmatrix}\)

Check each column adds to 1. Unlike an adjacency matrix, the 'from' vertices are along the top.

The long-run proportion of time

The beetle in the last example walks for a very long time. Find the proportion of time it spends at vertex D.

Working

The matrix
M = \(\begin{pmatrix}0 & \frac{1}{3} & 0 & \frac{1}{4} & \frac{1}{2} \\ \frac{1}{3} & 0 & \frac{1}{2} & \frac{1}{4} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{1}{4} & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{3} & 0 & 0 & \frac{1}{4} & 0\end{pmatrix}\)

Use the matrix from before.
A high power
From the calculator: M^50 = a matrix with every column (0.214, 0.214, 0.143, 0.286, 0.143)

Use decimals. Check M^51 gives the same numbers to 3 significant figures: then the walk has settled.
Read the row
Row D: 0.286

Every column is the same, so it does not matter where the beetle starts. The proportion of time at D is 0.286, or 28.6%.
Check with the degrees
deg(D) ÷ (sum of degrees) = 4/14

For an undirected graph the long-run proportion is the vertex's degree over the sum of the degrees.

Can the walk go on for ever?

The directed graph shows the links between four web pages. A visitor on a page clicks one of the links on it at random, each equally likely. Explain why the long-run proportions cannot be found for this graph. One arrow is added from D to A. Write down the transition matrix for the new graph and find the proportion of time spent on page D in the long run.

Working

Arrows leaving each page
A 2, B 1, C 2, D 0

Page D has no link out. Its column cannot add to 1, so there is no transition matrix.
Strongly connected?
From D you can reach: no other page

A directed graph is strongly connected if you can get from every vertex to every other vertex by following the arrows. Once the visitor is on D they cannot leave, so this graph is not strongly connected.
Repair
Add D → A

Now D has one arrow out, and from D you can reach every other page: D–A–B–C.
The matrix
M = \(\begin{pmatrix}0 & 0 & \frac{1}{2} & 1 \\ \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0\end{pmatrix}\)

Column = the page the visitor leaves. Order A, B, C, D. Each column adds to 1.
A high power
From the calculator: M^50 has every column (0.333, 0.167, 0.333, 0.167)

Use decimals. Check that M^51 agrees.
Read the row
Row D: 0.167

The long-run proportion of time on page D.

Long-run time on a directed graph

A robot moves along the arrows of the directed graph. At each vertex it chooses one of the arrows leaving that vertex at random, with each arrow equally likely. Write down the transition matrix and find the proportion of time the robot spends at vertex D in the long run.

Working

Arrows leaving each vertex
Arrows leaving: A = 2, B = 1, C = 1, D = 2

Divide each column by the number of arrows leaving that vertex. Here the walk follows arrows, so use the arrows leaving, not the edges.
The matrix
M = \(\begin{pmatrix}0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 1 & 0 & 0 \\ \frac{1}{2} & 0 & 1 & 0\end{pmatrix}\)

Column = the vertex the robot leaves. Each column adds to 1.
A high power
From the calculator: M^50 has every column (0.167, 0.25, 0.25, 0.333)

Use decimals. Check that M^51 agrees.
Read the row
Row D: 0.333

The long-run proportion of time at that vertex.

After n moves

The beetle starts at vertex A. Use the matrix M from the first example to find the probability that it is at vertex D after 4 moves.

Working

Four moves
M^4

Each move multiplies by M, so after 4 moves use the fourth power.
From the calculator
M^4 = \(\begin{pmatrix}0.262 & 0.167 & 0.251 & 0.214 & 0.177 \\ 0.167 & 0.262 & 0.177 & 0.214 & 0.251 \\ 0.167 & 0.118 & 0.182 & 0.127 & 0.135 \\ 0.285 & 0.285 & 0.255 & 0.317 & 0.255 \\ 0.118 & 0.167 & 0.135 & 0.127 & 0.182\end{pmatrix}\)

Rows are 'to', columns are 'from'. The calculator shows the matrix row by row.
Pick the entry
Column A (start), row D (finish): 0.285

Start = column, finish = row.

Ranking web pages

The directed graph shows the links between four web pages. A person browses by clicking on one of the links on the page they are on, chosen at random. Use a transition matrix to rank the pages from the most to the least important.

Working

Links from each page
Arrows leaving: A = 2, B = 1, C = 2, D = 1

A link is an arrow. Each column is shared equally between the links on that page.
The matrix
M = \(\begin{pmatrix}0 & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 1 & 0 & 1 \\ \frac{1}{2} & 0 & 0 & 0\end{pmatrix}\)

Column = the page you are on. Row = the page you move to.
A high power
From the calculator: M^50 has every column (0.2, 0.3, 0.4, 0.1)

Check M^51 agrees. These are the long-run proportions of time on each page.
Rank them
C > B > A > D (C = 0.4, B = 0.3, A = 0.2, D = 0.1)

The page with the largest long-run probability ranks first. Page C comes top.

A stop state

In a second model of the same four pages, at every step the person stops browsing with probability 0.1. Otherwise they click a link at random, as before. Add a fifth state, End, and write down the new transition matrix. Then find the probability that a person who starts on page A is on page C after 2 steps.

Working

The stop state
Each page column: 0.1 to End, and 0.9 shared over its links

With probability 0.9 the person goes on and clicks a link: multiply the old probabilities by 0.9.
The End column
End → End = 1

Once the search has stopped, it stays stopped.
The matrix
N = \(\begin{pmatrix}0 & 0 & 0.45 & 0 & 0 \\ 0.45 & 0 & 0.45 & 0 & 0 \\ 0 & 0.9 & 0 & 0.9 & 0 \\ 0.45 & 0 & 0 & 0 & 0 \\ 0.1 & 0.1 & 0.1 & 0.1 & 1\end{pmatrix}\) (order A, B, C, D, End)

Each column still adds to 1.
Two steps
From the calculator: N^2, column A, row C: 0.810

Start = column, finish = row. The answer is smaller than before because some people have stopped.

Do the two models agree?

Use both models of the four pages (links only, and links with a stop probability of 0.1). A person starts on page A. Compare the probabilities of being on each page after 10 steps. Does the new model change the order of the pages?

Working

Old model
From M^10, column A: (0.188, 0.281, 0.438, 0.0938)

Order: C > B > A > D.
New model
From N^10, column A, rows A to D: (0.0654, 0.0981, 0.153, 0.0327)

Use the first four rows. The fifth row is End.
Compare
Order: C > B > A > D

The new model gives the same order.
Why
Each new value is 0.9^10 × the old value = 0.349 × the old value

Every step multiplies the four page probabilities by 0.9. The same factor on every page cannot change the order.

Menu

Graph Theory

Random walks, transition matrices and page rank

By the end of this section

Key points

The transition matrix

Powers and the long run

Web pages and a stop state

Strongly connected graphs

On the calculator

Entering a transition matrix

Matrix powers

The long-run proportion

Explore: a random walk on web pages

Worked examples

A transition matrix for a random walk

Working

The long-run proportion of time

Working

Can the walk go on for ever?

Working

Long-run time on a directed graph

Working

After n moves

Working

Ranking web pages

Working

A stop state

Working

Do the two models agree?

Working

Choose a skill

Quiz