The narrowest door sets the pace

How long until it forgets ended on a number and a warning. The number is the spectral gap, one minus the second eigenvalue of the transition matrix, and the time a chain takes to forget where it started is about one over it. The warning is that the gap of any chain worth studying cannot be computed: a chain on the orderings of a deck of cards has a matrix with $52!$ rows, and no eigenvalue of it will ever be found.

What can be found is a picture. A chain is slow when its states fall into two parts with little traffic between them, so that a walk started in one part stays there and the distribution remembers the start. The conductance measures the narrowest such door, and Cheeger’s inequality says that it and the gap are the same quantity to within a square. This essay is that inequality, measured on graphs small enough that both sides can be computed exactly and compared.

The figure below is the case the intuition is built on: two tight clusters of six joined by a single edge. The door is the bridge. Its conductance, found by trying every one of the 2,047 ways to split the twelve vertices, is $0.0161$, and Cheeger’s inequality then says the gap lies between $0.00013$ and $0.0323$. The gap computed from the eigenvalues is $0.0253$ — inside the range, and near its top.

What the door measures #

Every chain here is the lazy walk on a graph: at each step, stay put with chance one half, and otherwise move to a neighbour chosen uniformly. It is reversible, its stationary share at each vertex is proportional to the vertex’s degree, and the laziness makes every eigenvalue non-negative, so the gap is simply one minus the second largest.

For a set of vertices $S$, the flow out of it is the chance, in the stationary regime, that one step goes from inside $S$ to outside it. Dividing by the weight $S$ holds gives a conditional chance: given that the walk is in $S$, how likely is the next step to leave. That ratio is the conductance of $S$,

$$\Phi(S) = \frac{Q(S, S^c)}{\pi(S)},$$

and the conductance of the chain, $\Phi$, is the smallest value over every set holding at most half the weight. The half matters: without it, the set of all vertices would have nowhere to go and conductance zero, and the definition would say nothing.

The ratio is the whole idea. A set with few edges leaving it is not a bottleneck if it is tiny — a single leaf of a tree has one edge out, and one edge in total, so the walk leaves it immediately. A bottleneck is a set that is large and hard to leave, and dividing the flow by the weight is what says so. It is also what makes conductance different from the minimum cut, which counts the edges alone and would happily cut off one leaf.

The inequality #

Cheeger’s inequality, in the form for reversible chains, says

$$\frac{\Phi^2}{2} \le \text{gap} \le 2\Phi.$$

Jeff Cheeger proved the ancestor in 1970 for curved surfaces and manifolds, where the gap is the lowest vibration of a drum and the door is the shortest curve cutting the drum into two large pieces. The discrete versions came in the 1980s — Dodziuk, then Alon and Milman for graphs, and Lawler and Sokal and then Jerrum and Sinclair for Markov chains — and it was Jerrum and Sinclair’s use of it, to prove that a chain on the matchings of a graph mixes fast, that turned it into the working tool of the subject.

The two sides do different jobs. The upper bound, gap at most $2\Phi$, says a narrow door forces slow mixing: find one set that is hard to leave and the chain is slow, without computing anything else. The lower bound, gap at least $\Phi^2/2$, says a chain with no narrow door must mix: prove that every set has a wide exit and the gap is bounded below. The second is the one that carries the weight in practice, because it turns a question about an eigenvalue into a question about every subset of the state space — harder to state, but answerable by counting paths and edges, which is what the combinatorics of a large chain can supply.

Every point in that figure is two independent computations meeting. The conductance comes from enumerating vertex sets — over 130,000 of them for the largest graph — and the gap from Jacobi rotations on the symmetrised transition matrix, which share no code. The wedge between the dashed lines is the inequality, and nothing about the drawing puts the points inside it: the figure is built to fail if one lands outside.

What the scatter also shows is that the wedge is wide. At a conductance of a hundredth the two lines are four orders of magnitude apart, and a chain could sit anywhere between them. The inequality locates the gap only up to a square, which sounds like a weak statement and is exactly strong enough for its job: the difference between a gap of $\Phi$ and a gap of $\Phi^2$ is the difference between a mixing time of $1/\Phi$ and one of $1/\Phi^2$, and when $\Phi$ is a power of the chain’s size that is a change of exponent, not a change from fast to slow.

Both ends are reached #

A range is only an honest description of a quantity if the quantity can be at both ends of it. Two families show that it can.

