Sensitivity of mixing times
Authors:
Open Access
- 1 January 2013
- journal article
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 18 (none) , 1-6-6
Abstract
In this note, we demonstrate an instance of bounded-degree graphs of size $n$, for which the total variation mixing time for the random walk is decreased by a factor of $\log n/ \log\log n$ if we multiply the edge-conductances by bounded factors in a certain way.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Mixing Times are Hitting Times of Large SetsJournal of Theoretical Probability, 2013
- Critical random graphs: Diameter and mixing timeThe Annals of Probability, 2008
- The evolution of the mixing rate of a simple random walk on the giant component of a random graphRandom Structures & Algorithms, 2008
- Faster Mixing and Small BottlenecksProbability Theory and Related Fields, 2006
- Mixing Time Bounds via the Spectral ProfileElectronic Journal of Probability, 2006
- Evolving sets, mixing and heat kernel boundsProbability Theory and Related Fields, 2005
- Faster mixing via average conductance1999
- Logarithmic Sobolev inequalities for finite Markov chainsThe Annals of Applied Probability, 1996
- Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growthJournal of Theoretical Probability, 1991
- Rapid Convergence to Equilibrium of Stochastic Ising Models in the Dobrushin Shlosman Regime1987