Conductance and Cheeger inequalities

For a finite irreducible chain on at least two states with stationary law π, define Q(x,y)=π(x)P(x,y), the probability of a directed edge in one stationary transition. The boundary flow Q(A,Aᶜ) sums only edges leaving A, so it counts that orientation once. Dividing by π(A) gives the probability of exiting in one transition when the initial law is π conditioned on A. Conductance is the minimum of this ratio over nonempty sets with stationary mass at most one half. Holding transitions contribute no boundary flow.

For a reversible chain Q is symmetric, but the definition still uses the directed sum from A to its complement, not twice that sum. The restriction to mass at most one half is also essential. A huge region can have a tiny exit probability merely because almost all stationary mass lies there; the bottleneck convention instead examines the smaller side. For a regular undirected graph, degree weights simplify the formula, while for an irregular or weighted graph counting vertices or raw edges without π can give an incorrect answer.

Assume now finite irreducibility and reversibility on at least two states. With the conductance above and ordinary gap γ, Cheeger’s inequalities give Φ²/2≤γ≤2Φ. The upper bound follows by using an indicator of A, centered by its stationary mean, in the Rayleigh quotient. Its Dirichlet energy is Q(A,Aᶜ), while its variance is π(A)π(Aᶜ). Since the latter complementary mass is at least one half, the quotient is at most twice the escape ratio. Minimizing over A supplies the bound.

The lower bound is deeper: level sets of a low-energy eigenfunction supply a set with small boundary ratio, and a Cauchy–Schwarz argument converts this into the squared-conductance inequality. This is a proof mechanism rather than a claim that every eigenfunction has a visibly unique bottleneck. The square gap between the lower and upper estimates is real; different families can make either order sharp. Additional geometry may be needed to estimate a mixing time closely instead of accepting a broad interval for its spectral scale.

A nonlazy walk on a bipartite graph can have respectable conductance and still alternate between its two sides forever. Its ordinary gap can be positive while its absolute gap is zero because of eigenvalue minus one. Making the walk lazy removes that obstruction, after which conductance bounds and the finite-state spectral TV inequality can be combined. All conductance quantities must then be recomputed for the lazy kernel: adding a one-half hold halves boundary flow and the ordinary gap, rather than leaving the original constants unchanged.

Conductance can also give direct lower bounds on mixing by starting within a low-flow set. Such an argument averages escape from a stationary-conditioned region and must account for repeated transitions rather than identifying a one-step ratio with an independent geometric hazard. The state distribution inside the region can change before escape. This warning is useful when designing samplers: an apparent narrow boundary is evidence of a possible obstruction, but its precise effect depends on stationary weights, transition probabilities and a justified multi-step estimate.