Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels (Q2461043)

The Perron-Frobenius theorem guarantees that a finite, ergodic, reversible Markov kernel \(P\) has a real valued eigenbasis with eigenvalues \(1=\lambda_0(P)>\lambda_1(P)\geq \dots\geq\lambda_{n-1}(P)\geq -1\). The spectral gap \(\lambda=1-\lambda_1(P)\), or in the non-reversible case the gap \(\lambda=1-\lambda_1(\frac{P+P^*}{2})\) of the additive symmetrization, governs key properties of the Markov chain. In the article the generic sharp lower bound estimate on \(\lambda\) is obtained. It uses the evolving set methodology of \textit{B. Morris} and \textit{Y. Peres} [Probab. Theory Relat. Fields 133, No.~2, 245--266 (2005; Zbl 1080.60071)]. The generic estimate is used to obtain sharp edge, vertex and mixed Cheeger-like lower bounds on \(\lambda\). Cheeger-like lower bounds on \(1+\lambda_{n-1}(P)\) follow as well.