Compare simple random walk $P$ with the independent sampler $\widetilde 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$,
$$
Q(e)=\frac1{nd},
\qquad
\widetilde Q(x,y)=\frac1{n^2},
\qquad
|\Gamma_{xy}|\leq\Delta.
$$
Part i therefore bounds the congestion by
$$
B\leq nd\frac{\Delta}{n^2}f(e)
\leq2d\Delta^2.
$$
Part a, equivalently the <Canonical paths comparison theorem>, gives
$$
1=\widetilde\gamma\leq B\gamma,
\qquad
\boxed{\frac1\gamma\leq2d\Delta^2}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-215/3/b/ii/solution