The rate is the second eigenvalue

Put a walker on one vertex of a connected graph and let it step to a random neighbour repeatedly. Its distribution starts concentrated and ends at the stationary one, which for an undirected graph is the degree distribution. How long that takes is the mixing time, and there is a quantity that is supposed to name it.

The walk matrix P = D⁻¹A is not symmetric, so at first sight none of this field’s machinery applies. It is similar to one that is: $D^{1/2}PD^{-1/2} = D^{-1/2}AD^{-1/2}$ = I − 𝓛, so the walk’s eigenvalues are one minus the normalised Laplacian’s, are real, and lie in [−1, 1]. The mixing rate is |λ₂(P)|, the largest of them in absolute value below one.

The prediction, and what it is not #

The asymptotic statement is that the distance to stationarity falls like |λ₂|ᵏ. Reading that as a number of steps gives

k  ≈  log(1/ε) ÷ log(1/|λ₂|)

which is what a practitioner would use to size a run. It is not a bound — a bound would carry a constant from the starting distribution, and that constant can be large — and it is not a fit. It is an asymptotic rate treated as a schedule, which is a thing people do constantly and which deserves to be checked.

What it is worth #

Sixty vertices in two blocks, with the density between the blocks swept over forty times, the walk started at one vertex and run until the total variation distance falls below 10⁻⁶:

between-block density   |λ₂|        steps measured   predicted   ratio
0.005                   0.986994        1002            1055      0.950
0.010                   0.958917         314             329      0.953
0.020                   0.925170         169             178      0.951
0.030                   0.900071         122             131      0.930
0.080                   0.698104          36              38      0.936
0.200                   0.450568          16              17      0.923

The step count moves by a factor of sixty across the sweep and the ratio moves from 0.950 to 0.923. The prediction is between five and eight per cent high — at this tolerance.

That last qualification is the whole of the next section, and it matters because the percentage is not a property of the walk.

The bias is not quite constant, and what it tracks is the length of the run. At densities of 0.01, 0.02, 0.08 and 0.2 the measured counts are 314, 169, 36 and 16 against predictions of 329, 178, 38 and 17 — ratios of 0.954, 0.949, 0.947 and 0.941. The prediction is 4.8% high on the longest run and 6.2% high on the shortest.

Which is the mechanism below, measured rather than argued. The transient buys a fixed head start, so its share of the run grows as the run gets shorter: at 314 steps the head start is worth 4.8% of the count, and at 16 steps it is worth 6.2%. The ratio therefore falls monotonically with the step count and not with λ₂ — the two happen to move together here, and it is the step count that the discrepancy is a function of. A reader correcting the asymptotic prediction should scale the correction by the length of the run rather than by the spectral gap.

The sign of the discrepancy is worth a sentence first: the walk mixes faster than the asymptote predicts, consistently. The starting distribution is a single vertex, which has a large component along every mode, and the fast modes die early — so the opening of the run buys more than its share, and the run reaches the tolerance ahead of schedule. The curve in the figure shows exactly that: it falls steeply at first and then becomes parallel to the dashed line.

The discrepancy is a number of steps, not a percentage #

Parallel to the dashed line is the clue, and following it changes the shape of the claim. A head start means the distance is C·|λ₂|ᵏ with C below one rather than |λ₂|ᵏ, and a constant in front of an exponential is a fixed number of steps — log(1/C) ÷ log(1/|λ₂|) — whatever accuracy is asked for.

Running the same graph at four tolerances four decades apart:

  tolerance      predicted      measured     difference     percentage
    10⁻³            527.6          475          52.6           10.0%
    10⁻⁶           1055.3         1002          53.3            5.0%
    10⁻⁹           1582.9         1530          52.9            3.3%
    10⁻¹²          2110.6         2058          52.6            2.5%

Fifty-three steps, four times over, to a tenth of a step. The head start is exact and constant; the percentage is 1 − 53/predicted, which is a statement about the tolerance and not about the graph.

