For reversible finite Markov chains, the L-infinity mixing time is at most trel log(e thit / trel), so the mixing time is comparable to the maximal hitting time exactly when the spectral gap times the hitting time remains bounded; this resolves the Aldous-Fill coalescence conjecture under…
A spectral characterization for concentration of the cover time
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated if and only if the product of the spectral-gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumption (than transitivity) that the maximal hitting time of a state is of the same order as the average hitting time.
fields
math.PR 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Some inequalities for reversible Markov chains and branching random walks via spectral optimization
For reversible finite Markov chains, the L-infinity mixing time is at most trel log(e thit / trel), so the mixing time is comparable to the maximal hitting time exactly when the spectral gap times the hitting time remains bounded; this resolves the Aldous-Fill coalescence conjecture under…