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.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 d Solution Created 2026-10-03 Updated 2026-10-06
Use the ratio definition of cutoff from part (a), and write . In the reversible Markov chain setting of the preceding parts let and . In particular .
If did not tend to infinity, there would be a subsequence and for which . Along it part (c) implies, for every fixed ,Since , choose fixed so small that . The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for or for , which is at least . No real ordering of complex eigenvalues is implicit.
For the requested counterexample take nonlazy simple random walk on the complete graph , . Let have every row equal to the uniform distribution on a finite set, and let . ThenThus and : every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is and the absolute one is , so both products with tend to one, not infinity. The divergence assumption on is therefore essential under this convention.
Peres product condition Created 2026-10-06 Updated 2026-11-05
For finite irreducible Markov chains that are aperiodic Markov chains and reversible Markov chains, the ratio definition of cutoff and imply the Peres product condition, with . If on a subsequence, then and the eigenvalue lower bound for total variation mixing giveFor sufficiently small fixed , this contradicts the limit one forced by cutoff for Markov chains. The same argument proves the stronger conclusion .
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.