So five to eight per cent, everywhere is a statement about 10⁻⁶. At a looser tolerance the prediction is ten per cent high; at a tighter one, two and a half. A reader sizing a run to three digits rather than six, and carrying the seven-per-cent margin, has doubled their error in the margin without noticing.

The implied constant is the same at every tolerance too — log(1/C) comes out at 0.689, 0.698, 0.693, 0.688 — so C ≈ 0.50 on this graph, and 0.37 on the one at pOut = 0.03 where the head start is nine steps rather than fifty-three. The constant is a property of the starting vertex’s overlap with the slow mode, which is what the asymptotic statement discards and what a bound would have to carry.

And a handful of steps is fifty-three. On the slowest graph in the sweep that is a twentieth of the run; on the fastest, at seventeen steps predicted, a head start of that size would be the whole computation — which is why the far end of the sweep has the ratio approaching one from a different direction and why the essay’s original range of 0.950 to 0.923 is not monotone in the way it looks.

What that does to the practitioner’s formula #

The formula this essay opened with is k ≈ log(1/ε) ÷ log(1/|λ₂|), and the measurement gives it a correction with a shape:

k  ≈  ( log(1/ε) − log(1/C) ) ÷ log(1/|λ₂|)

with log(1/C) between 0.7 and 1.0 on these graphs. Against log(1/ε) of 13.8 at a tolerance of 10⁻⁶ that is a five per cent trim, and against 6.9 at 10⁻³ a ten per cent one — which is exactly the table.

The useful reading is not the correction, which is small, but what it says about the uncorrected formula’s error bar. C depends on the starting vertex, and sweeping all sixty starts on the pOut = 0.03 graph gives step counts from 119 to 127 against a prediction of 131 — a spread of eight steps against a head start of nine. The variation across starting vertices is the same size as the correction itself, so there is no version of the formula, corrected or not, that is right to better than about five per cent without knowing where the walk begins.

That is a comfortable place to end rather than an awkward one. A schedule good to five per cent is a schedule, and the reason it cannot be better is not the arithmetic and not the asymptotics — it is that the question how many steps has an answer that depends on the starting distribution, and the eigenvalue does not know the starting distribution. The rate is a property of the graph; the step count is a property of the graph and the start, and only one of the two is what λ₂ is.

Three of the four graphs never mix at all #

The measurement above was taken on a two-block graph, and the choice was not incidental. Run the same experiment on the other families in this field and most of them do not converge:

graph          λ₂(P)      smallest eigenvalue    bipartite    steps to 10⁻⁶
grid 6×7       0.937025        −1.000000            yes        never
cycle 24       0.965926        −1.000000            yes        never
path 30        0.994138        −1.000000            yes        never
two blocks     0.900071        −0.471447            no          122

After twenty thousand steps the total variation distance on all three bipartite graphs is exactly 0.5, and it stays there forever. The reason is the eigenvalue at −1: a bipartite graph’s walk moves from one side to the other at every step and back at the next, so a walker started on one side is on that side at even times and the other at odd times, permanently.

The rate |λ₂| said nothing about this, because it is the second largest in absolute value and here that is the eigenvalue at −1, which does not decay. Quoting λ₂ as the rate — the second largest eigenvalue rather than the second largest in modulus — is the error, and on a bipartite graph it predicts convergence at 0.937 a step for a walk that never converges at all.

Bipartite graphs are not exotic. A grid is bipartite. A tree is bipartite. Any graph with no odd cycle is bipartite, and a great many graphs from discretisations are.

The repair, and what it costs #

The standard fix is the lazy walk: at each step stay put with probability a half and move with probability a half. Its matrix is (I + P)/2, whose eigenvalues are (1 + μ)/2 — so the eigenvalue at −1 becomes 0, every eigenvalue lands in [0, 1], and periodicity is impossible.

The cost is a factor of two and a bit. The lazy walk’s rate is (1 + λ₂)/2, which for the grid is 0.9685 against 0.9370, so the number of steps roughly doubles. That is the trade: a walk that converges half as fast, in exchange for converging.

