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 1083-6489

Preview

Text WRAP_Croydon_mixing.pdf - Submitted Version Download (323Kb)

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 Erdos-Renyi 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.

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:	1083-6489
Date:	5 January 2012
Volume:	Vol.17
Page Range:	article no.3
Identification Number:	10.1214/EJP.v17-1705
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
References:	[1] L. Addario-Berry, 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. Saloff-Coste, 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 Galton-Watson 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, Addison-Wesley 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 high-dimensional 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 self-similar 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), 375-398. [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

Request changes to a record

Actions (login required)

View Item