×

On sensitivity of mixing times and cutoff. (English) Zbl 1387.60112

Summary: A sequence of chains exhibits (total variation) cutoff (resp., pre-cutoff) if for all \(0<\varepsilon < 1/2\), the ratio \(t_{\text{mix}}^{(n)}(\varepsilon)/t_{\text{mix}}^{(n)}(1-\varepsilon)\) tends to 1 as \(n \rightarrow \infty\) (resp., the \(\limsup\) of this ratio is bounded uniformly in \(\varepsilon\)), where \(t_{\text{mix}}^{(n)}(\varepsilon)\) is the \(\varepsilon\)-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_{\text{mix}}^{(n)}(\varepsilon)\rightarrow \infty\) as \(n \rightarrow \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 D. Aldous and J. Fill [Reversible Markov chains and random walks on graphs. Unfinished manuscript, http://www.stat.berkeley.edu/~aldous/RWG/book.html].

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G50 Sums of independent random variables; random walks
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] L. Addario-Berry and M. I. Roberts, Mixing Time Bounds via Bottleneck Sequences, Journal of Statistical Physics, (2017): 1–27. · Zbl 1403.60060
[2] D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs, (2002) Unfinished manuscript. Available at http://www.stat.berkeley.edu/ aldous/RWG/book.html.
[3] N. Alon and V. Milman, \(λ _1\) isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B 38.1 (1985): 73–88. · Zbl 0549.05051
[4] N. Alon, \(λ _1\) Eigenvalues and expanders, Combinatorica 6.2 (1986): 83–96. · Zbl 0661.05053
[5] R. Basu, J. Hermon, and Y. Peres, Characterization of cutoff for reversible Markov chains, Ann. Probab. 45.3 (2017): 1448–1487. · Zbl 1374.60129
[6] I. Benjamini, Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growth, Journal of Theoretical Probability 4.3 (1991): 631–637. · Zbl 0725.60087
[7] G. Y. Chen and L. Saloff-Coste, Comparison of cutoffs between lazy walks and Markovian semigroups, Journal of Applied Probability 50.4 (2013): 943–959. · Zbl 1288.60088
[8] P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, The Annals of Applied Probability, 6(3) (1996): 695–750. · Zbl 0867.60043
[9] J. Ding, E. Lubetzky and Y. Peres, Total variation cutoff in birth-and-death chains, Probability Theory and Related Fields 146.1-2 (2010): 61–85. · Zbl 1190.60005
[10] J. Ding and Y. Peres, Sensitivity of mixing times, Electronic Communications in Probability 18.88 (2013): 1–6. · Zbl 1307.60051
[11] N. Fountoulakis and B. A. Reed, Faster mixing and small bottlenecks, Probability Theory and Related Fields 137.3 (2007): 475–486. · Zbl 1113.60073
[12] S. Goel, R. Montenegro and P. Tetali, Mixing time bounds via the spectral profile, Electron. J. Probab 11.1 (2006): 1–26. · Zbl 1109.60061
[13] J. Hermon, On sensitivity of uniform mixing times, Annales de l’Institut Henri Poincaré Probabilités et Statistiques 54.1 (2018): 234–248. · Zbl 1396.60085
[14] J. Hermon, H. Lacoin and Y. Peres, Total Variation and Separation Cutoffs are not equivalent and neither one implies the other, Electron. J. Probab., 21(44) (2016): 1–36. · Zbl 1345.60077
[15] G. Kozma, On the precision of the spectral profile, ALEA Lat. Am. J. Probab. Math. Stat. 3 (2007): 321–329. · Zbl 1162.60335
[16] D. Levin and Y. Peres, Markov chains and mixing times, American Mathematical Soc. (2017). With contributions by Elizabeth L. Wilmer and a chapter by James G. Propp and David B. Wilson.
[17] E. Lubetzky and A. Sly, Explicit expanders with cutoff phenomena, Electronic Journal Probability 16.15 (2011): 419–435. · Zbl 1226.60098
[18] A. Lubotzky. R. Phillips and P. Sharnak, Ramanujan Graphs, Combinatorica 8.3 (1988): 261–277.
[19] M. Morgenstern, Existence and explicit constructions of q+ 1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory, Series B 62.1 (1994): 44-62. · Zbl 0814.68098
[20] B. Morris and Y. Peres, Evolving sets, mixing and heat kernel bounds, Probability Theory and Related Fields 133.2 (2005): 245–266. · Zbl 1080.60071
[21] Y. Peres. American Institute of Mathematics (AIM) research workshop “Sharp Thresholds for Mixing Times” (Palo Alto, December 2004). Summary available at http://www.aimath.org/WWN/mixingtimes.
[22] Y. Peres and P. Sousi, Mixing times are hitting times of large sets. Journal of Theoretical Probability 28.2 (2013): 1–32. · Zbl 1323.60094
[23] C. Pittet and L. Saloff-Coste, On the stability of the behavior of random walks on groups. Journal of Geometric Analysis, 10(4) (2000): 713–737. · Zbl 0985.60043
[24] A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation 82.1 (1989): 93–133. · Zbl 0668.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.