PageRank as a Markov Chain: The Random Surfer Model

Markov chains and the stationary distribution

A Markov chain is a sequence of states where the probability of the next state depends only on the current one, encoded in a row-stochastic transition matrix P, with Pᵢⱼ the probability of moving from state i to state j. For the web, states are pages, and Pᵢⱼ = 1/k if page i has k outgoing links and one of them points to j. A stationary distribution π* satisfies π*·P = π* — a left eigenvector of P with eigenvalue 1 — and π*ᵢ is the long-run fraction of time the chain spends at state i, provided the chain is irreducible and aperiodic. PageRank is exactly π* for the web-surfer chain: pages with the highest stationary probability rank highest.

The random surfer and the damping factor

Picture a surfer who, at each step, clicks a uniformly random outgoing link with probability d (the damping factor, typically 0.85), or gets bored and teleports to a uniformly random page with probability (1−d). That random-jump term prevents the surfer getting permanently trapped in a subgraph with no exit and guarantees the chain is irreducible and aperiodic, so a unique stationary distribution always exists no matter how the link graph is shaped. A dangling node — a page with zero outgoing links — has its probability mass redistributed uniformly over all N pages, as if it linked to everyone; without this fix, probability mass would simply vanish from the system.

Power iteration: matrix multiplication, repeated

Rather than solving π·P = π directly — infeasible for billions of pages — PageRank uses power iteration: start from a uniform distribution and repeatedly multiply by the transition matrix until it stops changing. Each iteration costs O(E), touching every edge once, which is what makes PageRank tractable at web scale — a dense matrix multiplication would cost O(N²) and be completely infeasible. Convergence is guaranteed by the Perron-Frobenius theorem: because every entry of the damped transition matrix is at least (1−d)/N > 0, the matrix has a unique largest eigenvalue λ₁ = 1 with a strictly positive eigenvector, and repeated multiplication suppresses every other eigenvector component at a rate bounded by the damping factor d.

PR(p) = (1 − d)/N + d · Σ_(q→p) PR(q) / L(q)

d = 0.85 → ~50-100 power-iteration steps to converge
π_t = π₀·P^t → v₁ as t → ∞     (convergence rate ∝ |λ₂|^t, bounded by d)

Beyond the web

The same "random walker + stationary distribution" idea shows up wherever nodes need ranking by structural importance rather than local properties: social-network influence scores, citation-weighted paper rankings (PageRank's original bibliometric inspiration), personalised recommendation systems that bias the teleport step toward known interests, structurally central proteins in biological interaction networks, and the Metropolis-Hastings sampling that powers Markov Chain Monte Carlo methods.

Frequently asked questions

Try it live

Everything above runs in your browser — open PageRank and watch power iteration converge on a custom graph, or switch to a random-surfer simulation that arrives at the same stationary distribution. Nothing is installed, nothing is uploaded.