Concentration of hitting times in Erdős-Rényi graphs

被引:2
|
作者
Ottolini, Andrea [1 ]
Steinerberger, Stefan [1 ]
机构
[1] Univ Washington, Dept Math, Seattle, WA 98195 USA
关键词
Erd & odblac; s-R & eacute; nyi graphs; hitting time; random walk;
D O I
10.1002/jgt.23119
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider Erd & odblac;s-R & eacute;nyi graphs G(n,p) $G(n,p)$ for 0<p<1 $0\lt p\lt 1$ fixed and n ->infinity $n\to \infty $ and study the expected number of steps, Hwv ${H}_{wv}$, that a random walk started in w $w$ needs to first arrive in v $v$. A natural guess is that an Erd & odblac;s-R & eacute;nyi random graph is so homogeneous that it does not really distinguish between vertices and Hwv=(1+o(1))n ${H}_{wv}=(1+o(1))n$. L & ouml;we-Terveer established a CLT for the Mean Starting Hitting Time suggesting Hwv=n +/- O(n) ${H}_{wv}=n\pm {\mathscr{O}}(\sqrt{n})$. We prove the existence of a strong concentration phenomenon: Hwv ${H}_{wv}$ is given, up to a very small error of size less than or similar to(logn)3/2/n $\lesssim {(\mathrm{log}n)}<^>{3\unicode{x02215}2}\unicode{x02215}\sqrt{n}$, by an explicit simple formula involving only the total number of edges divided by E divided by $| E| $, the degree deg(v) $\text{deg}(v)$ and the distance d(v,w) $d(v,w)$.
引用
收藏
页码:245 / 262
页数:18
相关论文
共 20 条
  • [1] The Hitting Times of Random Walks on Bicyclic Graphs
    Xiaomin Zhu
    Xiao-Dong Zhang
    Graphs and Combinatorics, 2021, 37 : 2365 - 2386
  • [2] Cover and hitting times of hyperbolic random graphs
    Kiwi, Marcos
    Schepers, Markus
    Sylvester, John
    RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (04) : 915 - 978
  • [3] The Hitting Times of Random Walks on Bicyclic Graphs
    Zhu, Xiaomin
    Zhang, Xiao-Dong
    GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2365 - 2386
  • [4] An Explicit Formula of Hitting Times for Random Walks on Graphs
    Xu, Hao
    Yau, Shing-Tung
    PURE AND APPLIED MATHEMATICS QUARTERLY, 2014, 10 (03) : 567 - 581
  • [5] Finding hitting times in various graphs
    Rao, Shravas K.
    STATISTICS & PROBABILITY LETTERS, 2013, 83 (09) : 2067 - 2072
  • [6] Hitting Times of Random Walks on Edge Corona Product Graphs
    Zhu, Mingzhe
    Xu, Wanyue
    Li, Wei
    Zhang, Zhongzhi
    Kan, Haibin
    COMPUTER JOURNAL, 2024, 67 (02) : 485 - 497
  • [7] 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
  • [8] Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs
    Zeng, Yibo
    Zhang, Zhongzhi
    COMPUTER JOURNAL, 2021, 64 (01) : 76 - 92
  • [9] Means of Hitting Times for Random Walks on Graphs: Connections, Computation, and Optimization
    Xia, Haisong
    Xu, Wanyue
    Zhang, Zuobai
    Zhang, Zhongzhi
    ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2025, 19 (02)
  • [10] Hitting times for random walks on subdivision and triangulation graphs
    Chen, Haiyan
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (01) : 117 - 130