Sensitivity of mixing times of Cayley graphs
Open Access
- 18 July 2023
- journal article
- research article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 76 (4) , 1400-1431
Abstract
We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs, we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to $1+o(1)$ .
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Sensitivity of mixing timesElectronic Communications in Probability, 2013
- Mathematical Aspects of Mixing Times in Markov ChainsFoundations and Trends® in Theoretical Computer Science, 2006
- Mixing Time Bounds via the Spectral ProfileElectronic Journal of Probability, 2006
- Evolving sets, mixing and heat kernel boundsProbability Theory and Related Fields, 2005
- On the stability of the behavior of random walks on groupsThe Journal of Geometric Analysis, 2000
- Logarithmic Sobolev inequalities for finite Markov chainsThe Annals of Applied Probability, 1996
- Comparison Theorems for Reversible Markov ChainsThe Annals of Applied Probability, 1993
- Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growthJournal of Theoretical Probability, 1991
- Random Walks on Discrete Groups: Boundary and EntropyThe Annals of Probability, 1983
- Some Inequalities for Reversible Markov ChainsJournal of the London Mathematical Society, 1982