LINEAR COVER TIME IS EXPONENTIALLY UNLIKELY
成果类型：
Article
署名作者：
Dubroff, Quentin; Kahn, Jeff
署名单位：
Rutgers University System; Rutgers University New Brunswick
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/24-AOP1699
发表日期：
2025
页码：
1-22
关键词：
摘要：
Proving a 2009 conjecture of Itai Benjamini, we show: Theorem. For any C there is an epsilon > 0 such that for any simple graph G on V of size n, and X-0, ... an ordinary random walk on G, P ({ X- 0 ,...,X (C n )} = V ) < e (- epsilon n) . A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are sufficiently small relative to C .