## On sensitivity of mixing times and cutoff

##### View / Open Files

##### Journal Title

Electronic Journal of Probability

##### ISSN

1083-6489

##### Publisher

Institute of Mathematical Statistics

##### Volume

23

##### Issue

2018

##### Number

25

##### Type

Article

##### This Version

VoR

##### Metadata

Show full item record##### Citation

Hermon, J., & Peres, Y. (2018). On sensitivity of mixing times and cutoff. Electronic Journal of Probability, 23 (2018. 25)https://doi.org/10.1214/18-EJP154

##### Abstract

A sequence of chains exhibits (total-variation) cutoff (resp., pre-cutoff) if
for all $0<\epsilon< 1/2$, the ratio
$t_{\mathrm{mix}}^{(n)}(\epsilon)/t_{\mathrm{mix}}^{(n)}(1-\epsilon)$ tends to
1 as $n \to \infty $ (resp., the $\limsup$ of this ratio is bounded uniformly
in $\epsilon$), where $t_{\mathrm{mix}}^{(n)}(\epsilon)$ is the
$\epsilon$-total-variation mixing-time of the $n$th chain in the sequence. We
construct a sequence of bounded degree graphs $G_n$, such that the lazy simple
random walks (LSRW) on $G_n$ satisfy the "product condition" $\mathrm{gap}(G_n)
t_{\mathrm{mix}}^{(n)}(\epsilon) \to \infty $ as $n \to \infty$, where
$\mathrm{gap}(G_n)$ is the spectral gap of the LSRW on $G_n$ (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 $G_n=(V_{n},E_{n})$
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 $\Theta (\log |V_n|)$. Similarly, we also show that "lumping"
states together may increase the order of the mixing-time by an optimal factor
of $\Theta (\log |V_n|)$. This gives a negative answer to a question asked by
Aldous and Fill.

##### Keywords

math.PR, math.PR, 60J10

##### Relationships

Is supplemented by: https://doi.org/10.1214/18-EJP154

##### Identifiers

External DOI: https://doi.org/10.1214/18-EJP154

This record's URL: https://www.repository.cam.ac.uk/handle/1810/276128

## Recommended or similar items

The following licence files are associated with this item: