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 条

[1] On cover times of Markov chains
Sericola, Bruno
STOCHASTIC MODELS, 2024, 40 (04) : 685 - 727
[2] Tail bounds via generic chaining
Dirksen, Sjoerd
ELECTRONIC JOURNAL OF PROBABILITY, 2015, 20 : 1 - 29
[3] Generic chaining and the l1-penalty rejoinder
van de Geer, Sara
JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 2013, 143 (06) : 1026 - 1028
[4] Hitting times, commute times, and cover times for random walks on random hypergraphs
Helali, Amine
Loewe, Matthias
STATISTICS & PROBABILITY LETTERS, 2019, 154
[5] The hitting and cover times of Metropolis walks
Nonaka, Yoshiaki
Ono, Hirotaka
Sadakane, Kunihiko
Yamashita, Masafumi
THEORETICAL COMPUTER SCIENCE, 2010, 411 (16-18) : 1889 - 1894
[6] Cover and hitting times of hyperbolic random graphs
Kiwi, Marcos
Schepers, Markus
Sylvester, John
RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (04) : 915 - 978
[7] On generic chaining and the smallest singular value of random matrices with heavy tails
Mendelson, Shahar
Paouris, Grigoris
JOURNAL OF FUNCTIONAL ANALYSIS, 2012, 262 (09) : 3775 - 3811
[8] A SIMPLE PROOF OF THE DPRZ THEOREM FOR 2D COVER TIMES
Schmidt, Marius A.
ANNALS OF PROBABILITY, 2020, 48 (01) : 445 - 457
[9] EXPECTED HITTING AND COVER TIMES OF RANDOM-WALKS ON SOME SPECIAL GRAPHS
PALACIOS, JL
RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (01) : 173 - 182
[10] A sharp estimate for cover times on binary trees
Ding, Jian
Zeitouni, Ofer
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2012, 122 (05) : 2117 - 2133

← 1 2 3 4 5 →