Cheeger's inequality: Markov chain version is a special case of graph version?

Question

For a Markov chain

the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a special case of Cheeger inequalities in expander graphs.

Let $X$ be a finite set and let $K(x,y)$ be the transition probability for a reversible Markov chain on $X$. Assume this chain has stationary distribution $\pi$. $$ 1 - 2 \Phi \leq \lambda_2 \leq 1 - \frac{\Phi^2}{2}. $$

where $\Phi$ is the edge expansion of the graph for the random walk corresponding to the MC. Note that a homogeneous DTMC can be seen as a random walk on a directed graph with its vertex set being the state space of the MC.

For a graph

When $G$ is d-regular, there is a relationship between edge expansion $h(G)$ and the spectral gap $d - \lambda_2$ of $G$. An inequality due to Tanner and independently Alon and Milman[7] states that $$ \frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}\,.$$

I cannot understand why the MC version is a special case of the graph version. Specifically, how can a reversible finite-state MC be seen as a regular graph? In particular, the stationary/reversible/limiting distribution of a reversible finite-state MC is not necessarily uniform.

I suspect the articles miss something? Maybe someone happen to know more general versions of Cheeger's inequality, which can have the two versions here as special cases?

Thanks and regards!

Answer 1

Both versions of the Cheeger inequality follow from the version for weighted graphs proved by Chung (see e.g. [1]).

Let $G$ be an undirected graph in which edge $(u,v)$ has non-negative weight $\pi(u,v)$ (if there is no edge between $u$ and $v$ then $\pi(u,v) = 0$). Let the degree of vertex $v$ be the total weight of all edges incident to $v$. Define the Laplacian matrix ${\cal L}$ as follows: $${\cal L} = \begin{cases} 1 - \frac{\pi(u,v)}{d_u} , &\text{if } u = v,\\ -\frac{\pi(u,v)}{\sqrt{d_ud_v}} , & \text{if } u\neq v. \end{cases} $$

Let $\lambda_1$ be the second smallest eigenvalue of $\cal L$ and $$h = \min_{X\subset V} \frac{\sum_{u\in X, v\notin X}\pi(u,v)}{\min(\sum_{\in X} d_u,\sum_{u\notin X} d_u)},$$ where $X\neq \varnothing$ and $X\neq V$. Then $$\frac{h^2}{2} \leq \lambda_1 \leq 2h.$$

The Cheeger inequality for $d$-regular graphs follows immediately if we let $\pi(u,v) = 1$ iff $(u,v) \in E$.

The Cheeger inequality for reversible MC follows if we let $\pi(u,v) = p(u)\cdot K(u,v)$ (where $p(u)$ is the stationary distribution and $K(u,v)$ is the transition probability).

[1] F. R. K. Chung. Laplacians of graphs and Cheeger inequalities. Available at: http://www.math.ucsd.edu/~fan/wp/cheeger.pdf