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.
Bookmark and Share


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