### Sensitivity of mixing times

**Jian Ding**

*(University of Chicago)*

**Yuval Peres**

*(Microsoft Research)*

#### 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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-6

Publication Date: November 11, 2013

DOI: 10.1214/ECP.v18-2765

#### References

- Aizenman, M.; Holley, R. Rapid convergence to equilibrium of stochastic Ising models in the
Dobrushin Shlosman regime.
*Percolation theory and ergodic theory of infinite particle systems (Minneapolis, Minn., 1984–1985),*1--11, IMA Vol. Math. Appl., 8,*Springer, New York,*1987. MR0894538 - D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
- Benjamini, Itai. Instability of the Liouville property for quasi-isometric graphs and
manifolds of polynomial volume growth.
*J. Theoret. Probab.*4 (1991), no. 3, 631--637. MR1115166 - I. Benjamini, G. Kozma, and N. C. Wormald. The mixing time of the giant component of a random graph. Preprint, available at http://arxiv.org/abs/math/0610459.
- Diaconis, P.; Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains.
*Ann. Appl. Probab.*6 (1996), no. 3, 695--750. MR1410112 - Fountoulakis, N.; Reed, B. A. Faster mixing and small bottlenecks.
*Probab. Theory Related Fields*137 (2007), no. 3-4, 475--486. MR2278465 - Fountoulakis, N.; Reed, B. A. The evolution of the mixing rate of a simple random walk on the giant
component of a random graph.
*Random Structures Algorithms*33 (2008), no. 1, 68--86. MR2428978 - Goel, Sharad; Montenegro, Ravi; Tetali, Prasad. Mixing time bounds via the spectral profile.
*Electron. J. Probab.*11 (2006), no. 1, 1--26 (electronic). MR2199053 - Kozma, Gady. On the precision of the spectral profile.
*ALEA Lat. Am. J. Probab. Math. Stat.*3 (2007), 321--329. MR2372888 - Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times.
With a chapter by James G. Propp and David B. Wilson.
*American Mathematical Society, Providence, RI,*2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937 - Lovász, László; Kannan, Ravi. Faster mixing via average conductance.
*Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999),*282--287,*ACM, New York,*1999. MR1798047 - Morris, B.; Peres, Yuval. Evolving sets, mixing and heat kernel bounds.
*Probab. Theory Related Fields*133 (2005), no. 2, 245--266. MR2198701 - Nachmias, Asaf; Peres, Yuval. Critical random graphs: diameter and mixing time.
*Ann. Probab.*36 (2008), no. 4, 1267--1286. MR2435849 - Y. Peres and P. Sousi. Mixing times are hitting times of large sets. Preprint, available at http://arxiv.org/abs/1108.0133.

This work is licensed under a Creative Commons Attribution 3.0 License.