Random walks and page rank Problem set B Answers

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

1. (a) Edges: AB (8), AE (13), BC (6), BD (15), CD (9), DE (11)
2. (b) \(M=\begin{pmatrix}0 & \frac{1}{3} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{3} & 0\end{pmatrix}\)

0.375 (37.5%)

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

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

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

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

1. (a) \(N=\begin{pmatrix}0 & 0.9 & 0 & 0 & 0 \\ 0 & 0 & 0.45 & 0.45 & 0 \\ 0 & 0 & 0 & 0.45 & 0 \\ 0.9 & 0 & 0.45 & 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) C > D > A > B
2. (b) A = 0.0654, B = 0.0327, C = 0.153, D = 0.0981
3. (c) No: the order is still C > D > A > B.