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

For $0<\alpha ,\epsilon <1$, defineA hit${}_{\alpha }$ cutoff means that for every fixed $0<\epsilon <1/2$,For finite reversible chains, mixing-time cutoff implies hit${}_{1/2}$ cutoff; this is the hitting-time characterization of cutoff.

Both chains are reversible. Since $G$ is $d$-regular, simple random walk $X$ is reversible with uniform invariant distribution. In the weighted graph every vertex has total incident weight $d+\theta$, so $Y$ is also reversible with the same uniform invariant distribution.

Writewhere $M$ traverses the added perfect matching. The standard rare-transition robustness theorem for reversible chains says that when $t_{\mathrm{rel}}=o(t_{\mathrm{mix}})$, adding a bounded-degree kernel at rate $q\asymp 1/t_{\mathrm{mix}}$ cannot create cutoff: if the original chain's mixing window is a nonvanishing fraction of its mixing time, the perturbed chain retains such a window. The proof couples the chains between matching jumps; the geometric waiting time for those jumps has mean $\asymp t_{\mathrm{mix}}$ and nonconcentrated fluctuations, while the $X$ segments retain the original noncutoff profile. Therefore cutoff of $Y$ would imply cutoff of $X$, contrary to hypothesis. Hence $Y$ does not exhibit cutoff.