Convergence of blanket times for sequences of random walks on critical random graphs

被引:0
|
作者
Andriopoulos, George [1 ]
机构
[1] NYU Shanghai, NYU ECNU Inst Math Sci, Shanghai, Peoples R China
基金
英国工程与自然科学研究理事会;
关键词
random walk in random environment; blanket time; Gromov-Hausdorff convergence; Galton-Watson tree; Erdos-Renyi random graph; BROWNIAN-MOTION; SCALING LIMITS; LOCAL-TIMES; TREES;
D O I
10.1017/S0963548322000359
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Under the assumption that sequences of graphs equipped with resistances, associated measures, walks and local times converge in a suitable Gromov-Hausdorff topology, we establish asymptotic bounds on the distribution of the e-blanket times of the random walks in the sequence. The precise nature of these bounds ensures convergence of the epsilon-blanket times of the random walks if the e-blanket time of the limiting diffusion is continuous at e with probability 1. This result enables us to prove annealed convergence in various examples of critical random graphs, including critical Galton-Watson trees and the Erdos-Renyi random graph in the critical window. We highlight that proving continuity of the epsilon-blanket time of the limiting diffusion relies on the scale invariance of a finite measure that gives rise to realizations of the limiting compact random metric space, and therefore we expect our results to hold for other examples of random graphs with a similar scale invariance property.
引用
收藏
页码:478 / 515
页数:38
相关论文
共 50 条
  • [1] Convergence of mixing times for sequences of random walks on finite graphs
    Croydon, D. A.
    Hambly, B. M.
    Kumagai, T.
    ELECTRONIC JOURNAL OF PROBABILITY, 2012, 17 : 1 - 32
  • [2] Meeting times of random walks on graphs
    Bshouty, NH
    Higham, L
    Warpechowska-Gruca, J
    INFORMATION PROCESSING LETTERS, 1999, 69 (05) : 259 - 265
  • [3] The Hitting Times of Random Walks on Bicyclic Graphs
    Zhu, Xiaomin
    Zhang, Xiao-Dong
    GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2365 - 2386
  • [4] Hitting times for random walks on tricyclic graphs
    Zhu, Xiao-Min
    Yang, Xu
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2023, 20 (01) : 65 - 72
  • [5] The Hitting Times of Random Walks on Bicyclic Graphs
    Xiaomin Zhu
    Xiao-Dong Zhang
    Graphs and Combinatorics, 2021, 37 : 2365 - 2386
  • [6] Linking the mixing times of random walks on static and dynamic random graphs
    Avena, Luca
    Guldas, Hakan
    van Der Hofstad, Remco
    den Hollander, Frank
    Nagy, Oliver
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2022, 153 : 145 - 182
  • [7] Random Walks on Random Graphs
    Cooper, Colin
    Frieze, Alan
    NANO-NET, 2009, 3 : 95 - +
  • [8] Hitting Times for Random Walks on Sierpiski Graphs and Hierarchical Graphs
    Qi, Yi
    Dong, Yuze
    Zhang, Zhongzhi
    Zhang, Zhang
    COMPUTER JOURNAL, 2020, 63 (09): : 1385 - 1396
  • [9] On the mean and variance of cover times for random walks on graphs
    Ball, F
    Dunham, B
    Hirschowitz, A
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1997, 207 (02) : 506 - 514
  • [10] Hitting times for random walks on subdivision and triangulation graphs
    Chen, Haiyan
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (01): : 117 - 130