Linear cover time is exponentially unlikely
| Autor: | Dubroff, Quentin, Kahn, Jeff |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is an $\varepsilon>0$ such that for any simple graph $G$ on $V$ of size $n$, and $X_0,\ldots$ an ordinary random walk on $G$, $P(\{X_0,\dots, X_{Cn}\}= V) < e^{-\varepsilon 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$. Comment: 20 pages; appendix added |
| Databáze: | arXiv |
| Externí odkaz: |
|