Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 c Solution Created 2026-10-03 Updated 2026-10-06
Let be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap . For a finite irreducible Markov chain that is an aperiodic Markov chain, .
For , choose a real eigenfunction whose eigenvalue has modulus , and an initial state maximizing . It has , and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, . At , for ,The second inequality follows from , the supplied inequality with . Since ,When the left side is zero, so no logarithm of zero is needed. For the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention the bound is again trivial.
Pre-cutoff for Markov chains Created 2026-09-28 Updated 2026-11-05
A sequence of finite irreducible Markov chains exhibits pre-cutoff if there are constants and times such that its worst-case total variation distance satisfiesThis only bounds the transition between two fixed multiples of a scale; cutoff requires the transition window to be negligible relative to the mixing scale.
For reversible aperiodic chains with , pre-cutoff implies the product condition . In fact the analogous Absolute relaxation time must be negligible too. To see the mechanism, the two distance limits make comparable to . If is the largest nontrivial eigenvalue modulus, the Eigenvalue lower bound for total variation mixing gives . The limit at forces , which implies when . The ordinary spectral gap is at least , giving the ordinary product condition.
The diverging-scale hypothesis matters. Nonlazy simple random walk on the complete graph has and , so the displayed pre-cutoff convention holds on the bounded scale , but its Relaxation time is not negligible relative to its mixing time.