On the mean and variance of cover times for random walks on graphs

被引：0
|
作者：
Ball, F [1 ]
Dunham, B [1 ]
Hirschowitz, A [1 ]
机构：
[1] UNIV EDINBURGH,DEPT COMP SCI,EDINBURGH EH9 3JZ,MIDLOTHIAN,SCOTLAND
来源：
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS | 1997年 / 207卷 / 02期
关键词：
D O I：
10.1006/jmaa.1997.5298
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A method is described for calculating the mean cover time for a particle performing a simple random walk on the vertices of a finite connected graph. The method also yields the variance and generating function of the cover time. A computer program is available which utilises the approach to provide results for vertex symmetric graphs. Some examples are given. (C) 1997 Academic Press.
引用
收藏
页码：506 / 514
页数：9
相关论文
共 50 条
  • [21] Cover and hitting times of hyperbolic random graphs
    Kiwi, Marcos
    Schepers, Markus
    Sylvester, John
    RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (04) : 915 - 978
  • [22] 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
  • [23] Convergence of blanket times for sequences of random walks on critical random graphs
    Andriopoulos, George
    COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (03) : 478 - 515
  • [24] Cover time and mixing time of random walks on dynamic graphs
    Avin, Chen
    Koucky, Michal
    Lotker, Zvi
    RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (04) : 576 - 596
  • [25] Multiple random walks on graphs: mixing few to cover many
    Rivera, Nicolas
    Sauerwald, Thomas
    Sylvester, John
    COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (04) : 594 - 637
  • [26] Cover times for Brownian motion and random walks in two dimensions
    Dembo, A
    Peres, Y
    Rosen, J
    Zeitouni, O
    ANNALS OF MATHEMATICS, 2004, 160 (02) : 433 - 464
  • [27] 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
  • [28] Expected hitting times for random walks on quadrilateral graphs and their applications
    Huang, Jing
    Li, Shuchao
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (12): : 2389 - 2408
  • [29] 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
  • [30] Expected hitting times for random walks on weak products of graphs
    González-Arévalo, B
    Palacios, JL
    STATISTICS & PROBABILITY LETTERS, 1999, 43 (01) : 33 - 39
12345