A Spectral Characterization for Concentration of the Cover Time
- PDF / 414,970 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 134 Views
A Spectral Characterization for Concentration of the Cover Time Jonathan Hermon1 Received: 18 January 2019 / Revised: 16 September 2019 © The Author(s) 2019
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. Keywords Mixing times · Hitting times · Cover times · Vertex-transitive graphs · Spectral gap Mathematics Subject Classification (2010) 60J10 · 60J27
1 Introduction A big part of the modern theory of Markov chains is dedicated to the study of the hierarchy of different quantities associated with a Markov chain. It is a common theme that certain phenomena can be characterized by a simple criterion concerning whether or not two such quantities are strongly separated (i.e., are of strictly different orders). Often, one of these quantities is the inverse of the spectral gap. One instance is the cutoff phenomenon and the condition that the product of the mixing time and the spectral gap diverges, known as the product condition (a necessary condition for precutoff in total variation [32, Proposition 18.4] and a necessary and sufficient condition for cutoff in L 2 [14]). The condition that the product of the spectral gap and the maximal (expected) hitting time diverges is studied in [1] and [28, Theorem 1]). Aldous’ classic criterion for concentration of the cover time [4] is another such instance. Aldous’ criterion asserts that for a sequence of Markov chains on finite state Financial support by the EPSRC Grant EP/L018896/1.
B 1
Jonathan Hermon [email protected] University of Cambridge, Cambridge, UK
123
Journal of Theoretical Probability
spaces of diverging sizes
(n)
τcov (n)
tcov
(n)
(n)
→ 1 in distribution if tcov /thit → ∞, where throughout
the superscript ‘(n)’ indicates that we are considering the nth Markov chain in the sequence, and where τcov = inf{t : {X s : s t} = V } is the cover time of a Markov chain (X t )t 0 on a finite state space V , defined to be the first time by which every state was visited at least once by the chain, tcov := max Ex [τcov ] x∈V
its worst-case expectation and thit := max Ex [Ty ], x,y
where
Ty := inf{t : X t = y},
is the maximal expected hitting time of a state. More precisely, Aldous [4, Proposition (n) (n) = (tcov ), then there exists a sequence of 1] showed that in the reversible case if thit (n) (n) initial states such that τcov /tcov does not concentrate around any value.1,2 Conversely (n) (n) (n) (n) (n) (even without reversibility) tcov min y E y [τcov ] + thit and when tcov /thit → ∞, we have that
(n)
tcov
(n) min y E y [τcov ]
→ 1 and that
(n)
τcov (n) tcov
→ 1 in distribution for every sequence of
initial states. Our Theorem 1 refines Aldous’ crit
Data Loading...
