Repository logo
 

On sensitivity of mixing times and cutoff

Published version
Peer-reviewed

Type

Article

Change log

Authors

Peres, Yuval 

Abstract

A sequence of chains exhibits (total-variation) cutoff (resp., pre-cutoff) if for all 0<ϵ<1/2, the ratio tmix(n)(ϵ)/tmix(n)(1−ϵ) tends to 1 as $n \to \infty $ (resp., the lim sup of this ratio is bounded uniformly in ϵ), where tmix(n)(ϵ) is the ϵ-total-variation mixing-time of the nth chain in the sequence. We construct a sequence of bounded degree graphs Gn, such that the lazy simple random walks (LSRW) on Gn satisfy the "product condition" $\mathrm{gap}(G_n) t_{\mathrm{mix}}^{(n)}(\epsilon) \to \infty $ as n, where gap(Gn) is the spectral gap of the LSRW on Gn (a known necessary condition for pre-cutoff that is often sufficient for cutoff), yet this sequence does not exhibit pre-cutoff. Recently, Chen and Saloff-Coste showed that total-variation cutoff is equivalent for the sequences of continuous-time and lazy versions of some given sequence of chains. Surprisingly, we show that this is false when considering separation cutoff. We also construct a sequence of bounded degree graphs Gn=(Vn,En) that does not exhibit cutoff, for which a certain bounded perturbation of the edge weights leads to cutoff and increases the order of the mixing-time by an optimal factor of Θ(log⁡|Vn|). Similarly, we also show that "lumping" states together may increase the order of the mixing-time by an optimal factor of Θ(log⁡|Vn|). This gives a negative answer to a question asked by Aldous and Fill.

Description

Keywords

math.PR, math.PR, 60J10

Journal Title

Electronic Journal of Probability

Conference Name

Journal ISSN

1083-6489
1083-6489

Volume Title

23

Publisher

Institute of Mathematical Statistics
Relationships
Is supplemented by: