Generalized Cheeger inequality

For a finite irreducible Reversible Markov chain with Stationary distribution $\pi$, let $Q(x,y)=\pi (x)P(x,y)$ and define its conductance profile byFor ${\pi }_{\ast }:={\min }_x\pi (x)\le r\le 1/2$ and the variance-normalized Spectral profile,The star here names the small-set profile on this restricted domain; some sources reserve a star for its extension truncated at $1/2$.^[ref]

For the upper bound, test the spectral-profile quotient with $f=1_A$. Its energy is $Q(A,A^c)$ and its variance is $\pi (A)(1-\pi (A))$. For the lower bound, take a nonnegative function supported on a set of mass at most $r$. Applying the level-set integral identity to $f^2$ bounds ${\Phi }_{\ast }(r)\Vert f{\Vert }_2^2$ by $\frac{1}{2}{\sum }_{x,y}Q(x,y)|f(x{)}^2-f(y{)}^2|$. Factoring the difference of squares and applying the Cauchy-Schwarz inequality bounds this last expression by $\sqrt{2\mathcal{E}(f,f)}\Vert f{\Vert }_2$. Squaring and using ${\mathrm{Var}}_{\pi }(f)\le \Vert f{\Vert }_2^2$ proves the lower bound. Thus a geometric obstruction to boundary flow produces an analytic obstruction to relaxation.