Ratio definition of cutoff

ID: ratio-definition-of-cutoff

The ratio convention for cutoff for Markov chains requires for every fixed , with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph , every fixed-level mixing time is eventually one.

New to topics? Read the docs here!