= Solution
Let $P$ be a finite reversible Markov chain with stationary distribution $\pi$, and write $Q(e)=\pi(u)P(u,v)$ for an oriented transition edge $e=(u,v)$. For every ordered pair $(x,y)$ choose a directed path $\gamma_{xy}$ from $x$ to $y$ using positive-capacity edges, and define the congestion
$$
\rho=\max_e\frac1{Q(e)}
\sum_{x,y:e\in\gamma_{xy}}
\pi(x)\pi(y)|\gamma_{xy}|.
$$
Then the <Canonical paths comparison theorem> gives the <Poincare inequality>
$$
\boxed{\operatorname{Var}_\pi(f)\leq\rho\,\mathcal E(f,f)}
$$
for every real function $f$, and hence the spectral gap is at least $1/\rho$.
Indeed,
$$
\operatorname{Var}_\pi(f)
=\frac12\sum_{x,y}\pi(x)\pi(y)(f(x)-f(y))^2.
$$
Write each difference as the sum of edge differences along $\gamma_{xy}$ and apply <Cauchy-Schwarz inequality>:
$$
(f(x)-f(y))^2
\leq|\gamma_{xy}|\sum_{e\in\gamma_{xy}}(\nabla_ef)^2.
$$
Interchanging the pair and edge sums, then applying the definition of $\rho$, bounds the result by
$$
\frac\rho2\sum_eQ(e)(\nabla_ef)^2
=\rho\mathcal E(f,f).
$$
Back to article page
