Math
Random walks and PageRank
Follow probability mass through a directed graph and compare power iteration with a crowd of random walkers. Teleportation can make PageRank converge to a unique distribution. Compare a periodic cycle with a graph whose unpatched dangling nodes leak mass.
What happens
The bars show the distribution at the current step; the thin bars show an ensemble of walkers. These are not the fraction of time spent at each node by one walker. On a directed cycle, a distribution concentrated at one node keeps circulating, while long-run occupation fractions can still approach the uniform stationary distribution.
With positive teleport probability and patched dangling rows, the transition matrix is stochastic and all nodes communicate: the stationary distribution is unique and the iterates converge. Leaving a dangling row empty creates a leaking, sub-stochastic model. Its reference solution is disabled here; this does not mean that every sub-stochastic graph lacks a stationary distribution.
The subdominant eigenvalue modulus describes the asymptotic exponential decay rate when convergence occurs. Individual steps can oscillate, and special initial states can miss the slowest mode. Try a point start, a uniform start and different damping values.
Equations used in the module
Equations walk: P[i][j] = w[i][j] / (sum over j of w[i][j]); a row of zeros is a DANGLING node Google matrix: G = d·P + (1 − d)/n, with a dangling row replaced by the uniform row stationary: pi·G = pi with sum(pi) = 1; reached by power iteration, and solved directly as the check convergence: the error falls like |lambda_2|^n, so |lambda_2| IS the rate - but the step size only tracks it on average, because a complex subdominant pair makes the decay ROTATE (the geometric mean of the step ratios recovers it, the arithmetic mean sits 1.5 % high) damping bound: |lambda_2| = d·|mu_2(P)| exactly, so |lambda_2| ≤ d is an INEQUALITY - measured to 5.0e-16, loose by the factor 0.667 on the small web, tight on a cycle where |mu_2| = 1 rank sink: with the dangling row left empty the total mass decays to zero - the rank leaks out of the system entirely periodic: a directed n-cycle has the n-th roots of unity for eigenvalues, all of modulus 1; from a point start it returns to that point every n steps and never settles undirected: the walk is reversible and pi is just degree / 2|E| - one line of arithmetic, and the check that the iteration solves what it claims to
