Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 2

Markov chains, stationary distributions and PageRank

Start the chain in one state and apply the transition matrix t times: the bars show πt = π0At, the gold marks the long-run distribution. For an irreducible, aperiodic chain the total-variation distance to the stationary distribution decays geometrically at a rate set by the second-largest eigenvalue modulus; PageRank adds random jumps with probability 1 − p so that the rate is at most p. A periodic or reducible chain shows what goes wrong.

Chain

Start in state

Steps t

Try these

States are numbered from 1. The 500-page web is a simulated stand-in for the book's Harvard web graph; on it the contraction per step is much smaller than p, but on the 30-page cycle it equals p. For the PageRank chains the walk follows a link uniformly with probability p and jumps to a uniformly random page otherwise; a page with no links always jumps.

In the lecture notes