PageRank as the stationary distribution of a random surfer
Statement
Let be the all-ones matrix ( = number of web pages) and let be the row-stochastic link matrix (page links equally to each page it points to; pages with no outlink are sent uniformly to all pages). For any damping factor , the Google matrix is the transition matrix of an irreducible, aperiodic Markov chain, so by the fundamental theorem above it has a unique stationary distribution with — this is exactly the PageRank vector, and the power-iteration algorithm 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 , every entry of is strictly positive (), 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 is irreducible.
Aperiodicity. A chain where every state can go directly to every state (including itself, since too) has return times of every length available, whose greatest common divisor is 1; so is aperiodic.
Existence, uniqueness, convergence. is row-stochastic by construction (a convex combination of two row-stochastic matrices and 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 exists with , and converges entrywise to a matrix with every row equal to .
Power iteration. Since for any starting distribution , and every row of converges to as , the weighted average converges to as well — this is precisely why repeatedly applying 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
- David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
- Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
- James R. Norris (1997). Markov Chains