It is also exactly what PageRank’s teleportation does, seen from a different angle. Mixing αP with a rank-one term does the same job as mixing P with the identity — both destroy periodicity by giving the walker something to do other than follow an edge — and both cost a factor in the rate. The difference is that teleportation also changes the answer, since (1 − α) of the stationary vector is the teleport distribution, while laziness does not: (I + P)/2 has exactly the same stationary vector as P. Laziness buys convergence for free and teleportation buys it for a change of answer, which is the choice the essay on α is about.

It is the same eigenvalue the partition essays are about #

The measurement above and the conductance measurements three essays earlier are the same number seen twice, and it is worth putting them in one table:

between-block density   λ₂(𝓛)      conductance φ    mixing steps
0.005                   0.013006      0.008357          1002
0.020                   0.074830      0.045576           169
0.080                   0.301896      0.183486            36

A graph that is hard to cut is a graph a walk crosses slowly, and the two statements are the same eigenvalue read in two directions. Cheeger’s inequality connects φ to λ₂(𝓛); the mixing time connects λ₂(P) = 1 − λ₂(𝓛) to a number of steps. So a bottleneck is simultaneously a good partition and a slow walk, and neither fact is a metaphor for the other.

That is a genuinely useful equivalence rather than a curiosity. It means the certificate the Cheeger lower bound provides — that no cut is better than λ₂/2 — is also a certificate that the walk cannot mix faster than a rate, and the reverse. One eigenvalue computation answers both questions.

The other direction: what a walk is used for #

The reason to care about the rate is that almost nothing waits for the exact stationary vector.

A power iteration for PageRank is a walk with teleportation and is stopped when successive iterates stop moving. A Markov chain Monte Carlo sampler is a walk whose burn-in is exactly a mixing time. A graph-based recommendation is often a few steps of a walk rather than its limit. In every case the question is not what the stationary vector is but how many steps buy how much of it, and that is the quantity the table above measures.

The bad case is worth naming. A walk on a graph with a bottleneck of conductance 10⁻³ takes of order 10³ steps to cross it, and no amount of arithmetic accuracy changes that: the slowness is a property of the graph. What changes it is preconditioning the graph — adding edges, or restarting the walk — which changes the answer as well as the rate, and is the same trade the iterative field makes with a preconditioner.

And now the claim that is not true #

PageRank’s power iteration is said to contract by α a step. It is in every account of the method, it is the basis of every statement about how many iterations are needed, and it is a corollary of a theorem about the Google matrix’s second eigenvalue.

The theorem says the second eigenvalue of αP + (1 − α)v1ᵀ is α·λ₂(P), not α. The two agree exactly when λ₂(P) = 1.

λ₂(P) = 1 happens when the chain has more than one closed communicating class — when the link graph is in pieces that cannot reach each other. A real web graph is exactly that: a giant component, a large number of small islands, and no path from most of the islands back to the main body. So λ₂(P) = 1 holds, and the folk rate is exact.

It is not exact on a connected graph. Measured, at two values of α on three connected graphs:

graph               λ₂(P)      α      predicted α·λ₂   measured rate
two blocks 50      0.902380   0.50       0.4512          0.4509
two blocks 50      0.902380   0.85       0.7670          0.7668
two blocks 60      0.828870   0.50       0.4144          0.4147
grid 5×6           0.910790   0.50       0.4554          0.4551
two islands        1.000000   0.50       0.5000          0.4848
two islands        1.000000   0.85       0.8500          0.8271

On the connected graphs the measured rate matches α·λ₂(P) to four digits and is nowhere near α. On the graph built in two closed pieces it matches α.

So a widely quoted rate is correct because of a property of the data that is never mentioned when the rate is quoted. It is not wrong and it is not tight for the reason anybody thinks: the analysis gives α·λ₂(P), the web supplies λ₂(P) = 1, and the two coincide by accident of subject matter.

Why this is worth more than a correction #

Two consequences follow, and the second is the one that matters.

