Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 215 / 3

For a path $\Gamma$,by the Cauchy-Schwarz inequality. Average over ${\nu }_{xy}$, multiply by $\tilde{Q}(x,y)$, and sum. Reversing the order of summation in the definition of the two Dirichlet forms givesLet $M={\max }_x\pi (x)/\tilde{\pi }(x)$. The variational formula for variance givesTake a nonconstant eigenfunction attaining the Rayleigh quotient $\gamma$ for $P$. Then

Choose the uniform distribution on shortest paths equivariantly under graph automorphisms. Automorphisms preserve distances and send uniform shortest paths to uniform shortest paths, so vertex transitivity makesconstant in $x$. Summing this constant over vertices counts each path-edge incidence at most twice:Thus $\tilde{f}(x)\le 2n\Delta$, and each nonnegative summand satisfies

Compare simple random walk $P$ with the independent sampler $\tilde{P}(x,y)=\pi (y)=1/n$, whose spectral gap is one. Both stationary distributions are uniform. Route each transition $(x,y)$ of the sampler along a uniformly selected shortest path. For a directed graph edge $e$,Part i therefore bounds the congestion byPart a, equivalently the Canonical paths comparison theorem, gives