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.
The case of simple random walk on binary trees received extensive studies recently, originally as a counterexample showing that in second order, cover time is no longer determined by the corresponding GFF (cf. @cite_4 ). A second order result with error @math was given in Ding and Zeitouni @cite_4 , then refined to @math in @cite_5 by second moment methods, and a scaling limit was given in @cite_6 using an extremal landscape approach, @math for some implicit constant @math and explicit distribution @math (the sum of two independent copies of the limit of the derivative martingale associated with the branching random walk).
@cite_5 @cite_4 @cite_6
2760681307 2001123643 2906272554
We compute the second order correction for the cover time of the binary tree of depth n by (continuous-time) random walk, and show that with probability approaching 1 as n increases, τcov=|E|[2log2⋅n−logn 2log2+O((loglogn)8)], thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree. We consider a continuous time random walk on the rooted binary tree of depth @math with all transition rates equal to one and study its cover time, namely the time until all vertices of the tree have been visited. We prove that, normalized by @math and then centered by @math , the cover time admits a weak limit as the depth of the tree tends to infinity. The limiting distribution is identified as that of a Gumbel random variable with rate one, shifted randomly by the logarithm of the sum of the limits of the derivative martingales associated with two negatively correlated discrete Gaussian free fields on the infinite version of the tree. The existence of the limit and its overall form were conjectured in the literature. Our approach is quite different from those taken in earlier works on this subject and relies in great part on a comparison with the extremal landscape of the discrete Gaussian free field on the tree.