MathLabs
TheoremProved

PageRank as the stationary distribution of a random surfer

Statement

Let JJ be the N×NN\times N all-ones matrix (NN = number of web pages) and let PP be the row-stochastic link matrix (page ii links equally to each page it points to; pages with no outlink are sent uniformly to all pages). For any damping factor d∈(0,1)d\in(0,1), the Google matrix G=dP+(1−d)1NJG=dP+(1-d)\tfrac1N J is the transition matrix of an irreducible, aperiodic Markov chain, so by the fundamental theorem above it has a unique stationary distribution π\pi with π=π(dP+(1−d)1NJ)\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big) — this π\pi is exactly the PageRank vector, and the power-iteration algorithm πk+1=πkG\pi_{k+1}=\pi_k G converges to it from any starting guess.

Why is it true?

This turns the vague idea "important pages are linked to by other important pages" into a well-posed fixed-point problem with a guaranteed unique solution, and it explains why simply repeating "spread rank along links" (power iteration) is guaranteed to work rather than oscillate or diverge.

Proof sketch

Irreducibility. Because 1−d>01-d>0, every entry of GG is strictly positive (Gij≥(1−d)/N>0G_{ij}\ge(1-d)/N>0), so from any page there is a positive-probability direct jump to any other page in one step — the underlying graph is trivially strongly connected, hence GG is irreducible.

Aperiodicity. A chain where every state can go directly to every state (including itself, since Gii>0G_{ii}>0 too) has return times of every length 1,2,3,…1,2,3,\dots available, whose greatest common divisor is 1; so GG is aperiodic.

Existence, uniqueness, convergence. GG is row-stochastic by construction (a convex combination dP+(1−d)1NJdP+(1-d)\tfrac1N J of two row-stochastic matrices PP and J/NJ/N is row-stochastic), and it is irreducible and aperiodic as just shown, so the fundamental theorem of finite Markov chains applies directly: a unique stationary π\pi exists with π=π(dP+(1−d)1NJ)\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big), and GnG^n converges entrywise to a matrix with every row equal to π\pi.

Power iteration. Since πk=π0Gk\pi_k=\pi_0G^k for any starting distribution π0\pi_0, and every row of GkG^k converges to π\pi as k→∞k\to\infty, the weighted average π0Gk\pi_0G^k converges to π\pi as well — this is precisely why repeatedly applying πk+1=πkG\pi_{k+1}=\pi_k G from an arbitrary starting rank (commonly the uniform distribution) converges to the true PageRank vector.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
  2. Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
  3. James R. Norris (1997). Markov Chains