On a ring the narrowest door is to cut it in half: two edges cross, and each carries a stationary flow of $1/(4m)$ on a ring of $m$, so the door has conductance $1/m$. The gap is $(1 - \cos(2\pi/m))/2$, which for a large ring is about $\pi^2/m^2$. So the gap is $\pi^2$ times the square of the conductance — the lower side of the inequality, in its exponent, with only the constant to spare. The figure checks both closed forms against the search and the eigenvalues at every size.

The reason is that a walk on a ring does not so much squeeze through a door as diffuse towards it. To get from one half to the other it must travel about half the ring, and a random walk covers a distance $d$ in about $d^2$ steps — the square-root law that governs every unbiased walk. The door is wide open, two edges out of a small set; what makes the ring slow is the distance to the door, and conductance, which only looks at one step, sees the door and not the distance. Hence the square.

A dumbbell is the opposite case. Inside each clique the walk forgets its position in one or two steps, so it arrives at the door almost immediately; all the waiting is at the door itself, for the one step in many that happens to cross. The time to cross is one over the conductance, and so is the mixing time. The upper side of the inequality is the right order here, and the table’s middle column stays flat while the last one grows.

The cube goes further. The lazy walk on the $d$-dimensional cube has gap exactly $1/d$, its narrowest door is any half-cube — cut across one coordinate — with conductance exactly $1/(2d)$, and so the gap equals $2\Phi$ with no room at all. The scatter’s upper line passes through the two cube points, not merely near them. Neither side of Cheeger’s inequality can be improved, even by a constant, on every graph.

The door that is not where it looks #

The picture of a bottleneck is usually two blobs and a bridge, and it is worth seeing a graph where the door is a different shape.

A lollipop — a clique with a long stick attached — has both kinds of slowness at once. The door, found by the search, is the edge where the stick meets the clique: the stick is the smaller part, holding weight in proportion to its eleven degrees against the clique’s thirty-one. But the walk is not slow only because of the door. Once inside the stick it must diffuse along it, the ring’s problem, and so the gap sits between the dumbbell’s regime and the ring’s, well inside the range and near neither bound. Conductance names the right door and cannot say how long the corridor behind it is.

That is the general limitation. The door is a one-step quantity and mixing is a many-step one. Wherever the slowness is geometric — long thin state spaces, walks that must travel before they can cross — the gap is nearer $\Phi^2$ and the upper bound is loose. Where the slowness is a genuine bottleneck with fast mixing on either side, the gap is nearer $\Phi$. Most chains of interest have some of each, and the inequality gives the honest range for all of them.

Finding the door from the eigenvector #

The lower bound’s proof is constructive, and the construction is an algorithm anyone who has partitioned a graph has used.

Take the second eigenvector of the chain, the one belonging to the eigenvalue just below one, as a function on the vertices. Sort the vertices by its value. Of all the $n - 1$ ways to cut the sorted list into a low part and a high part, try each and keep the one with the smallest conductance. The proof of Cheeger’s inequality shows that this cut has conductance at most $\sqrt{2 \cdot \text{gap}}$: the eigenvector does not merely certify that a door exists, it points to one.

The eigenvector has a physical reading. It is the slowest way the chain’s distribution can be out of balance, the mode that survives longest as the chain runs, and on a graph with a bottleneck that mode is “too much on one side, too little on the other”. Sorting by it lines the vertices up from the deepest point of one side to the deepest point of the other, and the door is where the sign changes. On the two grids, the sweep’s best cut is exactly the bridge, and the V-shaped curve of the sweep’s conductances has its minimum there.

On the cube the guarantee is loose by a factor of more than five, and that is typical. The sweep usually finds a much better door than $\sqrt{2 \cdot \text{gap}}$ promises; what the proof shows is only that it can never do worse. The same algorithm, run on the eigenvector of a graph’s Laplacian rather than a chain’s transition matrix, is spectral partitioning, used to split meshes across processors and to cluster data, and Miroslav Fiedler’s 1973 paper on the vector that bears his name is where it starts. The eigenvector is the highest point of a quadratic form on a sphere, restricted to directions orthogonal to the stationary one, and the sweep turns that continuous optimum into a discrete cut.

Why the upper bound is easy and the lower bound is not #

The two halves of the proof are unequal, and the imbalance explains which one gets used for what.

The gap has a variational description: it is the smallest value of the ratio of how much a function changes across edges to how much it varies overall, taken over every function orthogonal to the constants. To show the gap is small, it is enough to exhibit one function with a small ratio. The indicator of the narrowest door, shifted to average zero, is such a function; its ratio is at most $2\Phi$; and the upper bound follows in three lines.

