The Library
Convergence of mixing times for sequences of random walks on finite graphs
Tools
Croydon, David A., Hambly, Ben M. and Kumagai, Takashi. (2012) Convergence of mixing times for sequences of random walks on finite graphs. Electronic Journal of Probability, Vol.17 . article no.3. ISSN 10836489

Text
WRAP_Croydon_mixing.pdf  Submitted Version Download (323Kb) 
Official URL: http://128.208.128.142/~ejpecp/archive.php
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 GromovHausdorff sense. With this result we are able to establish the convergence of the mixing times on the largest component of the ErdosRenyi 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, GaltonWatson trees and the range of a highdimensional random walk.
[error in script] [error in script]Item Type:  Journal Article 

Subjects:  Q Science > QA Mathematics 
Divisions:  Faculty of Science > Statistics 
Library of Congress Subject Headings (LCSH):  Random walks (Mathematics), Graph theory 
Journal or Publication Title:  Electronic Journal of Probability 
Publisher:  Institute of Mathematical Statistics 
ISSN:  10836489 
Date:  5 January 2012 
Volume:  Vol.17 
Page Range:  article no.3 
Identification Number:  10.1214/EJP.v171705 
Status:  Peer Reviewed 
Publication Status:  Published 
Access rights to Published version:  Restricted or Subscription Access 
References:  [1] L. AddarioBerry, N. Broutin, and C. Goldschmidt, The continuum limit of critical random graphs, Probab. Theory Related Fields, to appear. [2] D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs, Preprint http://www.stat.berkeley.edu/∼aldous/RWG/book.html [3] M.T. Barlow, A.A. J´arai, T. Kumagai and G. Slade, Random walk on the incipient infinite cluster for oriented percolation in high dimensions, Comm. Math. Phys. 278 (2008), 385– 431. [4] I. Benjamini, G. Kozma and N. Wormald, The mixing time of the giant component of a random graph, preprint. [5] P. B´erard, G. Besson and S. Gallot, Embedding Riemannian manifolds by their heat kernel, Geom. Funct. Anal. 4 (1994), 373–398. [6] C. Borgs, J.T. Chayes, R. van der Hofstad, G. Slade and J. Spencer, Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Random Structures Algorithms, 27 137–184, 2005. [7] D. Burago, Y. Burago, and S. Ivanov, A course in metric geometry, Graduate Studies in Mathematics, vol. 33, American Mathematical Society, Providence, RI, 2001. [8] G.Y. Chen and L. SaloffCoste, The cutoff phenomenon for ergodic Markov processes, Electron. J. Probab. 13 (2008), 26–78. [9] 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. [10] , Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree, Ann. Inst. Henri Poincar´e Probab. Stat. 44 (2008), 987– 1019. [11] , Volume growth and heat kernel estimates for the continuum random tree, Probab. Theory Related Fields 140 (2008), 207–238. [12] , Random walk on the range of random walk, J. Stat. Phys. 136 (2009), 349–372. [13] , Scaling limits for simple random walks on random ordered graph trees, Adv. in Appl. Probab. 42 (2010), 528–558. [14] D. A. Croydon and B. M. Hambly, Local limit theorems for sequences of simple random walks on graphs, Potential Anal. 29 (2008), 351–389. [15] T. Duquesne, A limit theorem for the contour process of conditioned GaltonWatson trees, Ann. Probab. 31 (2003), 996–1027. [16] T. Duquesne and J.F. Le Gall, Probabilistic and fractal aspects of L´evy trees, Probab. Theory Related Fields 131 (2005), 553–603. [17] P. Erd˝os and S. J. Taylor, Some intersection properties of random walk paths, Acta Math. Acad. Sci. Hungar. 11 (1960), 231–248. [18] N. Fountoulakis and B.A. Reed, The evolution of the mixing rate of a simple random walk on the giant component of a random graph, Random Structures Algorithms, 33 (2008), 68–86. [19] M. Fukushima, Y. Oshima and M. Takeda, Dirichlet forms and symmetric Markov processes, de Gruyter Studies in Mathematics, 19. Walter de Gruyter & Co., Berlin, 2011. [20] B. V. Gnedenko and A. N. Kolmogorov, Limit distributions for sums of independent random variables, AddisonWesley Publishing Company, Inc., Cambridge, Mass., 1954, Translated and annotated by K. L. Chung. With an Appendix by J. L. Doob. [21] S. Goel, R. Montenegro, and P. Tetali, Mixing time bounds via the spectral profile, Electron. J. Probab. 11 (2006), 1–26. [22] A. Greven, P. Pfaffelhuber, and A. Winter, Convergence in distribution of random metric measure spaces (Λcoalescent measure trees), Probab. Theory Related Fields 145 (2009), 285–322. [23] M. Heydenreich and R. van der Hofstad, Random graph asymptotics on highdimensional tori II. Volume, diameter and mixing time, Probab. Theory Related Fields, 149 (2011), 397–415. [24] A. Kasue and H. Kumura, Spectral convergence of Riemannian manifolds, Tˆohoku Math. J. 46 (1994), 147–179. [25] D. P. Kennedy, The distribution of the maximum Brownian excursion, J. Appl. Probab. 13 (1976), 371–376. [26] J. Kigami, Resistance forms, quasisymmetric maps and heat kernel estimates, Memoirs AMS, to appear. [27] J. Kigami, Hausdorff dimensions of selfsimilar sets and shortest path metrics, J. Math. Soc. Japan 47 (1995), 381–404. [28] J. Kigami, Harmonic calculus on limits of networks and its application to dendrites, J. Funct. Anal. 128 (1995), 48–86. [29] J. Kigami, Analysis on fractals, Cambridge Tracts in Mathematics, vol. 143, Cambridge University Press, Cambridge, 2001. [30] T. Kumagai, Homogenization on finitely ramified fractals, Stochastic analysis and related topics in Kyoto, Adv. Stud. Pure Math., vol. 41, Math. Soc. Japan, Tokyo, 2004, pp. 189– 207. [31] T. Kumagai and S. Kusuoka, Homogenization on nested fractals, Probab. Theory Related Fields 104 (1996), 375398. [32] T. Kumagai and J. Misumi, Heat kernel estimates for strongly recurrent random walk on random media, J. Theoret. Probab. 21 (2008), 910–935. [33] J.F. Le Gall, Random real trees, Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), 35–62. [34] D. Levin, Y. Peres and E. Wilmer, Markov chains and mixing times, Amer. Math. Soc., Providence, RI, 2009. [35] A. Nachmias and Y. Peres, Critical random graphs: diameter and mixing time, Ann. Probab. 36 (2008), 1267–1286. [36] A. Nachmias and Y. Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010), 29–41. 
URI:  http://wrap.warwick.ac.uk/id/eprint/39472 
Actions (login required)
View Item 