= Solution
Write
$$
\widetilde P=(1-q)P+qM,
\qquad q=\frac\theta{d+\theta}\asymp\frac1{t_{\mathrm{mix}}},
$$
where $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\asymp1/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.
Back to article page