On a connected graph the iteration is faster than advertised, by exactly the factor λ₂(P). On the grid above that is a factor of 0.91 a step, which compounds: reaching 10⁻¹² takes 289 steps at the folk rate and 261 at the real one. Nobody is harmed by a pessimistic estimate, but a run sized by it is doing ten per cent more work than it needs to.

And a graph’s connectivity is now a performance parameter. If λ₂(P) is what decides the rate, then anything that changes the graph’s connectivity changes how long a PageRank computation takes — adding links between islands, merging crawls, restricting to a strongly connected core. Those are decisions made for other reasons, and the folk rate says they cannot possibly affect the cost. They can, and by the ratio between λ₂(P) and 1.

This is the shape the site keeps finding when a rate is quoted without its derivation: a rate that is known in advance is about the stationary iterations whose asymptotic factors are exact and whose transients are not, and the rate the condition number predicts is about a bound that is correct and is attained only when the spectrum has no structure. The pattern is that a rate is a statement about a spectrum, and quoting it without the spectrum is quoting a coincidence.

Where it starts hardly matters #

One assumption in the table is worth checking, because a rate that is only asymptotic could easily be dominated by the transient, and the transient depends on where the walker began.

Starting the same walk at seven different vertices of the two-block graph, chosen to span the degree range from eight to eighteen and to include vertices in both blocks:

start vertex   degree   steps to 10⁻⁶
 0              12          122
 1              11          125
29              18          125
30              12          126
59               9          127
 4              18          126
 6               8          126

Four per cent, across the whole range. The starting vertex is worth five steps out of a hundred and twenty-five, and its degree does not correlate with anything.

That is the asymptotic rate earning its keep. The transient differs between starts — a walker beginning at a high-degree vertex is closer to stationarity after one step than one beginning at a leaf — but the difference is spent within a dozen steps, and the remaining hundred and ten are the slow mode, which is the same slow mode whatever the start.

It also means the seven per cent discrepancy in the first table is not a start artefact. It is the transient, it is the same size wherever the walk begins, and it is a property of the graph rather than of the experiment.

What to measure instead #

The honest procedure is three lines and none of them is expensive relative to the run they are sizing.

Compute λ₂ of the walk, symmetrically. $D^{-1/2}AD^{-1/2}$ is symmetric, so the site’s own eigensolver applies, and one eigenvalue of a sparse symmetric matrix is a few dozen matrix–vector products.

Predict, and expect to be five per cent high. log(1/ε)/log(1/|λ₂|) was between 1.05 and 1.08 times the measured step count across a sixty-fold range here. That is a good enough estimate to size a run and a poor enough one that it should be reported as an estimate.

And measure the thing being waited for, not the iterate’s change. The total variation distance in the figure is available only because the stationary vector is known here; in practice what is measured is the change between iterates, and the change underestimates the remaining error by a factor of 1/(1 − |λ₂|). At |λ₂| = 0.987 that factor is seventy-seven. A run stopped when the change falls below 10⁻⁸ is 10⁻⁶ from the answer, and nothing in its output says so.

The one thing the eigenvalue does not say #

A closing caveat, because the whole essay has been about a single number and there is a question it cannot answer.

|λ₂| says how fast the worst starting distribution decays. It says nothing about how fast a particular functional of the walk converges, and functionals are usually what is wanted. A walk used to estimate the expected value of something concentrated on a few vertices can be accurate long before the distribution has mixed, because the modes that are still alive may have almost no component on those vertices. Equally it can be inaccurate long after, if they do.

This is the same distinction the trace estimation essays make about a randomised estimator: the variance of the quantity being estimated is not the variance of the vector it is computed from, and a bound on one is not a bound on the other.

The practical form of it is that a mixing time is an upper bound on the burn-in a sampler needs and is usually a pessimistic one. Sizing a run by it is safe and can be expensive; sizing a run by watching the quantity of interest is cheap and can be wrong, because a quantity that has stopped moving may be stuck rather than converged. Neither is a substitute for the other, and the honest procedure runs both — which is the same conclusion the stopping-test essays reach about a residual.