To show the gap is large, one has to control every function at once, and there is no single witness. The proof takes the eigenvector itself and slices it at every level, showing that some slice — some sweep cut — has conductance at most $\sqrt{2 \cdot \text{gap}}$. The square root enters through the Cauchy–Schwarz inequality, used once, and it is the square root that makes the lower bound quadratic. The gap between the two directions of the inequality is the gap between exhibiting an obstruction and ruling out all of them.

What the door costs to find #

The figures find every door by exhaustion, which is possible only because the graphs are tiny. The largest here has eighteen vertices, and 131,071 vertex sets is nothing; a graph of sixty vertices would need more sets than there have been seconds since the Big Bang.

In general the narrowest door is NP-hard to find — computing a graph’s conductance exactly is as hard as the hardest search problems, in contrast with the ordinary minimum cut, which a flow computation finds exactly. The best approximation known in polynomial time, due to Arora, Rao and Vazirani in 2004, is within a factor that grows like the square root of the logarithm of the size. The ratio is what makes it hard: dividing by the weight turns a minimisation that flows can settle into one they can only approximate, which is the same gap between flows and cuts that appears once several pairs share the roads.

This is why the lower bound, and not the sweep, is the tool for large chains. Nobody finds the door of the chain on $52!$ orderings. What is done instead is to prove that every set has a wide exit, usually by routing a canonical path between every pair of states and showing that no single transition carries too many of them — Jerrum and Sinclair’s method, and the one that proved the chain on the matchings of a graph mixes in polynomial time.

Families with a door that never narrows #

A family of graphs whose conductance stays above a fixed constant as the graphs grow is a family of expanders, and by Cheeger’s inequality their gaps stay above a fixed constant too. Their walks mix in a number of steps proportional to the logarithm of the number of vertices, the fastest any walk on a graph of bounded degree can manage, since it takes that many steps merely to reach most vertices.

None of the figures’ graphs is an expander. Rings, paths, grids and dumbbells all have conductance falling as they grow; even the cube’s, $1/(2d)$, falls as the dimension rises, though only like the logarithm of the vertex count. Expanders of bounded degree exist, and a random regular graph is one with high probability, but constructing one explicitly took until 1973 and the constructions that followed use deep number theory — the graphs of Lubotzky, Phillips and Sarnak, and independently Margulis, come from quaternion algebras and have the largest gap Alon and Boppana showed possible. A graph that every set leaves quickly is easy to find at random and hard to write down. That tension, between what is typical and what is constructible, is one expanders share with much of combinatorics.

What the figures cannot show #

Every graph here is tiny. Eighteen vertices is the most, and the whole point of the inequality is chains too large for any of this to be computed. The figures show the inequality holding and both ends being reached; they cannot show it being used, since using it means proving a bound on a chain where neither side can be computed.

The lazy walk is one chain per graph. A different transition rule on the same graph — a Metropolis walk, built to sample a chosen distribution, or a walk with edge weights — has a different conductance and a different gap, and the inequality holds for each with its own numbers. The figures fix the rule so that the graph is the only thing that varies.

And the inequality compares one step to the long run. It says nothing about the constant in the mixing time, which depends on how uneven the stationary distribution is, and nothing about the cutoff phenomenon, where the approach to stationarity happens suddenly in a family of chains. That needs a family and a rescaled axis, and it is the forgetting that happens all at once.

Still open: which door, and how narrow #

How long until it forgets measured the gap on single chains, and this essay bounds it by a door. What neither can say is where, in a large family of chains, the distance to stationarity actually falls — whether it slopes or falls off a cliff — since the door is a one-step quantity and the shape of the approach is not.

The open questions about the door itself are computational. Finding the narrowest door exactly is NP-hard, and whether the square root of the logarithm in the best approximation can be improved to a constant is tied to the unique games conjecture, one of the central open problems of complexity theory. The minimum cut that conductance refines is the bottleneck that is the whole story for flows, the second eigenvector is a highest point on a sphere, and the ring’s quadratic slowness is the diffusive scaling of a walk that comes home.

What is worth carrying away #

An eigenvalue that cannot be computed can still be bounded, if something else can be measured that it is tied to. The gap is tied to the narrowest door, above by twice it and below by half its square, and both ties are tight on graphs as simple as a ring and a cube.

The habit worth keeping is to look for the obstruction’s picture. A slow chain is slow for a reason that can be drawn — a door, a corridor, a set the walk cannot leave — and naming that reason is usually easier than computing the number it determines, and more informative once found.