COVER TIMES AND GENERIC CHAINING

被引：0
|
作者：
Lehec, Joseph [1 ]
机构：
[1] Univ Paris 09, UMR CNRS 7534, F-75016 Paris, France
来源：
JOURNAL OF APPLIED PROBABILITY | 2014年 / 51卷 / 01期
关键词：
Markov chain; hitting time; cover time; generic chaining;
D O I：
暂无
中图分类号：
O21 [概率论与数理统计]; C8 [统计学];
学科分类号：
020208 ; 070103 ; 0714 ;
摘要：
A recent result of Ding, Lee and Peres (2012) expressed the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their argument is based on Dynkin's isomorphism theorem. The purpose of this article is to present an alternative approach to this problem, based only on elementary hitting time estimates and chaining arguments.
引用
收藏
页码：247 / 261
页数：15
相关论文
共 50 条
  • [31] Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
    Jambulapati, Arun
    Liu, Yang P.
    Sidford, Aaron
    PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 196 - 206
  • [32] Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
    Maier, Benjamin F.
    Huepe, Cristian
    Brockmann, Dirk
    JOURNAL OF COMPLEX NETWORKS, 2019, 7 (06) : 865 - 895
  • [33] On the Hitting Times of Quantum Versus Random Walks
    Magniez, Frederic
    Nayak, Ashwin
    Richter, Peter C.
    Santha, Miklos
    ALGORITHMICA, 2012, 63 (1-2) : 91 - 116
  • [34] On the Hitting Times of Quantum Versus Random Walks
    Frédéric Magniez
    Ashwin Nayak
    Peter C. Richter
    Miklos Santha
    Algorithmica, 2012, 63 : 91 - 116
  • [35] The cover time of a (multiple) Markov chain with rational transition probabilities is rational
    Sylvester, John
    STATISTICS & PROBABILITY LETTERS, 2022, 187
  • [36] Multiple cover time
    Winkler, P
    Zuckerman, D
    RANDOM STRUCTURES & ALGORITHMS, 1996, 9 (04) : 403 - 411
  • [37] Joint distribution of the cover time and the last visited point of finite Markov chains
    Ohwa, Takuya
    Shirai, Tomoyuki
    KYUSHU JOURNAL OF MATHEMATICS, 2008, 62 (01) : 281 - 292
  • [38] COVER LEVELS AND RANDOM INTERLACEMENTS
    Belius, David
    ANNALS OF APPLIED PROBABILITY, 2012, 22 (02) : 522 - 540
  • [39] ON THE COVER TIME OF PLANAR GRAPHS
    Jonasson, Johan
    Schramm, Oded
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2000, 5 : 85 - 90
  • [40] ON THE COVER TIME OF THE EMERGING GIANT
    Frieze, Alan M.
    Pegden, Wesley
    Tkocz, Tomasz
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (03) : 1687 - 1710
12345