Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Mixing time — where it appears

How many steps a random walk takes to come within a stated distance of its stationary distribution. It is predicted by the second eigenvalue, and on the graphs measured here the prediction runs about five per cent high.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk

The rate is the second eigenvalue

A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces.

graph · random walk 02244668811013215417610⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)1predicted rate0.85measured0.84iterations176against the solve1.4·10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A chain with no stationary vector

A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps. A directed cycle never converges at all. And on a graph whose links only run one way, the entire rank of half the vertices is exactly one minus the teleportation parameter.

graph · random walk

Named alongside it

The objects these essays reach for when they reach for this one.

PagerankBipartiteCollatz wielandtConductanceDangling nodeIrreducibilityNormalised laplacianPeriodicityPerron frobeniusPower iterationRandom walkRegularisation

All concepts