= Solution
For a finite <irreducible Markov chain> that is an <aperiodic Markov chain>, set
$$
d_n(t)=\max_x\|P_n^t(x,\cdot)-\pi_n\|_{\mathrm{TV}},\qquad
\boxed{t_{\mathrm{mix}}^{(n)}(\alpha)=\min\{t\in\mathbb Z_{\geq0}:d_n(t)\leq\alpha\}.}
$$
Here $\pi_n$ is its unique <stationary distribution>, and the distance is <total variation distance>. Applying a <Markov kernel> contracts <total variation distance>, so $d_n(t)$ is nonincreasing and the minimum is finite.
Use the <ratio definition of cutoff>: a family has <cutoff for Markov chains> if, for every fixed $0<\varepsilon<1/2$,
$$
\boxed{\frac{t_{\mathrm{mix}}^{(n)}(\varepsilon)}{t_{\mathrm{mix}}^{(n)}(1-\varepsilon)}\longrightarrow1,}
$$
with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the <mixing time> scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha)/t_{\mathrm{mix}}^{(n)}(\beta)\to1$ for any fixed $\alpha,\beta\in(0,1)$.
Some definitions of <cutoff for Markov chains> additionally require the <mixing time> to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.
Back to article page
