In this paper we study the time required for a @math -biased ( @math ) walk to visit all nodes of a supercritical Galton-Watson tree up to generation @math . Inspired by the extremal landscape approach in [ 2018] for simple random walk on binary trees, we establish the near-independent nature of extremal points for the @math -biased walk, and deduce the scaling limit of the cover time.
More precise results can be obtained if we restrict to particular graphs. Postponding our topic of trees to the next paragraph, the most studied situation is the two-dimensional torus. The first order estimation of its cover time was determined in @cite_7 , then the result was ameliorated in Ding @cite_12 , Belius and Kistler @cite_9 , Abe @cite_8 , and most recently @cite_1 to the extend that @math where @math is a 2-dimensional manifold with some regularity conditions, @math is the area of @math , and @math is the time for the walk to intersect every ball of radius @math on @math .
@cite_7 @cite_8 @cite_9 @cite_1 @cite_12
2257118316 2760496220 1987243055 2949555217
The ( )-cover time of the two dimensional torus by Brownian motion is the time it takes for the process to come within distance ( >0 ) from any point. Its leading order in the small ( )-regime has been established by (Ann Math 160:433–464, 2004). In this work, the second order correction is identified. The approach relies on a multi-scale refinement of the second moment method, and draws on ideas from the study of the extremes of branching Brownian motion. We consider the cover time for a simple random walk on the two-dimensional discrete torus of side length @math . Dembo, Peres, Rosen, and Zeitouni [Ann. Math. 160:433-464, 2004] identified the leading term in the asymptotics for the cover time as @math goes to infinity. In this paper, we study the exact second order term. This is a discrete analogue of the work on the cover time for planar Brownian motion by Belius and Kistler [Probab. Theory Relat Fields. 167:461-552, 2017]. 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. We study the cover time @math by (continuous-time) random walk on the 2D box of side length @math with wired boundary or on the 2D torus, and show that in both cases with probability approaching 1 as @math increases, @math . This improves a result of Dembo, Peres, Rosen, and Zeitouni (2004) and makes progress towards a conjecture of Bramson and Zeitouni (2009).