Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 4 / a / 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 congestionThen the Canonical paths comparison theorem gives the Poincare inequalityfor every real function $f$, and hence the spectral gap is at least $1/\rho$.

Indeed,Write each difference as the sum of edge differences along ${\gamma }_{xy}$ and apply Cauchy-Schwarz inequality:Interchanging the pair and edge sums, then applying the definition of $\rho$, bounds the result by