Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 215 / 2 / a / Solution

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\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<\epsilon <1/2$,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 )\to 1$ 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.