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

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