Random walks and page rank Problem set A Answers

\(M=\begin{pmatrix}0 & \frac{1}{3} & \frac{1}{4} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{3} & 0 & \frac{1}{2} & 1 \\ 0 & \frac{1}{3} & \frac{1}{4} & 0 & 0 \\ 0 & 0 & \frac{1}{4} & 0 & 0\end{pmatrix}\) (order A, B, C, D, E)

1. (a) Edges: AB (14), AC (9), BC (11), BE (10), CD (7), DE (12)
2. (b) \(M=\begin{pmatrix}0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{3} & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{3} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{1}{2} \\ 0 & \frac{1}{3} & 0 & \frac{1}{2} & 0\end{pmatrix}\)

0.250 (25.0%)

1. (a) \(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}\) (order A, B, C, D)
2. (b) 0.333

1. (a) There is no route from D to A: from D you can only reach D and E.
2. (b) Any arrow from D or E to a page outside them, for example E → A.
3. (c) Only D and E

1. (a) \(M=\begin{pmatrix}0 & \frac{1}{4} & 0 & 0 & 0 \\ 1 & 0 & \frac{1}{3} & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{4} & \frac{1}{3} & 0 & 0 \\ 0 & \frac{1}{4} & \frac{1}{3} & 0 & 0\end{pmatrix}\) (order A, B, C, D, E)
2. (b) 0.118
3. (c) B (0.333 of the time)

1. (a) \(M=\begin{pmatrix}0 & \frac{1}{2} & 0 & 0 & 1 \\ \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0\end{pmatrix}\) (order A, B, C, D, E)
2. (b) B > A > D > C > E

1. (a) \(N=\begin{pmatrix}0 & 0.45 & 0 & 0 & 0 \\ 0 & 0 & 0.9 & 0.45 & 0 \\ 0 & 0 & 0 & 0.45 & 0 \\ 0.9 & 0.45 & 0 & 0 & 0 \\ 0.1 & 0.1 & 0.1 & 0.1 & 1\end{pmatrix}\) (order A, B, C, D, End)
2. (b) 0.3645

1. (a) D > A > B > C
2. (b) A = 0.109, B = 0.0763, C = 0.0327, D = 0.131
3. (c) No: the order is still D > A > B > C.