= Generalized Cheeger inequality
{c}
For a finite <irreducible Markov chain>[irreducible] <Reversible Markov chain> with <Stationary distribution> $\pi$, let $Q(x,y)=\pi(x)P(x,y)$ and define its <conductance profile> by
$$
\Phi_*(r)=\inf_{0<\pi(A)\leq r}\frac{Q(A,A^c)}{\pi(A)}.
$$
For $\pi_*:=\min_x\pi(x)\leq r\leq1/2$ and the variance-normalized <Spectral profile>,
$$
\frac{\Phi_*(r)^2}{2}\leq\Lambda(r)\leq\frac{\Phi_*(r)}{1-r}.
$$
The star here names the small-set profile on this restricted domain; some sources reserve a star for its extension truncated at $1/2$.<Mixing Time Bounds via the Spectral Profile by Sharad Goel and others>[Section 2.2, Definition 2.2 and Lemma 2.4]{ref}
For the upper bound, test the spectral-profile quotient with $f=\mathbf1_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_*(r)\lVert f\rVert_2^2$ by $\tfrac12\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)}\lVert f\rVert_2$. Squaring and using $\operatorname{Var}_\pi(f)\leq\lVert f\rVert_2^2$ proves the lower bound. Thus a geometric obstruction to boundary flow produces an analytic obstruction to <relaxation time>[relaxation].
Back to article page
