Theorem 13.14 -- the Cheeger inequality

Let $P$ be an irreducible Markov chain on a finite state space $V$ with at least two states, reversible with respect to its stationary distribution $\pi$ (detailed balance: $\pi(x)P(x,y)=\pi(y)P(y,x)$). Two quantities measure how quickly the chain can move:

• the bottleneck constant $\Phi_\star=\min\bigl\{\Phi(S):\varnothing\ne S\subseteq V,\ \pi(S)\le\tfrac12\bigr\}$, where $\Phi(S)=\sum_{x\in S,\,y\notin S}\pi(x)P(x,y)\,/\,\pi(S)$ is the conditional probability at stationarity of escaping the set $S$ in one step — a geometric, cut-based quantity;
• the spectral gap $\gamma=1-\lambda_2$, where $\lambda_2$ is the largest eigenvalue of $P$ different from $1$ (an eigenvalue being a real $\lambda$ with $Pf=\lambda f$ for some nonzero $f$) — an analytic quantity.

The theorem (Theorem 13.14 of Levin–Peres–Wilmer; Jerrum–Sinclair, Lawler–Sokal — the discrete Cheeger inequality, capstone of Chapters 12–13) asserts:

1. $\dfrac{\Phi_\star^2}{2}\;\le\;\gamma$;
2. $\gamma\;\le\;2\,\Phi_\star$.

Bottlenecks and spectral gaps control each other up to a square: a chain mixes rapidly exactly when it has no bottleneck. This equivalence is the backbone of the Markov-chain approach to approximate counting and of expander graph theory.