Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 4

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

Letand choose $x$ attaining the maximum. For every $t$, the Strong Markov property at time $t$ givesThusIf $t\ge t_{\mathrm{mix}}(1/4)$, thenSince $\{X_t\in A\}\subseteq \{T_A\le t\}$, this is impossible when $t<m/4$. Allowing for integer times, one may take any smaller absolute constant, for example