PageRank as a Markov chain: the random surfer and the stationary distribution

Markov chains: states and transitions

A Markov chain is a sequence of states where the probability of moving to the next state depends only on the current state, not on the history that led there — the Markov property. Formally, a chain over states {1, …, n} is defined by a transition matrix P where P_ij is the probability of moving from state i to state j:

For the web, the "states" are pages, and Pᵢⱼ is the probability that a surfer on page i clicks a link to page j. If page i has k outgoing links, the simplest model assigns Pᵢⱼ = 1/k for each linked page j, and 0 otherwise.

The stationary distribution

Let π be a row vector where πᵢ is the probability of being in state i. After one step, the new distribution is π·P. A stationary distribution π* is a fixed point of this transformation:

π*ᵢ is the long-run fraction of time the chain spends in state i, regardless of the starting state — provided the chain is irreducible (every state reachable from every other) and aperiodic (no rigid cycle length). PageRank is exactly π* for the "web surfer" chain: the pages with the highest stationary probability are ranked highest.

The random surfer model

Picture a surfer who, at each step, either (a) clicks a uniformly random outgoing link with probability d (the damping factor, typically 0.85), or (b) gets bored and jumps to a uniformly random page anywhere on the web with probability (1 − d). This gives the full PageRank transition:

The random jump term prevents the surfer from getting permanently trapped in a subgraph with no way out, and guarantees the chain is irreducible and aperiodic — so a unique stationary distribution exists no matter how the web graph is shaped.

Dangling nodes and the damping factor

A dangling node is a page with zero outgoing links (a PDF, an image, a dead end). Without special handling, all its probability mass simply vanishes from the system, and the rows of P no longer sum to 1. The standard fix redistributes a dangling page's mass uniformly over all N pages, as if it linked to everyone:

Power iteration in JavaScript

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.

function pageRank(adjacency, d = 0.85, iterations = 100, tol = 1e-9) {
  const N = adjacency.length;
  const outDegree = adjacency.map(links => links.length);
  let pr = new Float64Array(N).fill(1 / N);

  for (let iter = 0; iter < iterations; iter++) {
    const next = new Float64Array(N).fill((1 - d) / N);

    // Redistribute dangling-node mass uniformly over all N pages
    let danglingMass = 0;
    for (let i = 0; i < N; i++)
      if (outDegree[i] === 0) danglingMass += pr[i];
    const danglingShare = d * danglingMass / N;

    // Distribute each page's rank across its outgoing links
    for (let i = 0; i < N; i++) {
      if (outDegree[i] === 0) continue;
      const share = d * pr[i] / outDegree[i];
      for (const j of adjacency[i]) next[j] += share;
    }
    for (let j = 0; j < N; j++) next[j] += danglingShare;

    // Check L1 convergence
    let delta = 0;
    for (let j = 0; j < N; j++) delta += Math.abs(next[j] - pr[j]);
    pr = next;
    if (delta < tol) break;
  }
  return pr; // pr[i] ≈ π*ᵢ, sums to 1
}

Why it converges: Perron-Frobenius

Power iteration converges because of the Perron-Frobenius theorem: a matrix with all positive entries (which the damped, teleporting transition matrix is, since every entry is at least (1−d)/N > 0) has a unique largest eigenvalue λ₁ = 1, and its eigenvector is strictly positive. Repeatedly applying the matrix suppresses all other eigenvector components geometrically, at a rate governed by |λ₂/λ₁|:

This is exactly why the damping factor matters for convergence speed: it directly bounds the second-largest eigenvalue, so a smaller d converges faster (but ranks more uniformly), while a larger d preserves link structure but converges more slowly.

Beyond the web: other applications

The same "random walker + stationary distribution" idea shows up across computer science and beyond, wherever you need to rank nodes in a graph by structural importance rather than local properties:

• Social network influence: ranking accounts by how often a random "follower walk" lands on them.
• Citation networks: ranking papers by citation-weighted importance (the original inspiration for PageRank, from bibliometrics).
• Recommendation systems: personalised PageRank biases the teleport step toward a user's known interests instead of uniform restart.
• Protein interaction networks: identifying structurally central proteins in biological graphs.
• Markov Chain Monte Carlo (MCMC): the same stationary-distribution machinery underlies Metropolis-Hastings sampling.