Convergence of mixing times for sequences of random walks on finite graphs

David A Croydon (University of Warwick)
Ben M Hambly (University of Oxford)
Takashi Kumagai (Kyoto University)

Abstract


We establish conditions on sequences of graphs which ensure that the mixing times of the random walks on the graphs in the sequence converge. The main assumption is that the graphs, associated measures and heat kernels converge in a suitable Gromov-Hausdorff sense. With this result we are able to establish the convergence of the mixing times on the largest component of the Erdős-Rényi random graph in the critical window, sharpening previous results for this random graph model. Our results also enable us to establish convergence in a number of other examples, such as finitely ramified fractal graphs, Galton-Watson trees and the range of a high-dimensional random walk.


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

Pages: 1-32

Publication Date: January 5, 2012

DOI: 10.1214/EJP.v17-1705

References

  • L. Addario-Berry, N. Broutin, and C. Goldschmidt, The continuum limit of critical random graphs, Probab. Theory Related Fields, to appear.
  • D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs, Preprint http://www.stat.berkeley.edu/~aldous/RWG/book.html
  • Barlow, Martin T.; Járai, Antal A.; Kumagai, Takashi; Slade, Gordon. Random walk on the incipient infinite cluster for oriented percolation in high dimensions. Comm. Math. Phys. 278 (2008), no. 2, 385--431. MR2372764
  • I. Benjamini, G. Kozma and N. Wormald, The mixing time of the giant component of a random graph, preprint.
  • Bérard, P.; Besson, G.; Gallot, S. Embedding Riemannian manifolds by their heat kernel. Geom. Funct. Anal. 4 (1994), no. 4, 373--398. MR1280119
  • Borgs, Christian; Chayes, Jennifer T.; van der Hofstad, Remco; Slade, Gordon; Spencer, Joel. Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 (2005), no. 2, 137--184. MR2155704
  • Burago, Dmitri; Burago, Yuri; Ivanov, Sergei. A course in metric geometry. Graduate Studies in Mathematics, 33. American Mathematical Society, Providence, RI, 2001. xiv+415 pp. ISBN: 0-8218-2129-6 MR1835418
  • Chen, Guan-Yu; Saloff-Coste, Laurent. The cutoff phenomenon for ergodic Markov processes. Electron. J. Probab. 13 (2008), no. 3, 26--78. MR2375599
  • D. A. Croydon, Scaling limit for the random walk on the largest connected component of the critical random graph, Publ. RIMS. Kyoto Univ., to appear.
  • Croydon, David. Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree. Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), no. 6, 987--1019. MR2469332
  • Croydon, David A. Volume growth and heat kernel estimates for the continuum random tree. Probab. Theory Related Fields 140 (2008), no. 1-2, 207--238. MR2357676
  • Croydon, David A. Random walk on the range of random walk. J. Stat. Phys. 136 (2009), no. 2, 349--372. MR2525250
  • Croydon, D. A. Scaling limits for simple random walks on random ordered graph trees. Adv. in Appl. Probab. 42 (2010), no. 2, 528--558. MR2675115
  • Croydon, D. A.; Hambly, B. M. Local limit theorems for sequences of simple random walks on graphs. Potential Anal. 29 (2008), no. 4, 351--389. MR2453564
  • D. A. Croydon, B. M. Hambly and T. Kumagai, Convergence of mixing times for sequences of random walks on finite graphs (extended version), arXiv:1111.0108.
  • Duquesne, Thomas. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), no. 2, 996--1027. MR1964956
  • Duquesne, Thomas; Le Gall, Jean-François. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 (2005), no. 4, 553--603. MR2147221
  • Erdős, P.; Taylor, S. J. Some intersection properties of random walk paths. Acta Math. Acad. Sci. Hungar. 11 1960 231--248. MR0126299
  • 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
  • Fukushima, Masatoshi; Oshima, Yoichi; Takeda, Masayoshi. Dirichlet forms and symmetric Markov processes. Second revised and extended edition. de Gruyter Studies in Mathematics, 19. Walter de Gruyter & Co., Berlin, 2011. x+489 pp. ISBN: 978-3-11-021808-4 MR2778606
  • Gnedenko, B. V.; Kolmogorov, A. N. Limit distributions for sums of independent random variables. Translated from the Russian, annotated, and revised by K. L. Chung. With appendices by J. L. Doob and P. L. Hsu. Revised edition Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills., Ont. 1968 ix+293 pp. MR0233400
  • Goel, Sharad; Montenegro, Ravi; Tetali, Prasad. Mixing time bounds via the spectral profile. Electron. J. Probab. 11 (2006), no. 1, 1--26 (electronic). MR2199053
  • Greven, Andreas; Pfaffelhuber, Peter; Winter, Anita. Convergence in distribution of random metric measure spaces ($\Lambda$-coalescent measure trees). Probab. Theory Related Fields 145 (2009), no. 1-2, 285--322. MR2520129
  • Heydenreich, Markus; van der Hofstad, Remco. Random graph asymptotics on high-dimensional tori II: volume, diameter and mixing time. Probab. Theory Related Fields 149 (2011), no. 3-4, 397--415. MR2776620
  • Kasue, Atsushi; Kumura, Hironori. Spectral convergence of Riemannian manifolds. Tohoku Math. J. (2) 46 (1994), no. 2, 147--179. MR1272877
  • Kennedy, Douglas P. The distribution of the maximum Brownian excursion. J. Appl. Probability 13 (1976), no. 2, 371--376. MR0402955
  • J. Kigami, Resistance forms, quasisymmetric maps and heat kernel estimates, Memoirs Amer. Math. Soc. to appear.
  • Kigami, Jun. Hausdorff dimensions of self-similar sets and shortest path metrics. J. Math. Soc. Japan 47 (1995), no. 3, 381--404. MR1331321
  • Kigami, Jun. Harmonic calculus on limits of networks and its application to dendrites. J. Funct. Anal. 128 (1995), no. 1, 48--86. MR1317710
  • Kigami, Jun. Analysis on fractals. Cambridge Tracts in Mathematics, 143. Cambridge University Press, Cambridge, 2001. viii+226 pp. ISBN: 0-521-79321-1 MR1840042
  • Kumagai, Takashi. Homogenization on finitely ramified fractals. Stochastic analysis and related topics in Kyoto, 189--207, Adv. Stud. Pure Math., 41, Math. Soc. Japan, Tokyo, 2004. MR2083710
  • Kumagai, T.; Kusuoka, S. Homogenization on nested fractals. Probab. Theory Related Fields 104 (1996), no. 3, 375--398. MR1376343
  • Kumagai, Takashi; Misumi, Jun. Heat kernel estimates for strongly recurrent random walk on random media. J. Theoret. Probab. 21 (2008), no. 4, 910--935. MR2443641
  • Le Gall, Jean-François. Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35--62. MR2225746
  • 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
  • Nachmias, Asaf; Peres, Yuval. Critical random graphs: diameter and mixing time. Ann. Probab. 36 (2008), no. 4, 1267--1286. MR2435849
  • Nachmias, Asaf; Peres, Yuval. The critical random graph, with martingales. Israel J. Math. 176 (2010), 29--41. MR2653185
Bookmark and Share


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