= Solution
For a finite <irreducible Markov chain> satisfying <detailed balance>, define the directed-edge capacity $Q(u,v)=\pi(u)P(u,v)$. For every ordered pair $(x,y)$ choose a <path> $\eta_{xy}$ from $x$ to $y$ using only positive-capacity <edges>; take the empty <path> for $x=y$. Let $N_e(\eta)$ count occurrences of the directed <edge> $e$. The <canonical paths Poincare bound> says that
$$
\rho=\max_{e:Q(e)>0}\frac{1}{Q(e)}\sum_{x,y}\pi(x)\pi(y)|\eta_{xy}|N_e(\eta_{xy})
$$
is a valid <Poincare inequality for a reversible Markov chain> constant. Simple <paths> give $N_e\in\{0,1\}$; allowing repetitions requires the multiplicities shown.
To prove the theorem, expand the <variance> using two independent samples from $\pi$:
$$
\operatorname{Var}_\pi(f)=\frac12\sum_{x,y}\pi(x)\pi(y)(f(x)-f(y))^2.
$$
Telescoping along $\eta_{xy}$ and applying the <Cauchy-Schwarz inequality> gives
$$
(f(x)-f(y))^2\leq|\eta_{xy}|\sum_eN_e(\eta_{xy})(f(e^-)-f(e^+))^2.
$$
Interchange the finite sums, then use the definition of $\rho$:
$$
\begin{aligned}
\operatorname{Var}_\pi(f)&\leq\frac12\sum_e(f(e^-)-f(e^+))^2\sum_{x,y}\pi(x)\pi(y)|\eta_{xy}|N_e(\eta_{xy})\\
&\leq\frac\rho2\sum_eQ(e)(f(e^-)-f(e^+))^2=\rho\mathcal E(f,f).
\end{aligned}
$$
Consequently $\boxed{\operatorname{Var}_\pi(f)\leq\rho\mathcal E(f,f),\quad\gamma\geq1/\rho}$. All <edges> here are directed, so the $1/2$ in the <Dirichlet form of a Markov chain> is retained consistently.
Back to article page
