Markov chains and how Google ranked the web
Before this sheet: Matrices that move the plane and Conditional probability and trees.
Tonight's idea
In a Markov chain the next state depends only on the current one, not on the history.
Three states, Sunny, Cloudy, Rainy. Tomorrow's probabilities given today, one row per today, one column per tomorrow:
\[ P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.4 & 0.4 \end{pmatrix} \quad \begin{matrix} \text{from S} \\ \text{from C} \\ \text{from R} \end{matrix} \]Every row adds to 1. Two days ahead: sunny today, rain the day after tomorrow? Add up the routes through tomorrow: \(0.7 \times 0.1 + 0.2 \times 0.3 + 0.1 \times 0.4 = 0.17\). That is row S times column R. Two days is \(P^2\), \(n\) days \(P^n\).
Whatever you start from, the rows of \(P^n\) settle to the same vector, called \(\pi\) (a Greek letter here, not 3.14). This steady state satisfies \(\pi P = \pi\) (multiply the row \(\pi\) by \(P\) and you get \(\pi\) back: tomorrow's shares equal today's). Here \(\pi = \left(\tfrac{6}{13}, \tfrac{4}{13}, \tfrac{3}{13}\right)\), so 46% of days are sunny in the long run.
The random surfer. A page is important when important pages link to it. Make that a Markov chain: a surfer clicks a random link on each page; the steady state is the fraction of time she spends on each page, and that is PageRank. With probability \(1 - d = 0.15\) she types a random address instead. For \(N\) pages,
\(\displaystyle PR(p) = \frac{1 - d}{N} + d \sum_{q \to p} \frac{PR(q)}{\text{out}(q)}\), summing over pages \(q\) linking to \(p\), where \(\text{out}(q)\) is the number of links on \(q\).
Watch one: solving for the steady state
We want \(\pi = (a, b, c)\) with \(\pi P = \pi\) and \(a + b + c = 1\). Column by column:
\[ 0.7a + 0.3b + 0.2c = a, \qquad 0.2a + 0.4b + 0.4c = b, \qquad 0.1a + 0.3b + 0.4c = c. \]One equation is redundant (rows add to 1): drop the third and use \(a + b + c = 1\). The first gives \(b = a - \tfrac23 c\). In the second: \(0.2a - 0.6\left(a - \tfrac23 c\right) + 0.4c = 0\), so \(a = 2c\), and then \(b = \tfrac43 c\). Sum: \(\tfrac{13}{3}c = 1\), so \(c = \tfrac{3}{13}\), \(a = \tfrac{6}{13}\), \(b = \tfrac{4}{13}\).
Your turn
- A machine is Working or Broken. Each day a working machine breaks with probability 0.1 and a broken one is repaired with probability 0.6. Write the \(2 \times 2\) transition matrix and find the steady state. What fraction of days is it broken?
- Sunny today. Compute the whole first row of \(P^2\) (sunny, cloudy, rainy in two days).
- Cloudy today. What is the probability of sunshine in two days? Compare with the one-day value 0.3 and with \(6/13\).
- A three-page web: A links to B and C, B links to C, C links to A (demo: mathdetours.com/demos/pagerank.html). With the pure surfer (\(d = 1\)), writing \(r_A, r_B, r_C\) for the long-run shares of time on each page, the ranks satisfy \(r_A = r_C\), \(r_B = \tfrac12 r_A\), \(r_C = \tfrac12 r_A + r_B\). Solve them, given the ranks add to 1.
Stretch: how long until two heads in a row?
Toss a fair coin until you see HH. States: 0 (no progress), 1 (last toss a head), Done. With \(E_0, E_1\) the expected tosses still needed, \(E_0 = 1 + \tfrac12 E_1 + \tfrac12 E_0\) and \(E_1 = 1 + \tfrac12 E_0\). Solve for \(E_0\). Then do the same for the pattern HT. Which takes longer, and why?
Answers
- \(P = \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix}\). \(0.9w + 0.6b = w\) gives \(w = 6b\); with \(w + b = 1\), \(b = \tfrac17\). Broken about 14% of days.
- Sunny \(0.49 + 0.06 + 0.02 = 0.57\); cloudy \(0.14 + 0.08 + 0.04 = 0.26\); rainy \(0.17\). Sum 1. ✓
- \(0.3(0.7) + 0.4(0.3) + 0.3(0.2) = 0.39\), already much closer to 0.46 than 0.3 is. Each multiplication by \(P\) dilutes the starting state until only \(\pi\) is left.
- \(r_C = \tfrac12 r_A + \tfrac12 r_A = r_A\); sum \(\tfrac52 r_A = 1\), so \(r_A = \tfrac25\), \(r_B = \tfrac15\), \(r_C = \tfrac25\). B is lowest because its only incoming vote is half of A's.
Stretch. Substitute \(E_1 = 1 + \tfrac12 E_0\): \(E_0 = \tfrac32 + \tfrac34 E_0\), so \(E_0 = 6\) tosses. For HT, from state 1 a tail finishes and a head keeps you there: \(E_1 = 1 + \tfrac12 E_1\), so \(E_1 = 2\), and then \(E_0 = 4\). HH takes longer because a failure costs more: a tail after a head sends you back to zero, whereas while waiting for HT an extra head leaves you still one toss from done.