Gumbel fluctuations for cover times in the discrete torus
- PDF / 720,780 Bytes
- 55 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 151 Views
Gumbel fluctuations for cover times in the discrete torus David Belius
Received: 3 February 2012 / Revised: 23 October 2012 © Springer-Verlag Berlin Heidelberg 2013
Abstract This work proves that the fluctuations of the cover time of simple random walk in the discrete torus of dimension at least three with large side-length are governed by the Gumbel extreme value distribution. This result was conjectured for example in Aldous and Fill (Reversible Markov chains and random walks on graphs, in preparation). We also derive some corollaries which qualitatively describe “how” covering happens. In addition, we develop a new and stronger coupling of the model of random interlacements, introduced by Sznitman (Ann Math (2) 171(3):2039–2087, 2010), and random walk in the torus. This coupling is used to prove the cover time result and is also of independent interest. Mathematics Subject Classification
60G50 · 60D05 · 60G55
1 Introduction In this article we prove that if C N is the cover time of the discrete torus of side-length N and dimension d ≥ 3 then C N /(g(0)N d ) − log N d (where g(·) is the Zd Green function) tends in law to the Gumbel distribution as N → ∞, or in other words, that the fluctuations of the cover time are governed by the Gumbel distribution. This result was conjectured e.g. in [3, Chapter 7, p. 23]. We also construct a new stronger coupling of random walk in the torus and the model of random interlacements, thus improving a result from [25]. The coupling is of independent interest and is also used as a tool to prove the cover time result.
This research has been supported by the grant ERC-2009-AdG 245728-RWPERCRI. D. Belius (B) ETH Zurich, Zurich, Switzerland e-mail: [email protected]
123
D. Belius
Cover times of finite graphs by simple random walk have been studied extensively, see e.g. [1–3,8,9,15]. One important case is the cover time of the discrete torus T N = (Z/N Z)d . Let P be the canonical law of continuous time simple random walk in this graph, starting from the uniform distribution, and let the canonical process be denoted by (Yt )t≥0 . The cover time of the discrete torus is the first time Y· has visited every vertex of the graph, or in other words C N = max Hx , x∈T N
(1.1)
where Hx denotes the entrance time of the vertex x ∈ T N . For d ≥ 3 it is known that E[C N ] ∼ g(0)N d log N d , as N → ∞, and that C N concentrates in the sense C
that g(0)N d Nlog N d → 1 in probability, as N → ∞. However previously it was only conjectured that the finer scaling result CN law − log N d −→ G as N → ∞, for d ≥ 3, g(0)N d
(1.2)
holds, where G denotes the standard Gumbel distribution, with cumulative distribution −z function F(z) = e−e (see e.g. Chapter 7, pp. 22–23, [3]). In this article we prove (1.2). In fact our result, Theorem 3.1, proves more, namely that the (appropriately defined) cover time of any “large” subset of T N satisfies a similar relation. (For d = 1, 2, the asymptotic behaviour of E[C N ] is different; see [9] for d = 2, the case d = 1 is an exercise in classical pr
Data Loading...
