A Scaling Limit for the Cover Time of the Binary Tree
Aser Cortines Oren Louidor Santiago Saglietti

Privacy-Preserving Collaborative Deep Learning with Unreliable Participants
    Lingchen Zhao,
		Qian Wang, Senior Member, IEEE,
		Qin Zou, Senior Member, IEEE,

        Yan Zhang,
        and Yanjiao Chen, Member, IEEE


Qian Wang's research is supported in part by the NSFC under Grants 61822207 and U1636219, the Equipment Pre-Research Joint Fund of Ministry of Education of China (Youth Talent) under Grant 6141A02033327, the Outstanding Youth Foundation of Hubei Province under Grant 2017CFA047, and the Fundamental Research Funds for the Central Universities under Grant 2042019kf0210.
Qin Zou's research is supported in part by the NSFC under Grants 61872277 and 41571437, the  Natural Science Foundation of Hubei Province under Grant 2018CFB482.
Yanjiao Chen's research is supported by the NSFC under Grant 61702380, the Natural Science Foundation of Hubei Province under Grant 2017CFB134, the Hubei Provincial Technological Innovation Special Funding Major Projects under Grant 2017AAA125. (Corresponding author: Qin Zou)
L. Zhao and Q. Wang are with the School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China, and also with The State Key Laboratory of Cryptography, P.O. Box 5159, Beijing 100878, China. Email: {lczhaocs, qianwang}@whu.edu.cn.
Q. Zou and Y. Chen are with the School of Computer Science, Wuhan University, Wuhan 430072, Hubei, China. Email: {qzou, chenyanjiao}@whu.edu.cn.
Y. Zhang is with the Huawei Technologies Co., Ltd, Shenzhen 518129, Guangdong, China. Email: zhangyan113@huawei.com. Work done primarily at the School of Computer Science, Wuhan University, China

    

==============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



 
We consider a continuous time random walk on the rooted binary tree of depth n 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 2^n+1 n and then centered by (log 2) n - log n, 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.
 






§ INTRODUCTION AND RESULTS


Let _n be the rooted binary tree of depth n ≥ 1, of which the root we denote by 0 and its set of leaves by _n. Suppose that X_n = (X_n,t :  t ≥ 0) is a continuous time random walk (RW) on _n starting from 0 with all transition rates equal to one. Equivalently, starting from the root, upon reaching a vertex x ∈_n the process X_n first holds for an exponentially distributed time with mean 1/(x) and then jumps to one of the neighbors of x in _n, uniformly at random.
Given x ∈_n and t ≥ 0, the local time at x up to time t is defined as

    _n,t(x) := ∫_0^t 1_x(X_n,s)  s  .

The cover time of _n is the first time when all vertices in _n have been visited, namely

    ^_n := inf{t ≥ 0: min_x ∈_n_n,t(x) > 0 } .


The goal of the present work is to study the large n asymptotics of ^_n. As in many of the earlier works on this subject, it is easier to first consider the cover time measured in terms of the local time at the root. Formally, we let ^-1_n,t(x) be the generalized inverse of t ↦_n,t(x), namely

    ^-1_n,t(x) := inf{s ≥ 0 : _n,s(x) > t } .

Then, the local time at x ∈_n measured in terms of the local time at the root
is given by

    L_n,t(x) := _n,^-1_n,t(0)(x)  .

That is, L_n,t(x) is the local time at x up to the moment that the local time at the root is t.
The corresponding version of the cover time is then defined as

    T^_n := inf{t ≥ 0: min_x ∈_n L_n,t(x) > 0 } .


Our first theorem shows that √(T^_n) admits a distributional limit as n →∞ after centering by √(t_n^), where t_n^ is defined via

    √(t^_n) := √(log 2)  n - 1/2 √(log 2)log n  .

The limiting law is described in terms of the limit of the derivative martingale associated with the discrete Gaussian free field (DGFF) on the infinite rooted binary tree  with zero imposed at the root as boundary conditions. To be more explicit, let us now properly define these objects.

Suppose that each of the edges of the tree  is assigned a random value, chosen independently according to the Gaussian distribution with mean 0 and variance 1/2. Then, for each x ∈, let h(x) be the sum of the values assigned to the edges on the path going from the root of  to x. The field h = (h(x) :  x ∈) is then (a multiple of) the DGFF on . Alternatively, h(x) can be seen as recording the position of particle x in a branching random walk (BRW) process, with deterministic binary branching and centered Gaussian steps with variance 1/2.

The derivative martingale associated with h is the process (Z_n :  n ≥ 0) defined as

    Z_n := 2^-2n∑_x ∈_n(√(log 2)  n - h(x)) ^2 √(log 2)   h(x) .

It is well known <cit.> that the sequence (Z_n :  n ≥ 0) converges almost-surely to a positive and finite limit, and accordingly we set

    Z := lim_n →∞ Z_n   a.s.

We can now formulate our first theorem.


For all s ∈,

    lim_n →∞(√(T^_n) - √(t_n^)≤ s ) 
    = exp(-C_⋆ Z ^-2 √(log 2)  s)  ,

where C_⋆∈ (0,∞) and Z is as in (<ref>).


In order to deduce the weak convergence of the real cover time ^_n from the the convergence of T^C_n, we prove the following theorem which relates the two.


For all s ∈,

    lim_n →∞| (√(2^-(n+1)^_n) - √(t_n^) + ξ≤ s ) -
    ( √(T^_n) - √(t_n^)≤ s) | = 0  ,

where ξ is a centered Gaussian random variable with variance 1/2, which is independent of X_n.


Using Theorem <ref> and Theorem <ref>, deriving a scaling limit for ^_n is not a difficult task. To state the result, however, we first need to define a surrogate for Z in the description of the limiting law. To this end, we define a new centered Gaussian field = ((x) :  x ∈^1 ∪^2), where ^1, ^2 are two disjoint isomorphic copies of . The law of  is completely determined by insisting that 

    ((x^1) :  x^1 ∈^1) ((x^2) :  x^2 ∈^2) (h(x) :  x ∈) ,

with h being the DGFF from before and that

    (x^1) (x^2) = -12( 1-2^-|x^1| ∧ |x^2|) 
       :      x^1 ∈^1 ,  x^2 ∈^2  ,

where |x^1| and |x^2| denote the depths of x^1 and x^2 in ^1 and ^2, respectively.
The existence of such a field will be shown in Proposition <ref> of Section <ref>. In the meantime, we observe that 
for all n ≥ 1 and x^1 ∈^1_n, x^2 ∈^2_n, 

    (x^1) (x^2) = -12 (1-2^-n)  -12 
      as  n →∞ ,

where ^1_n and ^2_n denote the set of leaves at depth n of ^1 and ^2, respectively.

In light of (<ref>), we can define Z^1 and Z^2 to be the almost-sure limits of the derivative martingales with respect to ((x^1) :  x^1 ∈^1) and ((x^2) :  x^2 ∈^2), defined exactly as in (<ref>) and (<ref>) only with h replaced by  restricted to ^1 and ^2, respectively. We then set

    := Z^1 + Z^2  .

The weak convergence of the scaled real cover time is then given by,


For all s ∈,

    lim_n →∞(√(2^-(n+1)^_n) - √(t_n^)≤ s )
    = exp(-_⋆^-2 √(log 2)  s)  ,

where _⋆∈ (0,∞) and  is as in (<ref>) and is positive and finite almost surely. Furthermore, _⋆ and  are related to C_⋆ and Z from Theorem <ref> via,

    _⋆ = C_⋆/4
      ,     Λ Z ,

where Λ∼Log-normal(-2 log 2, 2 log 2) is assumed to be independent of .



Since |(2^-(n+1) n^-1^_n - ((log 2) n - log n)) - (2√(log 2)(√(2^-(n+1)^_n) - √(t^_n)))|
is 

    O (((√(2^-(n+1)^_n) - √(t^_n))^2 + 1 ) n^-1log^2 n )  ,

as a straightforward corollary of Theorem <ref> we get,


For all s ∈,

    lim_n →∞(^_n/2^n+1 n - ((log 2) n - log n) ≤ s )
    = exp(-_⋆^-s)  ,

where _⋆ and  are as in Theorem <ref>.


Remarks.

 1. In many other works on this subject, the mean holding time at a vertex x is assumed to be one, but the local time at x is then scaled by 1/(x). We chose instead (purely for aesthetic reasons) to define the mean holding time as 1/(x) and not to scale the local time. This makes no difference when one considers T_n^, but results in a difference by an overall multiplicative factor of 2 in the asymptotics of _n^ (that is, ^_n in the case of mean one is asymptotically twice what it is here). This is rather evident from the proof of Theorem <ref>. 

2. The asymptotics for the real cover time in the case of mean one holding times remain the same, if one then replaces the continuous time random walk with its discrete-time analog (in which case _n^ measures the number of steps taken before all vertices have been visited). This is because the fluctuations in the number of steps which X_n makes during t ≥ 0 time is of order √(t). Consequently, at times of the order of the real cover time 2^n n^2, these fluctuations are of order 2^n/2 n, which is far smaller than 2^n+1n – the order of fluctuations of ^_n, as shown by Corollary <ref>.




 §.§ Discussion and related works

The asymptotics of the cover time on the tree have been studied considerably in the past. The leading order term (log 2)2^n+1 n^2 was found by Aldous in <cit.>. The second order term -2^n+1 n log n was then derived by Ding and Zeitouni in <cit.>. (Both expressions are scaled by 2 for the sake of comparison, as the authors considered the mean one holding time case.) Tightness of the scaled cover time after centering by the median was shown by Bramson and Zeitouni <cit.>, without an explicit expression for its asymptotics. Very recently, Belius, Rosen and Zeitouni <cit.> showed that the remaining terms in the asymptotic expansion are O(1) and consequently proved tightness of the scaled cover time. 

What prevented the authors in <cit.> from obtaining the convergence in law of T_n^ was the lack of precise asymptotics for the right tail of √(T^_n) - √(t_n^). The authors do obtain the right order of the tail (<cit.>) using careful barrier estimates, but with non-matching constants for the upper and lower bounds. We remark that the approach taken in this work is quite different and, instead of using barrier estimates, relies almost entirely on comparison with the extremal landscape of the DGFF. As such, we avoid the need of deriving asymptotics for the right tail altogether and, as a side effect, essentially reproduce all the results mentioned above using different arguments (see Subsection <ref> for more details).

The limiting law in Corollary <ref> (as well as those in Theorem <ref> and Theorem <ref>) can be interpreted as the distribution of G + log, where G is a  Gumbel distributed random variable satisfying (G ≤ s) = exp(-_⋆^-s) for all s ∈, and  is as in (<ref>) and independent of G. As such, the limiting law of the cover time bears strong resemblance to the weak limit of the centered minimum/maximum of the DGFF on . Indeed, it was shown by Aïdékon <cit.> that for all s ∈,

    lim_n →∞(max_x ∈_n h(x) - m_n ≤ s )
    = exp(C_♢ Z ^-2 √(log 2) s)
     ;   
    m_n := √(log 2)  n - 3/4 √(log 2)log n  ,

where Z is precisely as in (<ref>) and C_♢∈ (0,∞). 

In view of Theorem <ref>, we see that when the cover time is measured in terms of the local time at the root, its square root admits exactly the same limiting law (up to an arbitrary shift) as that of the maximum of the DGFF, although the centering sequence in both cases differ by
√(t_n^) - m_n = (4√(log 2))^-1log n. In particular, from the known asymptotics for the right tail of the limit of the centered maximum (<cit.>), it readily follows that

    lim_n →∞(√(T^_n) - √(t_n^) > s ) ∼ C_∘ s ^-2√(log 2) s  as  s →∞ ,

for some C_∘∈ (0,∞). 
This was the missing stronger form of <cit.> mentioned above.

The overall form of the limiting law of the cover time as a randomly shifted Gumbel and its resemblance to the limiting law of the centered maximum of the DGFF were expected in the literature (see below). In fact, a randomly shifted Gumbel distribution is conjectured to be the universal limiting law of the maximum/minimum of fields with logarithmic or approximate logarithmic (e.g. hierarchical) correlations. This has been verified, for example, in the case of branching Brownian motion <cit.> and the discrete Gaussian free field in two dimensions <cit.>.

Somehow less expected, as far as we know, is the appearance of  in the definition of the random shift which governs the limiting law of the real cover time. The random variable , as defined in (<ref>), is the sum of two copies of the limit Z of the derivative martingale, defined with respect to two DGFFs on  which are coupled together such that the covariances between their values on _n all tend to -1/2 as n →∞. Alternatively,  can be viewed as the limit of a derivative-martingale-like process, defined similarly to (<ref>) only with respect to a centered Gaussian field  satisfying (<ref>) and (<ref>) (one can also take (<ref>) for a definition of ). The appearance of negative correlations in the definition of  is due to the negative dependency between T^_n and ^-1_n,t (see Subsection <ref>). 

The connection between the cover time of the tree and the maximum/minimum of the DGFF is well known. A general theory relating the two on general graphs was developed by Ding, Lee and Peres  in <cit.> and extended by Ding <cit.>. Further evidence for the connection between the extreme values of the local time field and those of the DGFF was demonstrated by Abe in <cit.>, who showed that the thinned extremal process of local times converges in law to a Cox process, driven by the limit of the derivative martingale  (in its random-measure form) of the DGFF. 

The reason why these two seemingly very different objects exhibit very similar extreme value statistics becomes apparent thanks to the second Ray-Knight Theorem (also sometimes referred to as a version of Dynkin's Isomorphism Theorem). The theorem, which in this context is due to Eisenbaum, Kaspi, Marcus and Rosen <cit.> relates the law of the local time field to the law of the DGFF on the same graph. Specializing to the tree, this relation can be expressed in terms of a coupling between L_n,t and two copies h, h' of the DGFF, under which L_n,t and h are independent of each other and the following identity holds almost-surely:

    L_n,t(x) + h^2(x) = 
    (h'(x) + √(t))^2 
       :  x ∈_n  .


To illustrate that the above relation readily yields a strong connection between the extreme values of the local time field and those of the DGFF, consider the case when √(t) is much larger than m_n - the order of extreme values of h and h' on _n. In this case, under the coupling we have  √(L_n,t(x)) - √(t)≈  
h'(x), which shows that extreme values of √(L_n,t) - √(t) on _n are approximately the same as those of the DGFF on _n. Unfortunately, in the study of the cover time √(t) is taken to be √(t_n^) + O(1) ∼ m_n and thus the use of the isomorphism is far less trivial. 

Lastly, let us mention that in a parallel development thread, considerable effort has been devoted to studying the cover time of a random walk on the two-dimensional torus or the cover time of a Brownian motion (BM) on a two-dimensional compact manifold (see, e.g. <cit.> for the definition in this case). Results here include, in chronological order, the derivation of the leading order term for RW and BM <cit.>, a bound on the second order term for RW <cit.>, a derivation of the second order term for BM <cit.>, a derivation of the second order term for RW <cit.> and most recently tightness in the case of BM <cit.>. Despite the very different natures of the underlying graphs, and as in the case of the DGFF, many of the results and techniques in the case of the tree, carry over to the two-dimensional setup, albeit with notable and difficult technical complications involved.  




 §.§ Proof outline


In this subsection we give a short overview of the proofs of Theorem <ref> and Theorem <ref>. In the case of Theorem <ref>, the argument is rather straightforward and can be easily understood from the top-level proof of the theorem in Section <ref>.



  §.§.§ Theorem <ref>

The proof of Theorem <ref> takes up the largest part of the paper. The first key idea is to split the running time of the walk into two consecutive phases: A and B. In phase A the random walk is run for time t^_n and in phase B for time t^_n+sn, where s ∈ and 

    √(t_n^ A) : = m_n = √(log 2)  n - 3/4 √(log 2)log n 
      ,     
    t_n^ := 1/2 nlog n  ,

Above m_n is as in (<ref>) and both running times are measured in terms of the local time at the root.
Observe that for fixed s as n →∞,

    √(t_n^ + t_n^ + sn) = √(t_n^) + (2√(log 2))^-1 s + o(1)  .


The motivation for this split comes from the isomorphism with the DGFF and the relation

    L_n,t(x) + h^2(x) = 
    (h'(x) + √(t))^2 
       :  x ∈_n  ,

under the coupling employed in (<ref>).
Since the min-extreme (near minima) values of the DGFF on _n are typically at a height -m_n + O(1), at time √(t)=√(t_n^) the right hand side in (<ref>) for such min-extreme leaves will be O(1). On the other hand, to get an O(1) value on the left hand side in (<ref>), we must have both L_n,t(x) = O(1) and h_n(x) = O(1). It follows that, under the isomorphism, min-extreme leaves of h' on _n correspond to low-local-time leaves (namely, leaves with O(1) local time under L_n,t), which “survived the isomorphism” because their corresponding value under h is also O(1). Since h(x) for x ∈_n has a Gaussian law with mean 0 and variance n/2,  a low-local-time leaf survives with probability of order 1/√(n). 

Now, as it turns out, at time t_n^, except for a negligible subset, with high probability most of the low-local-time leaves agglomerate in an order of √(n) clusters, each having diameter O(1) and at distance n-o(n) apart (both measured in graph distance). Moreover, the restrictions of the local time field to each of these low-local-time clusters follow jointly an asymptotic i.i.d. law. Since the law of the DGFF h restricted to such a clustered collection of leaves in _n follows a similar i.i.d. structure, the number of low-local-time clusters in which at least one leaf survives has asymptotically a Binomial distribution with order √(n) trials and success probability of order 1/√(n). 


It follows from the Poisson approximation to the Binomial distribution that the number of “surviving” clusters (namely, low-local-time clusters in which at least one leaf survives) is asymptotically Poisson with rate proportional to 1/√(n) times the total (random) number of low-local-time clusters. Since surviving clusters correspond exactly to min-extreme clusters of h' (namely, clusters of leaves whose value under h' is -m_n + O(1)), we can equate their respective laws. Thanks to earlier work on the extreme values of the DGFF, the asymptotic joint law of the min-extreme values of h' is well known. In the limit, these values have the same distribution as that of the atoms of a clustered Poisson point process with  (random) intensity given by Z ^2√(log 2)u u, where Z is as in (<ref>). In particular, the number of min-extreme clusters has a Poissonian law with (random) rate proportional to Z.

Equating the law of surviving clusters with the law of the min-extreme clusters, we find that the number of low-local-time clusters at the end of phase A has asymptotically the same law as C' √(n) Z for some C > 0 (which explicitly depends on all O(1) terms above). Using the i.i.d. nature of the clusters, the same asymptotics in law can be shown to hold (with the constant C_⋆ from Theorem <ref> replacing C) for the number of zero-local-time clusters, namely clusters with leaves which were not visited at all by time t_n^.

Turning to phase B, when the random walk leaves the root for an excursion in the direction of x ∈_n, a simple Gambler's Ruin estimate shows that the probability that x will be visited before the walk returns to the root is 1/n. It is not difficult to show that, whenever the random walk reaches x, it will also visit a cluster of diameter O(1) around it in the same excursion, with overwhelming probability. Since the number of excursions in the direction of x within time t_n^ + sn is essentially t_n^ + sn, the probability that a cluster of diameter O(1) will not be visited within such time is (1-1/n)^t_n^ + sn = ^-s/√(n). We now see that estimating the number of zero-local-time clusters after phase A which are then not entirely visited in phase B becomes a Coupon Collector Problem. 

Because the clusters are n-o(n) apart, the “not-entirely-visited” events are essentially independent for different clusters. Since asymptotically there are C_⋆√(n) Z clusters after phase A, each not entirely visited in phase B with probability ^-s/√(n), we are again in the Poisson regime of the Binomial distribution. It follows that the number of zero-local-time clusters not entirely visited after phase B is again Poisson in the limit with (random) rate C_⋆^-s Z. Observing that leaves which are not visited after both phases  are precisely those contained in such clusters, the probability that the tree _n is not entirely visited within time t_n^ + t_n^ + sn is the same as the probability that a Poisson with rate C_⋆^-s Z is equal to zero. In view of (<ref>), this is precisely the statement of Theorem <ref>.

Evidently, a crucial ingredient in the argument presented above is the sharp description of the clustering structure of the set of low-local-time leaves after phase A. One way of obtaining such a description is via truncated first moment bounds, by imposing a barrier on the local time trajectory of such leaves. This barrier method has been used, e.g. in <cit.>, to derive the tightness of the cover time. Our approach, which can be viewed as another key idea in the argument, is rather different. We instead rely almost entirely on comparison with the DGFF via (<ref>). 

More precisely, instead of just comparing their values, we compare the full trajectory of low-local-time leaves under L_n,t_n^ with the full trajectory of min-extreme leaves under h'. In a rather delicate analysis, we are then able to deduce from the known repulsion of trajectories of min-extreme leaves under h' a similar repulsion for the local time trajectories of the low-local-time leaves. More explicitly, if L_n,t^_n(x) = O(1) for x ∈_n, then we show that typically

    √(L_n,t^_n([x]_k)) - n-k/n√(t^_n) > (k ∧ (n-k))^1/2-ϵ :    k ∈ [n^1/2-ϵ', n]  ,

where [x]_k denotes the ancestor of x at depth k and ϵ, ϵ' > 0 can be chosen arbitrarily small. This sharp repulsion statement (which would have been also a necessary step had we employed the barrier method) in turn yields the needed sharp clustering description.  

We remark that not all low-local-time leaves obey the above clustering structure. Indeed, there are low-local-time leaves whose distance from other such leaves is o(n) but not O(1). Unfortunately, in order to show that they form a negligible set (which will be visited entirely in phase B with high probability, and therefore can be ignored), we were forced to rely on the usual barrier method, as we did not find a suitable comparison argument with the DGFF. Luckily, a coarse barrier is sufficient for this purpose, and consequently the application of this method is considerably simpler when compared to, say, its use in <cit.>. See the proof of the second part of Theorem <ref> and Subsection <ref> of the appendix.



  §.§.§ Theorem <ref>

Turning to the proof of Theorem <ref>, it requires a simple computation to show that the total running time R_n,t of the walk on _n when the local time at the root is t ≥ 0, has mean (2^n+1 - 1)t and variance 2^2n+3t(1+o(1)). In particular, the fluctuations of this quantity are uniformly of the same order as its mean. This implies that tightness of √(^_n/2^n+1) around √(t_n^) will follow from the tightness of  √(T^_n) around the same centering value. On the other hand, it also shows that there will be an additional randomness in the conversion between the two cover times which will not disappear in the limit. Moreover, there is no reason why (R_n,t -  R_n,t)/√( R_n,t) at t = T^_n should be independent of T^_n. In fact, it is not difficult to guess that they should be negatively correlated.

To control this additional randomness, we first reduce the problem to that of a finite order, regardless of n, by considering the tree up to level k ≤ n. To this end, we define the normalized running time by R_n,t := 2^-n R_n,t. Then, conditioning on (L_n,t(x) :  x ∈_k) and neglecting the local time at the first k-1 levels of the tree, the distribution of R_n,t is the same as that of

    2^-k∑_x ∈_k 2^-(n-k) R^(x)_n-k,L_n,t(x) ,

where (R^(x)_n-k,t :  t ≥ 0) are independent for different x-s and have the same law as (R_n-k, t :  t ≥ 0). This is a simple consequence of the spatial Markov property of L_n,t.
Furthermore, setting also S_k,t := ∑_x ∈_k L_n,t(x) and S_k,t := 2^-k S_k,t, under the conditioning above, the quantity in (<ref>) has mean 2S_k,t(1+o(1)) and variance O(2^-kS_k,t). Therefore 2S_k,t is a good approximation for R_n,t with high probability as k →∞.

This implies that, instead of running X_n until (real) time 2^n+1 s, we can consider the walk up to the stopping time τ_k, 2^k+1s, where τ_k, s := inf{t ≥ 0 :  2 S_k,t > s}. Using a version of the central limit theorem for a sum with a random number of terms, it can be shown that the joint law of (L_n,τ_k,2^k+1 s(x) :  x ∈_k) is then, asymptotically as s →∞, Gaussian with means s and covariances 

    (2s (|x∧ y| - 1) + o(1))_x,y ∈_k ,

with the o(1) term tending to 0 as k →∞. 

On the other hand, in view of the isomorphism relation (<ref>), for fixed k and s →∞, with high probability we have that

    L_n,s(x) = s + 2√(s) h'(x) + (h')^2(x) - h^2(x) =  s + 2√(s)(h'(x) + o(1))  
       :  x ∈_k  .

This shows that (L_n,s(x) :  x ∈_k) is, asymptotically as s →∞, also  Gaussian with means s, but with covariances given by 

    (4s  h'(x) h'(y))_x,y ∈_k = (2s |x ∧ y|)_x,y ∈_k .

Comparing (<ref>) with (<ref>), we see that on _k the local time field up to real time 2^n+1 s has asymptotically (as s →∞ followed by k →∞) the same law as that of the local time field when the local time at the root is s, up to a negative -2s term added to all covariances. This negative term is an artifact of the negative correlation mentioned above.

To compensate for this negative covariance term, we consider instead of the stopping time τ_k, 2^k+1s the stopping time ν_k,s := τ_k, 
2^k+1θ_s where θ_s := s + 2√(s)ξ and ξ∼(0,1/2) drawn independently of the walk. This essentially amounts to running the random walk until real time 2^n+1 (s + 2√(s)ξ), or equivalently until the square root of the running time scaled by 2^-(n+1) is √(s) + ξ. It can then be easily shown that the law of (L_n,ν_k,s(x) :  x ∈_k) is asymptotically the same as that of (L_n,s(x) :  x ∈_k). Thanks to the spatial Markov property again, the last two assertions now imply the asymptotic equivalence in law of √(T_n^) and √(2^-(n+1)^_n) + ξ around the centering value √(t_n^), which is precisely the statement in Theorem <ref>.




 §.§ Organization of the paper

Section <ref> includes the top-level proofs of all of our main theorems. These proofs capture the outline of the arguments leading to each of the main theorems and as such rely on key statements which are proved later in the manuscript. All the necessary preliminaries are stated in Section <ref> with all lengthy but standard proofs deferred to Appendix <ref>. Section <ref> includes upper bounds which are direct consequences of the isomorphism. They are used in Section <ref> to obtain the sharp clustering description as discussed in Subsection <ref>. Section <ref> deals with the i.i.d. nature of low-local-time clusters, as well as the i.i.d. nature of the DGFF on clustered sets. Section <ref> includes the proof of the main theorem for phase A. Section <ref> includes the proof of the main theorem for phase B. Both are building blocks in the proof of Theorem <ref>. Section <ref> and Section <ref> include the main results needed for the proofs of Theorem <ref> and Theorem <ref>, respectively. Finally, the appendix includes the proofs which were left out from Section <ref>.




§ TOP-LEVEL PROOFS


In this section we provide top-level proofs for Theorems <ref>, <ref> and <ref>. 
These proofs build on key statements whose proofs, in turn, constitute the main effort in this work. To obtain a top-down exposition, we shall present these key statements here and first show how to use them in order to prove the main results of the paper. Then, in the remainder of the paper, we will provide the necessary proofs of these key results.



 §.§ General notation

We start by introducing some further notation which will be used throughout the sequel. First and foremost, we will often consider the tree _n in place of _n. The former is defined exactly as _n, except that the root 0 has only one child, so that its degree is now one instead of two. Observe that the size of the leaf set _n of _n is 2^n-1 instead of 2^n (as it is for _n). Furthermore, we will think of _n for all n ≥ 1 as embedded in one single infinite rooted tree  where all vertices have degree 3, except for the root which has degree one. The slight advantage of working with this unconventional tree is that for any x ∈, each of the subtrees ^r(x), ^l(x) – consisting of x, one of its children and all of their descendants – is isomorphic to . This will be somewhat handy in the sequel. We note that the union (x) := ^l(x) ∪^r(x) forms an infinite regular rooted binary tree which is isomorphic to .

Given x ∈, we write |x| for the depth or generation of x, namely the (graph) distance between x and 0. For 0 ≤ k ≤ |x|, we write [x]_k for the ancestor of x at depth k. The deepest common ancestor of x,y ∈ will be denoted by x ∧ y. These last two definitions extend to an arbitrary collection of vertices ⊂ via ⋀ for the deepest common ancestor of all x ∈ and []_k for the set {[x]_k :  x ∈}. All of the above notation extends to the regular binary tree  with the obvious necessary changes. Furthermore, we will also use this notation for subtrees of  or . For instance, if x ∈ then _k(x) is the set of vertices in (x) at distance k from x, or equivalently the set of leaves in _k(x). 

When the underlying tree is _n, the process X_n = {X_n,t :  t ≥ 0} still denotes a continuous time random walk with all transition rates equal to one, and the local times _n,t(x) and L_n,t(x) are defined exactly as in the case of _n. The precise underlying graph will always be made explicit, so that there should be no confusion. For both graphs and any 1 ≤ k ≤ n, n', since the law of (L_n,t(x) :  |x| ≤ k  ,  t ≥ 0) is the same as that of (L_n',t(x) :  |x| ≤ k  ,  t ≥ 0), we shall often omit n from the notation and just write L_t(x).

Finally, for some general conventions, if f is a function on some domain D then we denote by f(D) the collection of all of its values on D. We denote the cardinality of a set D by |D|, not to be confused with the depth |x| of the vertex x.
As usual, constants whose value is immaterial and may change from one use to another are denoted by C, C', C”, etc. These are always positive and finite and are independent of any parameter, unless stated explicitly otherwise.



 §.§ Proof of Theorem <ref>

In order to prove Theorem <ref>, we first consider the tree _n in place of _n and, as explained in Subsection <ref>, split the running time of the walk on _n into two consecutive phases: A and B. In phase A the random walk is run for time t^_n and in phase B for time t^_n+sn, where s ∈ and 

    √(t_n^ A) := √(log 2)  n - 3/4 √(log 2)log n 
      ,     
    t_n^ := 1/2 nlog n  .

Both running times are measured in terms of the local time at the root. As before, we observe that for fixed s as n →∞,

    √(t_n^ + t_n^ + sn) = √(t_n^) + (2√(log 2))^-1 s + o(1)  .


We will show that after phase A, aside from a negligible subset of size o(√(n)), the collection of non-visited leaves agglomerate in clusters whose diameter (in graph distance) is o(n^1/2) (in fact, as the proof shows, most of these clusters are essentially of diameter O(1)). Moreover, scaled by 1/√(n), the number of such clusters converge weakly to a constant multiple of Z̅, defined as Z in (<ref>) only with respect to the tree , in place of . To handle phase B, we will then show that for such a clustered collection of leaves, the number of clusters not entirely visited by the random walk after t_n^+s n time is asymptotically Poisson with rate proportional to ^-s/√(n) times the original number of clusters in the set. This will show that, after phase B, the number of clusters of non-visited leaves is asymptotically Poisson with rate CZ̅^-s, from which the convergence in law of the cover time T_n^ will follow immediately.

To make this argument precise, for n ≥ 1 and t ≥ 0, we start by thinking of L_t = L_t(_n) as a (random) function on _n, and for u ≥ 0 define the sub-level set of L_t at height u as

    _n,t(u) := { x ∈_n :  L_t(x) ≤ u } .

For η∈ (0,1/2), whose precise value is immaterial for the argument, we also henceforth set

    r_n = r_n^η:= ⌊ n^1/2-η⌋ .

Then, for any y ∈ [_n,t(u)]_r_n, we shall call the set _n,t(u) ∩(y) an r_n-cluster of _n,t(u). 

For each k ∈ [r_n, n], the subset of leaves in _n,t(u) belonging to k-rooted r_n-clusters is defined as

    ^k_n,t(u) := { x ∈_n,t(u) : |⋀( _n,t(u) ∩([x]_r_n))| = k } .

This is the set of all leaves that belong to some r_n-cluster of _n,t(u) of which the deepest common ancestor is found at depth k. We will call z ∈ [_n,t^k(u)]_k the root of the cluster _n,t^k(u) ∩(z). Notice that any k-rooted r_n-cluster of ^k_n,t(u) has diameter 2(n-k) (in graph distance). Let us also set, for K ⊆ [r_n,n],

    ^K_n,t(u) := ⋃_k ∈ K^k_n,t(u)   ,

and observe that this is always a union of disjoint sets and is equal to _n,t(u) when K=[r_n, n].

In analog to Z from (<ref>), we define Z̅ as the almost-sure limit of the derivative martingale associated with the DGFF on :

    Z̅ := lim_n →∞Z̅_n  a.s.  ,     Z̅_n := 2^-2n+1∑_x ∈_n(√(log 2)  n - h(x)) ^2 √(log 2)   h_n(x) ,

where (h(x) :  x ∈) is defined exactly as in (<ref>) above, except that now the underlying tree is  instead of .
Since (2Z_n : n ≥ 0) has the same law as the sum of two independent copies of (Z̅_n : n ≥ 0), the existence, positivity and finiteness almost-surely of Z̅ follows from the validity of this claim for Z and, moreover, 

    2Z Z̅^l + Z̅^r  ,

where Z̅^l, Z̅^r are two independent copies of Z̅.

We can now state the key theorem for phase A, which includes both a sharp description of the clustered structure of non-visited leaves and asymptotics for the number of their r_n-clusters.


There exists C_A ∈ (0,∞) such that as n →∞,

    1√(n)|[_n, t_n^(0)]_r_n| ⟹ 
    C_A Z̅ ,

where Z̅ is as in (<ref>). In addition, the following holds in probability as n →∞:

    1√(n)|_n, t_n^^[r_n, n-r_n](0)|  0  .



Turning to phase B, for any 0 ≤ r ≤ R ≤ n we will say that a set of leaves _n ⊂_n is (r, R)-clustered if for all x, y ∈, we have either |x ∧ y| ≥ R or |x ∧ y| < r. The next theorem shows that the number of r_n-clusters in an (r_n, n-r_n)-clustered subset _n of _n which are not entirely visited by the walk after time t_n^+sn is asymptotically Poisson with rate C ^-s |_n|/√(n). Moreover, any subset _n of _n which is of size o(√(n)) will be entirely visited with high probability.



There exists C_B ∈ (0,∞) such that for all s ∈, λ≥ 0, 

    lim_n →∞sup__n| exp(-λ|[_n,t_n^+sn(0) ∩_n]_r_n| ) 
    - exp( -C_B ^-s√(n)|[_n]_r_n| (1-^-λ) ) | = 0  ,

where the supremum is over all (r_n, n-r_n)-clustered subsets _n of _n. 
Moreover, for all n ≥ 1, s ∈, any set _n ⊆_n (not necessarily clustered) and v > 0,

    ( |_n,t_n^+sn(0) ∩_n| > C_B v ^-s√(n)|_n| ) ≤ v^-1 .



Combining Theorem <ref> and Theorem <ref>, the proof of Theorem <ref> is not difficult.


Run the random walk for time t_n^ first. Since _n,t^_n(0) is the disjoint union of _n,t^_n^[r_n, n-r_n)(0) and _n,t^_n^[n-r_n, n](0), both parts of Theorem <ref> together yield 

    1√(n)|[_n,t_n^^[n-r_n, n](0)]_r_n| ⟹ C_A Z̅   as  n →∞ ,

where Z̅ is as in (<ref>). Now run the random walk for additional t_n^ + sn time and denote the set of unvisited leaves during this time by ^_n,t_n^+sn(0). Since _n,t_n^^[n-r_n, n](0) is (r_n, n-r_n)-clustered by definition, we can apply the first part of Theorem <ref> to conclude that for all λ≥ 0,

    lim_n →∞exp(-λ| [^_n,t_n^ +sn(0)
    ∩_n,t_n^^[n-r_n, n](0)]_r_n| ) = 
    exp( -C_A C_B ^-sZ̅(1-^-λ) )  .

Above we first condition on _n,t_n^^[n-r_n, n](0) and then take expectation, using the uniformity of the limit in the statement of Theorem <ref>.

Writing,

    _n, t_n^+t_n^+sn(0)     = _n, t_n^(0) ∩^_n, t_n^ + sn(0) 
        = (_n,t_n^^[n-r_n, n](0) ∩^_n,t_n^ +sn(0) ) ∪(_n,t_n^^[r_n, n-r_n)(0) ∩^_n,t_n^ +sn(0) ) ,

the probability that the second set in the union is not empty is bounded above for any δ > 0 by

    (|_n,t_n^^[r_n, n-r_n)(0)| > δ√(n))
    +
    ( |_n,t_n^+sn^(0) ∩_n,t_n^^[r_n, n-r_n)(0)| > 
    C_B v(δ) ^-s√(n)|_n,t_n^^[r_n, n-r_n)(0)| )  ,
 where v(δ) := C_B^-1^s δ^-1 /2.
Thanks to the second parts of Theorem <ref> and Theorem <ref>, both probabilities above tend to 0 when n →∞ followed by δ→ 0. This shows that 

    |[_n, t_n^+t_n^+sn(0)]_r_n| - 
    |[^_n,t_n^ +sn(0) ∩_n,t_n^^[n-r_n, n](0)]_r_n|  0  ,

as n →∞ in probability. Combined with (<ref>), this gives

    |[_n, t_n^+t_n^+sn(0)]_r_n|  Poisson(C_A C_B ^-sZ̅)  ,

where the right hand side of (<ref>) is the law of a random variable defined, conditionally on Z̅, to have a Poissonian law with rate C_A C_B ^-sZ̅.

Finally, observe that for 0 ∈_n the local time fields L_t(_n^l(0)) and L_t(_n^r(0)) are independent, and each has the same law as L_t(_n). In view of (<ref>), this implies that with s' = (2 √(log 2))^-1 s as n →∞,

    (√(T_n^) - √(t_n^)≤ s' + o(1))
    = (|[_n, t_n^+t_n^+sn(0)]_r_n| = 0 )^2
    exp(-C_A C_B ^-s(Z̅^l + Z̅^r))  ,

where Z̅^l and Z̅^r are independent copies of Z̅ from (<ref>). In view of (<ref>), this gives the desired statement with C_⋆ := 2C_A C_B ∈ (0,∞).




 §.§ Proof of Theorem <ref>

Next, we present the top-level proof of Theorem <ref>. In order to compare the cover time measured in terms of the local time at the root and the real cover time, we show that for any 1 ≤ k ≤ n and s ≥ 0 one can define a random time ν_k,s which is measurable with respect to the walk X_n and an additional independent random variable ξ∼(0,1/2) such that two statements hold. First, the laws of the local time field on _k at time s and at time ν_k,s, both measured in terms of the local time at the root, are close to each other. Second, when the local time at the root is ν_k,s, the total running time of the walk is with high probability close to an explicit expression involving s and ξ. This is formalized in the following theorem.
 
 
Given n ≥ 1 and a random variable ξ∼𝒩(0,1/2) independent of the walk X_n, for each 1 ≤ k ≤ n and any s ≥ 0 there exists a σ( X_n , ξ)-measurable random time ν_k,s such that for any ϵ > 0,
	
    lim_k →∞lim sup_s →∞sup_n ≥√(s)ℙ(|√(2^-(n+1)𝐋^-1_n, ν_k,s(0)) + ξ - √(s)| > ϵ) = 0.

Moreover, there exists a coupling (L'_ν_k,s(_k), L”_s(_k)) of the local time fields L_ν_k,s(_k) and L_s(_k) such that for any ϵ > 0,
	
    lim_k →∞lim sup_s →∞ℙ(√(L'_ν_k,s)(_k) - √(L”_s)( _k) _∞ > ϵ) = 0 .
 


Using Theorem <ref> we can now prove Theorem <ref>.

Fix s_0 ∈ and for n ≥ 1, ϵ∈, let s and s^ϵ be defined via the relations,

    √(s) := √(t_n^) + s_0
      ,     √(s^ϵ) = √(s) + ϵ = √(t_n^) + s_0 + ϵ ,

whenever such s and s^ϵ exist. For u ∈, let us also set

    p_n(u) := (√(T^_n)≤ u )
     ,   p_n(u) := p_n (√(t_n^) + u) = (√(T^_n) - √(t_n^)≤ u )
     ,   p_∞(u) := lim_n →∞p_n(u)  ,

where the last limit exists in light of Theorem <ref>. Clearly all of the quantities in the last display increase with u. Moreover, thanks to the explicit form of p_∞, as given by Theorem <ref>, and a straightforward application of the dominated convergence theorem, the function u ↦p_∞(u) is continuous.

Now, we first claim that for any ϵ > 0 and k ∈,

    lim_n →∞(√(L_s^±ϵ)(_k) - (√(L_s)(_k) ±ϵ)_∞ > ϵ/2 ) = 0  .
 
Indeed, by the mean value theorem for each x ∈_k, we have

    √(L_s^ϵ(x)) - √(L_s(x))≥L_s^ϵ(x) - L_s(x)/2 √(L_s^ϵ(x)) = ϵ√(s)+ϵ^2/2/√(s) + ϵ×L_s^ϵ(x) - L_s(x)/2ϵ√(s)+ϵ^2/√(L_s^ϵ(x)/s^ϵ) .

Since L_s^ϵ(x) - L_s(x)  L_2ϵ√(s)+ϵ^2(x), using that L_t(x)/t tends to 1 in probability, as t →∞ for any fixed x ∈, as implied by (<ref>), the right hand side above tends to ϵ in probability, as n →∞. Bounding √(L_s^ϵ(x)) - √(L_s(x)) from above by (L_s^ϵ(x) - L_s(x))/(2 √(L_s(x))) and proceeding in a similar way then gives the opposite inequality, and the case s^-ϵ is handled in exactly the same way.

Next, we make use of the coupling from the second part of Theorem <ref>, the Markov property of the local time field and monotonicity of p_n to write,

    (T_n^≤ν_k,s)     = ∏_x ∈_k p_n-k(√(L_ν_k,s(x))) 
       ≤∏_x ∈_k p_n-k(√(L_s(x)) + ϵ/2) + 
    (√(L'_ν_k,s)(_k) - √(L”_s)( _k) _∞ > ϵ/2 ) 
       ≤∏_x ∈_k p_n-k(√(L_s^ϵ(x)))
    + 
    (√(L'_ν_k,s)(_k) - √(L”_s)( _k) _∞ > ϵ/2 ) 
                + (√(L_s^ϵ)(_k) - (√(L_s)(_k) +ϵ)_∞ > ϵ/2 ) .

Thanks to the second part of Theorem <ref> and (<ref>), the last two probabilities tend to 0 when n →∞ followed by k →∞. At the same time, by the Markov property again, the last expectation is equal to (T_n^≤ s^ϵ) = p_n(s_0 + ϵ), which tends to p_∞(s_0) when n →∞ followed by ϵ→ 0, in light of Theorem <ref> and the continuity of p_∞. 
Consequently, if we take n →∞ followed by k →∞ and finally ϵ→ 0 in (<ref>), we obtain

    lim sup_k →∞lim sup_n →∞(T_n^≤ν_k,s) ≤p_∞(s_0)  .


Repeating the derivation in (<ref>) with √(L_s(x)) - ϵ/2 and √(L_s^-ϵ(x)) 
in place of √(L_s(x)) + ϵ/2 and √(L_s^ϵ(x)) respectively, and with the inequalities reversed, gives

    lim inf_k →∞lim inf_n →∞(T_n^≤ν_k,s) ≥p_∞(s_0)  .

This together with (<ref>) then shows that 

    lim_k →∞lim sup_n →∞| (T_n^≤ν_k,s) - p_∞(s_0) | = 0  .


Now, let ξ be the random variable from the statement of Theorem <ref> and use the union bound to write,

    (√(2^-(n+1)^_n) + ξ≤√(s))
    ≤(√(2^-(n+1)^-1_n, ν_k,s^ϵ(0)) + ξ < √(s))
    + (T^_n ≤ν_k,s^ϵ)

and

    (T^_n ≤ν_k,s^-ϵ) 
    ≤(√(2^-(n+1)^-1_n, ν_k,s^-ϵ(0)) + ξ > √(s))
    +
    (√(2^-(n+1)^_n) + ξ≤√(s))   .

Letting n →∞ followed by k →∞, it then follows from (<ref>) and (<ref>) (with s_0 ±ϵ in place of s_0), that

    p_∞(s_0-ϵ)  ≤ _n →∞(√(2^-(n+1)^_n) + ξ≤√(s)) 
     ≤ _n →∞(√(2^-(n+1)^_n) + ξ≤√(s)) 
     ≤ p_∞(s_0 + ϵ) .

Since this is true for all ϵ, the continuity of p_∞ again completes the proof.





 §.§ Proof of Theorem <ref>

In order to prove Theorem <ref>, we first need to address the existence of the field  and derive a distributional relation between  and Z. Both are stated in the following proposition, whose rather elementary proof is given in Section <ref>.



There exists a centered Gaussian random field = ((x) :  x ∈^1 ∪^2) satisfying (<ref>) and (<ref>). Moreover, if  is defined as in (<ref>) and Z is defined as in (<ref>) then

    Λ Z  ,

for Λ∼Log-normal(-2 log 2, 2 log 2) taken to be independent of . In particular,  is almost-surely finite and positive.


Let us now prove Theorem <ref>.

Set τ_n := √(2^-(n+1)^_n) - √(t_n^) and let ζ be the weak limit as n →∞ of √(T^_n) - √(t_n^), the existence of which is guaranteed by Theorem <ref>. It follows from Theorem <ref> that τ_n + ξ converges weakly to ζ as n →∞, where ξ∼(0,1/2) and independent of τ_n. Denoting by τ_n, ξ and ζ the characteristic functions of τ_n, ξ and ζ respectively, the latter implies that 
τ_n ξ tends pointwise to ζ under the same limit. Since ξ is never zero, we can divide by it and assert the convergence of τ_n to ζ/ξ. Since ζ and ξ are continuous at 0, so must be ζ/ξ. But then, by standard theory of weak convergence τ_n must converge weakly to some random variable τ whose characteristic function τ is ζ/ξ. Multiplying by ξ we see that τ must satisfy 

    τ + ξζ ,

where the random variables on the left hand side are taken to be independent. We remark that τ is uniquely defined via the above relation (since this claim holds for its characteristic function). 

In view of the right hand side in the statement of Theorem <ref>, we can further write

    ζ1/2 √(log 2)log Z + G  ,

where G is chosen according to the Gumbel distribution with rate 2√(log 2) (and a proper shift determined by C_⋆) and is independent of Z. Now, let  be as in (<ref>), whose existence, relation to Z via (<ref>) and almost-sure finiteness and positivity are all verified in Proposition <ref>. Taking the logarithm in (<ref>) and dividing by 2 √(log 2), we see that  must satisfy

    1/2 √(log 2)log + ξ - √(log 2)1/2 √(log 2)log Z  ,

for ξ with the same law as before and independent of . 
This in turn implies that if we replace τ in (<ref>) by G + (2 √(log 2))^-1log - √(log 2) with both random variables in this sum taken independent, then the equality in law there will still hold. But since τ is uniquely defined by (<ref>), we must have τ G + (2 √(log 2))^-1log - √(log 2), which in explicit form is exactly (<ref>). 





§ PRELIMINARIES


In this section we collect some results and tools which will be used in the sequel. Most statements here are taken from existing literature, while a few require proofs which are either straightforward or standard in the subject. Therefore, in order not to divert attention from the main argument, proofs which are not elementary will be relegated to Appendix <ref>. Throughout the entire section the underlying graph is assumed to be the tree .



 §.§ The DGFF and its relation to the local time field
 


  §.§.§ The Isomorphism Theorem

Let us recall that (h(x) :  x ∈), as defined below (<ref>), is the DGFF on  with zero imposed at the root as boundary conditions (for more information on the DGFF, see for example <cit.>). We shall often consider the restriction of h to _n which we denote by h_n = (h_n(x) :  x ∈_n). 

As mentioned in the introduction, a crucial tool which we use frequently in the proof is (a version of) the Second Ray-Knight Theorem (or Dynkin's Isomorphism Theorem) due to <cit.>. For convenience of use, we present this theorem as an almost-sure equivalence under a coupling of the processes involved.


For all t ≥ 0 and n ≥ 0, there exists a coupling of L_n,t = (L_n,t(x) :  x ∈_n) and two copies of the DGFF, h_n = (h_n(x) :  x ∈_n)
and h'_n = (h'_n(x) :  x ∈_n), such that L_n,t and h_n are independent of each other and almost-surely,

    L_n,t(x) + h^2_n(x) = 
    (h'_n(x) + √(t))^2 
       :  x ∈_n  .


Henceforth, whenever we use (<ref>) we implicitly assume that the process L_n,t, h_n and h'_n are all defined in our probability space and that they are coupled as in Theorem <ref>. Furthermore, the coupling above will mostly be used with t = t_n^ from (<ref>), in which case we write the right hand side of (<ref>) as h^2_n(x), where

    h_n(x) := h'_n(x) + m_n 
       ,      m_n = √(t_n^) .


For u ≥ 0, the sub-level set of h^2_n as a function on _n at height u is defined as

    _n(u) := { x ∈_n : h^2_n(x) ≤ u } .

Observe that under the coupling in Theorem <ref>, we always have

    _n(u) ⊆_n, t^_n(u)   ,

since the second term on the left hand side of (<ref>) is always positive. 
Accordingly, we shall sometimes say that a leaf x ∈_n, t^_n(u) survives the isomorphism to mean that it is also in _n(u).



  §.§.§ Extreme value theory for the DGFF on the tree

The main reason for considering the local time field at time √(t) = √(t_n^) = m_n is that the min-extreme (near minimum) values of h_n are typically at height -m_n + O(1). This means that sub-level sets near 0 of h_n coincide with the min-extreme level sets of h_n (both as functions on _n). Thanks to the isomorphism and the observation in (<ref>), the structure of leaves with low local time at t=t_n^ can then be inferred from the structure of min-extreme values of h_n. Since the theory of extreme values for the DGFF on the tree is fully developed, this offers a way of studying _n,t^_n and in turn to analyze phase A. 

In this subsection, we shall therefore survey the results we need from the theory of extreme values for the DGFF on . In the literature, such theory is mostly focused on the BRW. This would have posed no problems if one had been interested in the extreme values of the DGFF on , as the latter is a particular instance of the BRW, where branching is deterministically binary and steps are centered Gaussians. Since we have chosen to use the unconventional tree , a bit of work is required to convert off-the-shelf statements to our setup. 

This can be done by modifying the proofs of these results to handle an initial generation with branching by one. Alternatively, one can simply observe (as we have done before) that a BRW on  has the same law as two independent copies of a BRW on , or that a BRW on  has the same law as a BRW on  with the positions of all particles in all generations shifted by a common centered Gaussian. All of these approaches are straightforward and have been used substantially in the past. We shall therefore just cite the needed results from the literature, converted to the case when the underlying tree is  and leave the task of verifying the validity of the conversion to the reader.

We start with the following result showing exponential tightness of the minimum/maximum around ± m_n respectively. This follows, e.g., from Proposition 1.3 in <cit.>, where it shown also that, centered by ± m_n, the minimum/maximum of h_n converges in law.


There exists C, C' > 0, such that for all u ≥ 0,

    lim sup_n →∞(max_x ∈_n |h_n(x)| > m_n  + u ) ≤ C ^-C' u .



Other (min-)extreme values of h_n can be recorded via the so-called structured min-extremal process of h_n. To this end, for 1 ≤ r ≤ n and y ∈_n-r, we set:

    h^*_n,r(y) := min_x ∈_r(y)h_n(x) 
       ;
        _n,r(y) := ∑_x ∈_r(y)δ_(h_n(x) - h^*_n,r(y)) .

The random variable h^*_n,r(y) is the minimum of h_n on the set of leaves in _n whose common ancestor at generation n-r is y. The point process _n,r(y) records the heights of all such leaves, relative to the minimum. _n,r(y) is sometimes referred to as the cluster around the minimum in _r(y). The structured min-extremal process of h_n is then the aggregation of all such pairs of minima and clusters in the form of (yet another) point process:

    χ_n,r := ∑_y ∈_n-rδ_(h^*_n,r(y) ,  _n,r(y)) .


For the topological setup, we view the cluster _n,r(y) as taking values in the space _0(_+) of finitely bounded measures on [0,∞), and the process χ_n,r as taking values in the space of finitely bounded measures on ×_0(_+). Both spaces are equipped with the Vague Metric. The next proposition shows that χ_n,r converges weakly to an explicit point process. It can be deduced from Theorem 1.1 and Corollary 1.2 in <cit.>.


As n →∞ followed by r →∞,

    χ_n,r⟹ PPP(C_♢Z̅^2 √(log 2)u u ⊗ν(ω) )  ,

where C_♢ a positive and finite constant, Z̅ is as in (<ref>) and ν is a distribution on _0(_+) supported on infinite point measures with an atom at 0.

The notation PPP(μ), as in the right hand side of (<ref>), stands for a Cox process with random intensity measure μ, namely a point process defined conditionally on μ as a Poisson point process with μ as its intensity measure. 

We shall not use Theorem <ref> directly, but rather two propositions which follow from it and concern the set _n(u) from (<ref>). The first concerns the tightness and asymptotic non-triviality of the size of _n(u). This follows rather immediately from the above theorem together with the almost-sure finiteness and positivity of Z̅, and can also be found essentially in <cit.>.


For all u > 0, the sequence (|_n(u)| :  n ≥ 1) is tight and, moreover,

    lim_u →∞lim sup_n →∞(_n(u) = ∅) = 0  .



The second proposition requires a short proof which is rather standard.  It is therefore relegated to Appendix <ref>. 


For all u > 0, there exists C_u > 0, such that as n →∞ followed by r →∞,

    |[_n(u)]_n-r| ⟹ Poisson(C_u Z̅)  ,

where Z̅ is as in (<ref>). 

As in Theorem <ref>, the right hand side stands for the distribution of a random variable which is defined, conditionally on Z̅, to have a Poissonian law with intensity C_u Z̅.

An important fact that we shall use is that, for leaves x ∈_n having an O(1) value under h_n, their trajectory under h_n, namely the sequence ((k, h_n([x]_k)) :  k=0, …, n ), is typically much higher than the linear interpolation of its endpoints. This behavior, which goes by the name of entropic repulsion, is well known in the theory of extreme values of genealogically/logarithmically correlated fields, and is a key factor in both its phenomenology and the methods used to study it.

To formulate a quantitative statement, we first introduce the following notation, which will be used frequently in the sequel:

    ∧_n(k) := k ∧ (n-k)  .

For η∈ (0,1/2) we also set

    _k = _k^η := [k^1/2 - η ,   k^1/2 + η]  ,

and for u ≥ 0, define

    _n^k(u) = _n^k, η(u) := {x ∈_n(u) : h_n([x]_k) - √(log 2) (n-k) ∉_∧_n(k)^η] } ,

which is extended to all K ⊆ [0,n] via

    _n^K(u) = _n^K, η(u) := ⋃_k ∈ K_n^k,η(u)  .


This entropic repulsion of trajectories of min-extreme leaves of the field h_n is then given by the following proposition. We recall that r_n was defined in (<ref>).


Let η∈ (0,1/2). For all u ≥ 0,

    lim_r →∞lim sup_n →∞(_n^[r_n, n-r], η(u) ≠∅) = 0  .


Statements such as these appear in various places in the literature (c.f. Theorems 2.2 and 2.3 in <cit.> in the case of the related model of branching Brownian motion). However, they are usually either implicitly contained in a proof of a different statement or slightly weaker than what we need here. We therefore provide a proof for this proposition in the appendix. We remark that the exponent 1/2-η (with arbitrarily small η) in the lower boundary of _k is much stronger than what we actually require. The proofs of all of the main theorems go through without change for any η < 1/4 and with mild changes also for C log∧_n(k) for sufficiently large C > 0 in place of (∧_n(k))^1/2-η.



 §.§ Local time preliminaries

Next we collect some results concerning the local time of a continuous time simple random walk. 



  §.§.§ Some simple estimates for the local time on the tree

The following is an easy bound on the local time whenever √(t)≫ n^2, which follows easily from the isomorphism theorem.

 Given η > 0, there exist  constants C,C' > 0 such that, for all n ≥ 0 and t ≥ 0 satisfying √(t)≥ n^2+η, we have

    lim sup_n →∞(max_x ∈_n|√(L_t(x)) - √(t)| > m_n + u ) ≤ C^-C' u .



In light of the isomorphism, for t as in the statement of the lemma, on the event that |h_n(x)| ∨ |h'_n(x)| ≤ m_n + u-1 we have, by Taylor expansion, that

    √(L_t(x)) = √((h'_n(x) + √(t))^2 - h^2_n(x))
    = h'_n(x) + √(t) + O ( h^2_n(x)/√(t))

which is in [√(t) - m_n - u, √(t) + m_n + u] for all n large enough. Hence, the event in (<ref>) requires that there exists x ∈_n such that |h_n(x)| ∨ |h'_n(x)| > m_n + u - 1. But the probability of this is exponentially decaying in u thanks to Proposition <ref>.
 


Next, we give a (coarse) upper bound on the size of |_n,t(u)|.


For any u ≥ 0, t ≥ 0 and n ≥ 1,

    |_n,t(u)| ≤^-t/n + 2tu/n^2 + n log 2 + 1 .

In particular, for each u ≥ 0 there exists C_u > 0 such that if √(t) = √(log 2)  n + s for some s ∈ and n ≥ 4u,

    |_n,t(u)| ≤ C_u ^-√(log 2)  s

and also

    (_n,t(u) ≠∅) ≤ C_u ^-√(log 2)  s .



If t ≤ n then the bound (<ref>) trivially holds, so henceforth we will assume otherwise. 
For any x ∈_n, the number of visits to x until time ^-1_n,t(0) is Poisson with parameter t/n. Once at x, the total time spent there before returning to the root is exponentially distributed with rate 1/n. Since the accumulated times at different excursions from the root are independent, if we let X, Y be independent Poissons with rates t/n and u/n respectively, we have

    (x ∈_n,t(u)) = (X ≤ Y)

Since t/n ≥ 1, by conditioning on Y we can upper bound this probability by

    ( ∑_x=0^Y (X = x) )
    ≤^-t/n (Y+1) (tn)^Y
    = ^-t/n (1+tu/n^2) ^tu/n^2 - u/n ,

which is at most ^-t/n + 2tu/n^2. Then (<ref>) follows by summation. 

Plugging √(t) = √(log 2)n + s, the right hand side of (<ref>) is equal to

    exp(-2 (1 - 2un) √(log 2)  s + (2 log 2) u - (1 - 2un) s^2n  + 1 )

which is bounded by the right hand side of (<ref>) for C_u := ^(2 log 2) u + 1, 
whenever n ≥ 4u. Finally, (<ref>) follows by Markov's inequality.




  §.§.§ Local time on a branch of the tree

The local time of a one-dimensional continuous time random walk forms a zero-dimensional squared Bessel process (see, for example Lemma 7.7 in <cit.>), as shown in the next lemma.


Let t ≥ 0, n ≥ 1 and x ∈_n. Then

    ((L_n,t([x]_k) :  k=0, …,n) ∈·)
    = 
    ((Y_k :  k=0, …,n) ∈·)  ,

where Y = (Y_s :  s ∈ [0,n]) is one half times a zero-dimensional squared Bessel process starting from 2t.


The next two lemmas are useful in studying the process Y. They can be found, e.g., in <cit.>.


Let Y be the process from Lemma <ref> for some t ≥ 0 and n ≥ 1. Then for every measurable function φ: ^n+1→, we have

    (φ(Y_0, …, Y_n)  ;   Y_n ≠ 0 )
    = ( φ(B^2_0, …, B^2_n) √(t^1/2/B_n)exp(-316∫_0^n B^-2_s  s )  ; min_s ∈ [0,n] B_s > 0 )  ,

where (B_s :  s ∈ [0,n]) is a Brownian motion starting from √(t) with variance 1/2.



For each s ≥ 0, the law Q_s of Y_s is given by  

    Q_s(A)=exp(-t/s) 1_A(0) + ∫_A f_s(y)dy ,
 for any Borel set A ⊆_+, where f_s(y) satisfies

    f_s(y) ≤ C s^-1√(t/y)exp(-(√(t)-√(y))^2/s)  ,
 
for all y ≥ 0 and some absolute constant C > 0.




  §.§.§ Soft entropic repulsion of local time trajectories

As the last preliminary result, we need a statement concerning the entropic repulsion of the local time trajectory of non-visited leaves. To this end, for η' > 0 and K ⊂ [1,n], define

    𝒪^K_n = 𝒪^K, η'_n :={ x ∈_n,t^_n(0) : ∀ k ∈ K  ,√(L_t^_n([x]_k))≥√(log 2)(n-k) + n^η'} .
 
Then,
 
There exists η' > 0 such that for any δ > 0,

    lim_n →∞( |_n, t^_n(0) ∖𝒪^[r_n,n-r_n], η'_n| > δ√(n)) = 0 .


Similar repulsion statements, usually in a stronger form, exist in the literature (c.f. <cit.>), albeit not for the local time at t=t^_n. Our proof follows the usual “barrier” approach and introduces no new ideas. In fact, since we only need to exhibit repulsion far from the root and the leaves, the proof is much simpler compared to that of similar results in other works. It can be found in the appendix. 




§ UPPER BOUNDS AS CONSEQUENCES OF THE ISOMORPHISM


In this section we provide upper bounds on the number of r_n-clusters of _n,t^_n(u) for u ≥ 0, with and without additional constraints (for the definition of r_n and  r_n-clusters, see (<ref>)). These will be used both in Section <ref> to study the fine clustering structure of the set _n,t^_n(u) and in Section <ref>, where we prove the key theorem for phase A.
To economize on notation, henceforth we shall write _n(u) as a short for _n,t^_n(u) and note that whenever we need to consider the set _n,t(u) at a time other than t=t^_n, we will use the original explicit notation. 



 §.§ The number of r_n-clusters

From the isomorphism theorem we get the following upper bound for the number of r_n-clusters:


For each u ≥ 0, we have

    lim_δ→ 0lim sup_n →∞(|[_n(u)]_r_n| > δ^-1√(n)) = 0 .




Fix u ≥ 0 and for any n ≥ 1, define the random set ^*_n(u) from _n(u) by keeping one and only one vertex among those sharing the same ancestor at generation r_n according to some predefined but arbitrary rule. Observe that by definition [^*_n(u)]_r_n = [_n(u)]_r_n. 

Now, employing the coupling from (<ref>), the event

    {|_n(u+1)| > δ^-1}

is implied by the intersection:

    {|[_n(u)]_r_n| > δ^-1√(n)}∩{max_x ∈_r_n |h_n(x)| < r_n log r_n }∩{|{x ∈^*_n(u) :  |h_n(x)| ≤ 1 }| > δ^-1} .


By the Markov property for h_n, conditional on h_n(_r_n) the law of h_n(x) for x ∈_n is Gaussian with mean h_n([x]_r_n) and variance (n-r_n)/2. Moreover, under this conditioning h_n(x) and h_n(y) are independent whenever x,y ∈_n and [x]_r_n≠ [y]_r_n. Using this together with the independence of L_t^_n and h_n, conditional on the first two events in (<ref>), the law of 
|{x ∈^*_n(u) :  |h_n(x)| ≤ 1 }| stochastically dominates a Binomial distribution with ⌈δ^-1√(n)⌉ trials and success probability given by

    2/√(π(n-r_n))exp(-(r_n log r_n+1)^2n-r_n) = 2/√(π n)(1+o(1))  .


It therefore follows by Chebyshev's inequality that the probability of the last event in (<ref>) conditional on the first two tends to 1 as n →∞ followed by δ→ 0. Thanks to Proposition <ref>, the probability of the middle event also tends to 1 under the same limit.
Using the product rule and the independence between L_t^_n and h_n, it follows that for all n large enough, we have

    (|[_n(u)]_r_n| > δ^-1√(n))
    ≤ 2 (|_n(u+1)| > δ^-1)  .

But then, the tightness of the min-extreme level sets, as given by Proposition <ref>, completes the proof.




 §.§ The number of clusters without proper entropic repulsion

The same line of argument can also yield an upper bound on the number of r_n-clusters with leaves whose local time trajectory is not properly repelled. For η∈ (0,1/2) recalling the definition of _k^η from (<ref>), for t ≥ 0 and k ∈ [r_n, n] we define

    ^k_n,t(u) = ^k,η_n,t(u) := { x ∈_n,t(u) :  √(L_t([x]_k))∉√(log 2)(n-k) + _∧_n(k)^η} .

As usual, we also set for K ⊂ [r_n, n],

    _n,t^K(u) = _n,t^K,η(u) := ⋃_k ∈ K_n,t^k,η(u)  ,

and omit t from the subscript if it is equal to t_n^.
We then have:


Let η∈ (0,1/2). For all u ≥ 0 and δ > 0, 

    lim_r →∞lim sup_n →∞(|[_n^[r_n, n-r], η(u)]_r_n| > δ√(n))= 0  .




We fix u and η as in the conditions of the lemma, and omit the dependence on u from the notation henceforth. By definition, for each x ∈_n^[r_n, n-r], there exists a largest k(x) ∈ [r_n,n-r] such that

    √(L_t_n^([x]_k(x)))∉√(log 2)(n-k(x)) + _∧_n(k(x))^η .

Now, for all such x if |h_n([x]_k(x))| ≤∧_n(k(x))^1/2+η' for η' ∈ (0,1/2) then by Taylor expansion,

    h_n([x]_k(x)) = √(L_t_n^([x]_k(x)) + h_n([x]_k(x))^2)
    = √(L_t_n^([x]_k(x))) + O (∧_n(k(x))^2η')  ,

whenever √(L_t_n^([x]_k(x))) > 12 √(log 2)(n-k(x)). Therefore as soon as
2η' < 1/2-η and k(x) is large enough we will have

    h_n([x]_k(x)) ∉√(log 2)(n-k(x)) + _∧_n(k(x))^η” ,

for any η”∈ (0, η). The same conclusion also holds when √(L_t_n^([x]_k(x)))≤12 √(log 2)(n-k(x)), since then h_n([x]_k(x)) ≤34 √(log 2)(n-k(x)). 

We now argue as in the proof of Lemma <ref>. Let _n^* be a (random) subset of _n^[r_n, n-r] obtained by choosing one vertex among all ones in _n^[r_n, n-r] sharing the same ancestor in generation r_n, so that [_n^*]_r_n = [_n^[r_n, n-r]]_r_n. Then for any v ≥ 0 and δ > 0, on the event

    {|[_n^[r_n, n-r],η]_r_n| > δ√(n)}∩{max_x ∈_r_n |h_n(x)| < r_n log r_n }
    ∩{|{x ∈_n^* : |h_n(x)| ≤√(v) ,  |h_n([x]_k(x))| ≤∧_n(k(x))^1/2+η'}| > δ v^1/4} ,

we must have 

    {| _n^[r_n, n-r], η”(u+v) | > δ v^1/4} .


To estimate the probability of the third event in (<ref>), we observe that for any x ∈_n, w ∈ (-r_n log r_n,  r_n log r_n) and k ∈ [r_n, n] we can write

    (|h_n(x)| ≤√(v) ,  |h_n([x]_k)| ≤∧_n(k(x))^1/2+η' |  h_n([x]_r_n) = w ) = 
    ∫_-√(v)^√(v)(h_n(x) ∈ v' |  h_n([x]_r_n) = w )
    (|h_n([x]_k)| ≤∧_n(k)^1/2+η' |  h_n([x]_r_n) = w ,  h_n(x) = v' )   .

Now, conditional on h_n([x]_r_n) = w, the sequence (h_n([x]_l :  l=r_n,…, n) is random walk with Gaussian steps having mean zero and variance 1/2, starting from w. Therefore, the first term in the integrand can be bounded from below by 

    1/√(π (n-r_n))exp(-(√(v) + r_n log r_n)^2n-r_n) 
    ≥C/√(n) ,

for some C > 0 and all n large enough, depending on v. 

At the same time, since under the second conditional probability in the integral, h_n([x]_k) is a Gaussian with mean μ and variance σ^2 satisfying:

    |μ| = | w(n-k) + v'(k-r_n)/n-r_n| ≤√(v) + r_n log r_n 1_{n-k > √(n)} + 1 
    ,   σ^2 = (k-r_n)(n-k)/2(n-r_n)≤12∧_n(k)  .

It follows by the Gaussian tail formula, that the second term in the integrand is at least

    1 - 2exp(-( ∧_n(k)^1/2+η' - (√(v) + r_n log r_n 1_{n-k > √(n)} + 1))^2/∧_n(k))
    > C' >  0 ,

whenever ∧_n(k) is large enough, depending on v. Together this shows that the probability on the left hand side of (<ref>) is at least 
C”√(v) /√(n) for some C” > 0 whenever ∧_n(k) is large enough (depending on v).


Using this in (<ref>) we see that for any v ≥ 0, whenever r is large enough, when   we condition on the first two events in (<ref>), the probability of the third is larger or equal than the probability that a Binomial with ⌈δ√(n)⌉ trials each with probability C”√(v) / √(n) is at least δ v^1/4. It follows by standard arguments that this probability tends to 1 when n →∞ followed by v →∞. Since the middle event in (<ref>) has probability tending to 1 with n as well, using the independence in the coupling and the product rule this shows that for any δ > 0, we may choose v then r and finally n (all large enough) such that 

    (|[_n^[r_n, n-r], η]_r_n| > δ√(n))
    ≤ 2 
    ( |_n^[r_n, n-r], η”(u+v) | > δ v^1/4)  .

It remains to observe that when v is such that δ√(v)≥ 1, the right hand side goes to 0 when n →∞ followed by r →∞, in light of Proposition <ref>.


We shall also need a stronger upper bound on the number of r_n-clusters of leaves whose local time trajectory is unusually low. To this end, for any η' ∈ (0,1/2) and for k ∈ [r_n,n] we define the set of vertices in _k whose local time is unusually low.

    ^k_n
    = ^k,η'_n := { y ∈_k :  √(L_t_n^(y))≤√(log 2) (n-k) - ∧_n(k)^1/2-η'} .

Then,


Let 0 < η' < η” < 1/2. Then,

    lim_r →∞lim sup_n →∞( ∃ k ∈ [r_n, n-r] : | [^k, η'_n]_r_n| 
    > ^-∧_n(k)^1/2-η”√(n)) = 0  .



The argument is similar to that in the proof of Lemma <ref>. We fix η' and η” as in the statement of the lemma and in the remaining of the proof omit the dependence on these parameters from the notation. Let k ∈ [r_n, n-r] and set ^k*_n to be the random set obtained from _n^k by choosing (in a fixed but arbitrary manner) one member from each subset of vertices of _n^k sharing the same ancestor at depth r_n. By definition we have |[_n^k]_r_n| = |^k*_n|. Now, for all y ∈_n^k* if
|h_n(y)| ≤ 1 then by Taylor expansion,

    h_n(y) = √(L_t_n^(y) + h_n(y)^2)≤√(log 2) (n-k) - ∧_n(k)^1/2-η' + O ((n-k)^-1)  ,

which is at most m_n - m_k - 12∧_n(k)^1/2-η' for all k in the range considered whenever r is large enough. Consequently for such y we have h_k(y) ≤ -12 ∧_n(k)^1/2-η'.

Therefore, the intersection of

    {| _n^k*| 
    > ^-∧_n(k)^1/2-η”√(n)}∩{∃ y ∈_n^k* :  |h_n(y)| ≤ 1 } ,

implies that 

    {min_y ∈_kh_k(y) ≤ -12 ∧_n(k)^1/2-η'} .

Now if ^-∧_n(k)^1/2-η”√(n) < 1, then conditional on the first event in (<ref>), the probability of the second is at least the probability that one y ∈_n^k* satisfies |h_n(y)| ≤ 1. Thanks to the independence between L_t and h_n and since h_n is Gaussian with mean zero and variance k/2, this conditional probability is at least C/√(n)≥ C ^-∧_n(k)^1/2-η”. This gives 

    ( | _n^k*| 
    > ^-∧_n(k)^1/2-η”√(n))
    ≤ C ^∧_n(k)^1/2-η”( min_y ∈_kh_k(y) ≤ -12 ∧_n(k)^1/2-η')  .


On the other hand, if ^-∧_n(k)^1/2-η”√(n)≥ 1, then for n large enough, we must have k ≥ n/2. In this case, we replace the intersection in (<ref>) with

    {| _n^k*| 
    > ^-∧_n(k)^1/2-η”√(n)}∩{max_x ∈_r_n |h_n(x)| < r_n log r_n }∩{∃ y ∈_n^k* :  |h_n(y)| ≤ 1 } .

Then, conditional on second event in (<ref>) for any y ∈_k, the probability that |h_n(y)|≤ 1 is at least

    2/√(π (k-r_n) )exp(-(r_n log r_n+1)^2k-r_n) ≥C'/√(n) ,

It follows that conditional on the first two events in (<ref>), the probability of the third is larger or equal than the probability of at least one success in a sequence of 
⌈√(n)^-∧_n(k)^1/2-η”⌉ independent trials each succeeding with probability
at least C/√(n). Since the product of the last two quantities tends to 0 with n, standard arguments imply that this probability is at least C' ^-∧_n(k)^1/2-η”. Since the probability of the middle term in (<ref>) tends to 1 with n, as shown by Proposition <ref>, by the product rule, we again have (<ref>).

Since η' < η”, invoking Proposition <ref> again, we get

    ( | _n^k*| 
    > ^-∧_n(k)^1/2-η”√(n))
    ≤ C ^-14 ∧_n(k)^1/2-η'

Summing the left hand side over k ∈ [r_n, ⌈ n/2 ⌉] gives a quantity which tends to 0 with n, while the same sum over k ∈ [⌈ n/2 ⌉, n-r] is at most C ^-C' r^1/2-η'. Since |[_n^k]_r_n| = |^k*_n|, combining the sums and using the union bound, we recover (<ref>).




§ SHARP CLUSTERING OF LEAVES WITH LOW LOCAL TIME


We continue to the use the notional convention from the previous section, whereby we write _n(u) as a short for _n,t^_n(u). This is further extended to the set _n,t^_n(u) from (<ref>), as well as to other subsets of _n,t^_n(u) which appear in the sequel. A key ingredient in the proof of Theorem <ref> is a sharp description of the clustering structure of _n(u). Recall that _n^[r_n, n-r](u) is the set of leaves belonging to r_n-clusters whose root is at depth at most n-r. The following theorem shows that with high probability, for large r such leaves do not survive the isomorphism and moreover that the number of clusters containing such leaves is o(1) √(n) with the o(1) term tending to 0 in probability as r →∞.



For any u ≥ 0,

    lim_r →∞lim sup_n →∞( _n^[r_n, n-r](u) ∩_n(u)  ≠∅) = 0  .

Moreover, for all such u ≥ 0 and δ > 0,

    lim_r →∞lim sup_n →∞( | [_n^[r_n, n-r](u)]_r_n| > δ√(n)) = 0  .


In order to prove Theorem <ref> we cover the set _n^[r_n, n-r](u) by three subsets and show that each satisfies (<ref>) for a different reason. The first subset includes leaves whose ancestor at depth k has a large local time. To this end, let η∈ (0,1/2) and for any r_n ≤ k ≤ n and u ≥ 0, define 

    ^k_n(u) = ^k, η_n(u):= { x ∈_n^k(u) :  √(L_t_n^([x]_k)) > √(log 2) (n-k) + ∧_n(k)^1/2-η} .

For x ∈_n^k(u) the r_n-cluster containing x, namely _n(u) ∩([x]_r_n), will be called a k-up-repelled r_n-cluster.

The second subset is that of leaves belonging to clusters which are large:

    ^k_n(u) =
    ^k, η_n(u) := { x ∈_n^k(u) : | _n^k(u) ∩([x]_r_n) | > ^∧_n(k)^1/2-η} ,

where η, k and u are as in the previous definition. We will call the clusters of such leaves k-big. 
The third subset will simply be _n^k(u) ∖(^k_n(u)∪^k_n(u)).

Setting as usual for K ⊆ [r_n,n],

    ^K_n(u) = ^K,η_n(u) := ⋃_k ∈ K^k_n(u) 
       ,    ^K_n(u) = ^K, η_n(u) := ⋃_k ∈ K^k_n(u)  ,

we have the following two propositions:


Let η∈ (0,1/2). For any u ≥ 0,

    lim_r →∞lim sup_n →∞( ( _n^[r_n, n-r], η(u) ∪_n^[r_n, n-r], η(u)) ∩_n(u)  ≠∅) = 0  .




Let η∈ (0,1/2). For any u ≥ 0,

    lim_r →∞lim sup_n →∞(( _n^[r_n, n-r](u) ∖(_n^[r_n, n-r], η(u) ∪_n^[r_n, n-r], η(u)) ) ∩_n(u)  ≠∅) = 0  .



These clearly imply Theorem <ref>. Indeed,

 (<ref>) follows immediately from Propositions <ref> and <ref> by an application of the union bound. 
As for the proof of (<ref>), we will only sketch it as it is very similar to the upper bound arguments already found in Section <ref>. 

Fix u ≥ 0 and, for any r ≥ 1 and n ≥ r, let _n^*(u) be the random subset of _n^[r_n,n-r](u) obtained by picking exactly one vertex from each and every group of vertices in _n^[r_n,n-r](u) which share the same ancestor in generation r_n, according to some predefined but arbitrary rule, so that [^*_n(u)]_r_n = [_n^[r_n,n-r](u)]_r_n. 

By the isomorphism (<ref>), we see that, for any δ>0, the event

    {_n^[r_n, n-r](u+1) ∩_n(u+1)  ≠∅}

is implied by the intersection

    {|[_n^[r_n,n-r](u)]_r_n| > δ√(n)}∩{max_x ∈_r_n |h_n(x)| < r_n log r_n }∩{|{x ∈^*_n(u) :  |h_n(x)| ≤ 1 }| > δ} .


As in the proof of Lemma <ref>, the probability of the third event in (<ref>) given the first two is at least the probability of a Binomial random variable with ⌈δ√(n)⌉ trials and success probability 2/√(π n)(1+o(1)) being larger than δ, and is therefore bounded from below by some constant C > 0 for all n large enough. Furthermore, again as in Lemma <ref>, the probability of the second event in (<ref>) given the first tends to 1 under the same limit. It then follows from the product rule that for all r ≥ 1 and n large enough,

    (|[_n^[r_n,n-r](u)]_r_n| > δ√(n)) ≤2/C(_n^[r_n, n-r](u+1) ∩_n(u+1)  ≠∅)  ,

so that (<ref>) now follows from (<ref>).



In the remainder of this section we prove the above propositions.



 §.§ Proof of Proposition <ref>

In order to prove Proposition <ref> we shall show that


Let 0 < η < η' < 1/2. Then for all u ≥ 0,

    lim_r →∞lim sup_n →∞( ∃ k ∈ [r_n, n-r] : | [^k, η_n(u)]_k | 
    > ^-∧_n(k)^1/2-η'√(n)) = 0  .


and


Let 0 < η < η' < 1/2. Then for all u ≥ 0,

    lim_r →∞lim sup_n →∞( ∃ k ∈ [r_n, n-r] : | [^k, η_n(u)]_k | 
    > ^-∧_n(k)^1/2-η'√(n)) = 0  .



Let us first see why this proves Proposition <ref>.

We fix u and take r large enough. Writing _n^k, ^k_n and ^k_n as shorts for
_n^k, η(u), ^k, η_n(u) and ^k_n(u), for any r_n ≤ k ≤ n-r, by the union bound we have,

    ( (_n^k ∪_n^k) ∩_n ≠∅ |  L_t_n^(_n) ) 
    ≤∑_y ∈ [_n^k ∪_n^k]_k(∃ x ∈_n-k(y) :   
    |h_n(x)| ≤√(u))  .


The probability in the sum can be bounded from above by

    (|h_n(y)| ≤ (n-k)^2 ) +
    (∃ x ∈_n-k :  |h_n-k(x)| ≥ (n-k)^2-√(u)) 
    ≤ C ((n-k)^2√(k) + ^-C' (n-k)^2) ≤ C”(n-k)^2√(k) ,

where we have used the fact that h_n(y) is a centered Gaussian with variance k/2 for the first term and Proposition <ref> for the second.

Plugging this in (<ref>) we get for such k,

    ( (_n^k ∪_n^k) ∩_n ≠∅ |  L_t_n^(_n) )  ≤ C”( |[_n^k]_k| + |[_n^k]_k| ) (n-k)^2√(k) .


Therefore, whenever the events in Lemmas <ref> and <ref> do not occur, by the union bound the probability that there exists k ∈ [r_n, n-r] such that (_n^k ∪_n^k) ∩_n ≠∅ is at most

    C”∑_k=r_n^n-r (n-k)^2 √(n/k)^-∧_n(k)^1/2-η'≤ C”∑_k=r_n^⌈ n/2 ⌉^-12 k^1/2-η' 
    + C”∑_k=⌈ n/2 ⌉ +1^n-r (n-k)^2 ^-(n-k)^1/2-η' ,

which goes to 0 when n →∞ followed by r →∞. Using the union bound together with Lemmas <ref> and <ref> then completes the proof.





  §.§.§ Up-Repelled Clusters


We now turn to the proof of Lemma <ref>.


We fix u, η and η' as in the statement of the lemma and henceforth omit the dependence on these quantities from the notation. Letting k ∈ [r_n, n, in analog to (<ref>) we first define

    ^k_n := { x ∈_n :  √(L_t_n^([x]_k)) > √(log 2)(n-k) + ∧_n(k)^1/2-η} .

Since _n^k = _n^k ∩_n^k, if y ∈ [_n^k]_k we must have both
_n ∩^l(y) ≠∅ and _n ∩^r(y) ≠∅. We can then use the Markov property to write:

    (|[_n^k]_k|  |  [_n]_k  , 
    L_t_n^(_k) ) 
        = ∑_y ( y ∈ [_n^k]_k  |  L_t^_n(y) )/(y ∈ [_n]_k  |  L_t^_n(y) )
        = ∑_y
    (_n ∩^l(y) ≠∅ and _n ∩^r(y) ≠∅ |  L_t_n^(y) )/(_n ∩^l(y) ≠∅ or _n ∩^r(y) ≠∅ |  L_t_n^(y) )

where the sums are over the set [_n^k ∩_n^[k, n]]_k. Observe that this set is measurable with respect to the random variables under the conditioning on the left hand side. 

Abbreviating t(y) ≡ L_t_n^(y) and setting for any n ≥ 1 and t ≥ 0,

    p_n,t := (_n,t≠∅)  ,

the ratio in the sum is equal to 

    (p_n-k, t(y))^2/2p_n-k, t(y) - (p_n-k, t(y))^2≤ p_n-k, t(y) ,

whenever ∧_n(k) is large enough.
By definition, for any y in the sum √(t(y))≥√(log 2) (n-k) + ∧_n(k)^1/2-η and hence by Lemma <ref> and monotonicity of L_t in t,

    p_n-k, t(y)≤ C ^-C' ∧_n(k)^1/2-η .


Using the above bounds and since |[_n^k ∩_n^[k,n]]_k|
≤|[_n]_r_n|, the conditional expectation in (<ref>) can be bounded by
C^-C'∧_n(k)^1/2-η|[_n]_r_n|. Applying Markov's inequality and then taking expectation, for any δ>0 we then have

    (|[_n^k]_k| > δ^-∧_n(k)^1/2-η'|[_n]_r_n| ) 
    ≤ C δ^-1^-12 C'∧_n(k)^1/2-η ,

where we use that η' > η. 
The sum of the right hand side over k ∈ [r_n, ⌈ n/2 ⌉] gives a quantity which tends to 0 with n, while the same sum over k ∈ [⌈ n/2 ⌉, n-r] is at most C δ^-1^-C' r^1/2-η.  Altogether, by the union bound we therefore get for all δ > 0,

    lim_r →∞lim sup_n →∞( ∃ k ∈ [r_n, n-r] : | [^k_n(u)]_k | 
    > δ^-∧_n(k)^1/2-η'|[_n]_r_n| ) = 0  .

It remains to use Lemma <ref> and the union bound one more time to complete the proof.




  §.§.§ Big Clusters

To prove that the number of k-big clusters decay with ∧_n(k), we first show that the root of most of these clusters must have an unusually low local time. Recalling the definition of _n^k,η' from (<ref>), we then have


Let 0 < η < η' < 1/2. For all u ≥ 0,

    lim_r →∞lim sup_n →∞( ∃ k ∈ [r_n, n-r] : | [^k,η_n(u)]_k ∖^k,η'_n | 
    	> ^-∧_n(k)^1/2-η'√(n)) = 0  .




We fix u, η and η' as in the statement of the lemma and henceforth omit the dependence on these parameters from the notation. Proceeding as in the proof of Lemma <ref>, for k ∈ [r_n, n], we write

    (|[^k_n]_k ∖^k_n |  |  
    [_n]_k  ,   L_t_n^(_k))  
    = ∑_y ( y ∈ [_n^k]_k  |  L_t^_n(y) )/(y ∈ [_n]_k  |  L_t^_n(y) )
    
    = ∑_y
    (_n ∩^l(y) ≠∅ ,  _n ∩^r(y)  ≠∅ ,  | _n ∩(y) | > ^∧_n(k)^1/2-η |  L_t_n^(y) )/(_n ∩^l(y)  ≠∅ or _n ∩^r(y)  ≠∅ |   L_t_n^(y) ) ,

where the sums run over y ∈[^[k, n]_n]_k ∖_n^k. 

Abbreviating t(y) ≡ L_t_n^(y), using p_n,t from (<ref>) and setting for 1 ≤ k ≤ n and t ≥ 0,

    q_n,t,v := (|_n,t| > v ) 
       ,     
    v(n,k) := 12 ^∧_n(k)^1/2-η ,

the ratio in (<ref>) is at most

    2 p_n-k,  t(y)  q_n-k, t(y), v(n,k)/2p_n-k, t(y) - (p_n-k, t(y))^2≤ 2 q_n-k, t(y), v(n,k) ,


Since for y in the sum in (<ref>) we have t(y) > √(log 2) (n-k)  - ∧_n(k)^1/2-η', it follows from Lemma <ref>, monotonicity of the local time in t and Markov's inequality, that 

    q_n-k, t(y), v(n,k)≤ C ^-12 ∧_n(k)^1/2 - η

whenever ∧_n(k) is large enough. Plugging this back in (<ref>) and using Markov's inequality again, for any δ > 0 we have

    (|[^k_n]_k ∖^k_n| ≥δ^-∧_n(k)^1/2 - η'|[^[k,n]_n]_k ∖^k_n |
     |  [_n]_k  ,  L_t_n^(_k))
    ≤ C δ^-1^-14 ∧_n(k)^1/2 - η ,

as long as ∧_n(k) is large enough. Since |[^[k,n]_n]_k ∖^k_n | ≤ |[_n]_r_n|, taking expectation and summing from k=r_n to k=n-r, we get

    ( ∃ k ∈ [r_n, n-r] : | [^k_n]_k ∖^k_n  | 
    	> δ^-∧_n(k)^1/2 - η'|[_n]_r_n| ) ≤ 
    	C δ^-1^-C' r^1/2 - η + o(1)  ,

where the o(1) term tends to 0 with n. Together with Lemma <ref> and the union bound, this shows (<ref>).


The proof of Lemma <ref> is now straightforward.

Let u ≥ 0 and 0 < η < η”' < 1/2. Choose any η', η”∈ (η, η”') and write

    |[_n^k, η(u)]_k|  = 
    |[_n^k,η(u)]_k ∖_n^k,η'| +
    |[_n^k,η(u)]_k ∩_n^k,η'| 
    ≤|[_n^k,η(u)]_k ∖_n^k,η'|
    + |[_n^k,η']_r_n| .

Then for all k and n large enough, the event

    {|[_n^k,  η(u)]_k| > ^-∧_n(k)^1/2-η”'√(n)}

is included in

    {|[_n^k,η(u)]_k ∖_n^k,η'| 
    > ^-∧_n(k)^1/2-η'√(n)}∪{|[_n^k,η']_r_n| > ^-∧_n(k)^1/2-η”√(n)}

Now using Lemma <ref> for the first event, Lemma <ref> for the second and the union bound, we obtain (<ref>) with η”' in place of η'.





 §.§ Proof of Proposition <ref>



Let η∈ (0,1/2) and choose η' and η” such that 0 < η' < η” < η. We let also u ≥ 0 and as usual omit the dependence on this parameter from the notation. 
Thanks to Proposition <ref> and the union bound, it suffices to show

    lim_r →∞lim sup_n →∞(( _n^[r_n, n-r]∖(_n^[r_n, n-r], η∪_n^[r_n, n-r], η)) ∩(_n ∖_n^[r_n, n-r], η')  ≠∅) = 0  .

For all k ∈ [r_n, n], we first claim that if y ∈[(^k_n ∖_n^k, η∩ (_n ∖_n^k,η')]_k then we must have |h_n(y)| ≥∧_n(k)^3/4-η”/2. Otherwise, since
y ∈ [^k_n ∖_n^k,η]_k, we have √(L_t_n^(y))≤√(log 2) (n-k) + ∧_n(k)^1/2-η and therefore by Taylor expansion, since η” < η, 

    √(L_t_n^(y) + h^2_n(y))≤√(log 2)(n-k) +  O (∧_n(k)^1/2-η”)  ,

which is a contradiction to y ∈ [_n ∖_n^k, η']_k whenever ∧_n(k) is large enough, since η' < η”.

Therefore, conditional on L_t_n^(_n), the probability in (<ref>) is at most

    ∑_k=r_n^n-r ∑_y ∈ [_n^k ∖_n^k]_k ∑_x ∈_n ∩(y)(|h_n([x]_k)| ≥∧_n(k)^3/4 - η”/2 ,  
    |h_n(x)| ≤√(u))  .

As in (<ref>), conditional on h_n(x), the law of h_n([x]_k) is that of a Gaussian with mean h_n(x) k/n and variance k(n-k)/(2n) ≤∧_n(k)/2. Therefore, the probability in the last display is at most 

    C √(u)/√(n)exp(- 12 ∧_n(k)^1/2 - η”)

whenever ∧_n(k) is large enough.  
At the same time the number of summands in the inner sum is at most ^∧_n(k)^1/2-η since y ∈ [_n^k ∖_n^k,η]_k. Since η' < η and using that 
|[_n^k]_k| ≤ |[_n]_r_n|, it follows that the last sum is at most

    C √(u)/√(n)|[_n]_r_n| 
    ∑_k=r_n^n-r^-14 ∧_n(k)^1/2-η”≤ C √(u)/√(n)|[_n]_r_n| ( ^-18 r^1/2 - η” + o(1) )  ,

as long as r is large enough and with o(1) term tending to 0 with n. 

Consequently, on {|[_n]_r_n| ≤δ^-1√(n)} for δ > 0 the entire sum in (<ref>) tends to 0 as n →∞ followed by r →∞.  Since Lemma <ref> implies that (|[_n]_r_n| > δ^-1√(n)) can be made arbitrarily small by choosing δ small enough and taking n large, the result follows from the union bound.




§ THE IID NATURE OF CLUSTERS


In this section we study the i.i.d. structure of the law of the local time field restricted to clusters containing leaves with O(1) local time, as well as the i.i.d. nature of the law of the DGFF restricted to such clustered sets.



 §.§ Local time clusters


Our first task is to show that clusters containing leaves with low local time, follow an i.i.d. law, which is, most importantly, independent of n. To this end, we will show that if x ∈_n-r is a common ancestor of all leaves in an r_n-cluster of _n, then the law of its local time is insensitive to the local time of its ancestor [x]_k whenever k ≪ n-r. For a precise formulation, we define for η∈ (0,1/2), t ≥ 0, K ⊆ [0, n] and u ≥ 0, the set

    _n,t^K(u) = _n,t^K,η(u) := { x ∈_n,t(u) :  ∀ k ∈ K , √(L_t([x]_k))∈√(log 2)(n-k) + _n-k^η} ,

where _n-k^η is as in (<ref>).
(Notice the slight difference between _n,t^K,η(u) and _n,t(u) ∖_n,t^K,η(u), where the latter was defined in (<ref>).)



Now, given η∈ (0,1/2), t ≥ 0, k ∈ [0, n] and x ∈_n, define the probability measure _n^k(t  ; ·) on  via,

    _n^k(t  ; ·) := (L_t([x]_k) ∈· |  
    	x ∈_n, t^[0, k],η(u)   ,  [_n, t(u)]_k+1 = [x]_k+1)  .

We remark that, although the above quantity depends on u and η, we do not express this in the notation of _n^k(t  ; ·) to avoid clutter. Observe that by definition _n^k(t ; ·) is supported on { v ≥ 0 : √(v)∈√(log 2)(n-k) + _n-k^η}.

We then have,


If η > 0 is chosen small enough, then for all u ≥ 0, any n ≥ 1 and k ∈ [r_n, n], there exists a probability measure μ_n^k on _+ (which depends on u and η), such that for all r ≥ 1,

    lim_n →∞sup_√(t)∈√(log 2)n + _nsup_φ_∞≤ 1|∫φ(v) _n^n-r(t  ;  v )  - ∫φ(v) μ_n^n-r( v) | = 0  .
 
 

Fix u ≥ 0 and r ≥ 1. As usual we omit the dependency on u for brevity. The statement of the lemma will follow if we show that

    lim_n →∞sup_t,t'sup_φ_∞≤ 1|∫φ(v) _n^n-r(t  ;  v )  - ∫φ(v) _n^n-r(t'  ;  v ) | = 0  ,

with the outer supremum taken over all t,t' such that √(t), √(t')∈√(log 2)n + _n. Indeed, we may then set μ_n^k( v) := _n^k(t'  ;  v ) for √(t') = √(log 2)n + n^1/2 and claim (<ref>).

The first integral in (<ref>) is

    ( φ(L_t([x]_n-r))  ; 
    	x ∈_n, t^[0, n-r]  ,  [_n, t]_n-r+1 = [x]_n-r+1)/(x ∈_n, t^[0, n-r]  ,  [_n, t]_n-r+1 = [x]_n-r+1) .

Abbreviating n' ≡ n-n^3/4 and setting

    p_n(t ;  w) :=  (L_t([x]_n') ∈ w  ,  x ∈_n,t^[0,n'] , _n,t∖([x]_n'+1) = ∅)  ,

we now condition on L_t (∖([x]_n'+1) ) and use the Markov property to write (<ref>) as 

    ∫( φ(L_w([x]_n^3/4-r))  ;  x ∈_n^3/4, w^[0, n^3/4-r] ,  [_n^3/4, w]_n^3/4-r+1 = [x]_n^3/4 -r+1) p_n(t  ;  w)/∫( x ∈_n^3/4, w^[0,n^3/4-r] , [_n^3/4, w]_n^3/4-r+1 = [x]_n^3/4 -r+1) p_n(t  ;  w) ,

where both integrals are over w such that √(w)∈√(log 2)  n^3/4 + _n^3/4.
It will therefore be sufficient to show that p_n(t ;  w) depends on t via a multiplicative factor.

To this end, we further write p_n(t;  w) as

    (L_t([x]_n') ∈ w  ,  x ∈_n,t^[0,n']) 
    (_n,t∖([x]_n'+1) = ∅ |  
    L_t([x]_n') = w  ,  x ∈_n,t^[0,n'])  .

We first claim that the conditional probability above tends to 1 as n →∞, uniformly in √(t)∈√(log 2) n + _n. This is because under the conditioning we have √(L_t([x]_k)) > √(log 2) (n-k) + (n-k)^1/2-η for all k=1, …, n' and consequently, the probability in question is at least 1 minus  

    ∑_k=1^n'(_n-k, (√(log 2)(n-k) + (n-k)^1/2-η)^2≠∅)
    ≤∑_k=1^n' C ^-C' (n-k)^1/2-η≤^-n^1/4 .

Above we have used Lemma <ref> to bound the terms in the first sum.

Turning to the first term in (<ref>), by Lemma <ref> and Lemma <ref> it can be written as (B_n'^2 ∈ w , B_n'>0  | B_0 = √(t)) times

    (√(t)/√(w))^1/2( 
    exp(-316∫_0^n' B^-2_s  s )  ;      
    B_k ∈√(log 2)(n-k) + _n-k ,∀ k ∈ [1, n']  ,
    
        B_s > 0  , ∀ s ∈ [0,n'] 
     |  B_0 = √(t) ,  B_n' = √(w))  ,

where (B_s :  s ∈ [0,n']) is a Brownian motion with variance 1/2 starting from √(t) at time 0 (which we write formally as conditioning).

Since √(t)∧√(w) > 12 n^3/4, it follows by standard arguments (e.g. the Reflection Principle for Brownian motion) that 

    (min_s ∈ [0,n'] B_s < 14 n^3/4 |  B_0=√(t) ,  B_n' = √(ω)) ≤ C^-C'√(n) ,

uniformly in t and w. As on the complement of this event, the integral in (<ref>) is bounded by C/√(n), display (<ref>) is equal to

    n^1/8( B_k ∈√(log 2)(n-k) + _n-k ,∀ k ∈[1, n']  |  B_0 = √(t) , B_n' = √(w)) (1+o(1)) + O  (^-C √(n))  .

Tilting by s ↦ -√(log 2)(n-s), the last probability is further equal to

    (B_k ∈_n-k , ∀ k ∈ [1, …, n']  |  B_0 = √(t̂), B_n' = √(ŵ))  ,

where √(t̂) := √(t) - √(log 2)  n ∈_n and √(ŵ) := √(w) - √(log 2) n^3/4∈_n^3/4. Standard Brownian motion estimates (c.f. <cit.>) then show that the last probability has the same asymptotics as that of the probability for the same Brownian motion to stay positive on [1,n'], namely

    2√(t̂)√(ŵ)/n'(1+o(1))= 2√(t̂ŵ)/n(1+o(1))   ,
 
uniformly in the ranges of t and w, so that (<ref>) is then equal to 2n^- 78√(t̂ŵ)(1+o(1)), also uniformly in t and w.

At the same time, if η is chosen small enough,

    (B_n'^2 ∈ w  , B_n'>0 | B_0 = √(t))     = 1/√(2π n' w)^-(√(t) - √(w))^2/n'
        = 1/√(2 π w n) 2^-n'exp( -2√(log 2)(√(t̂) - √(ŵ)) 
    	-t̂/n') (1+o(1))  .


Combining all of the above we get

    p_n(t ;  w) = √(2/π) 2^-n' n^-11/8 √(ŵ)/√(w)^2 √(log 2)√(ŵ) √(t̂)^-2√(log 2)√(t̂) -t̂/n'(1+o(1))  .

where the o(1) goes to 0 as n →∞, uniformly in the ranges of t and w.
Plugging this in (<ref>) shows that the ratio there is asymptotically equivalent as n →∞ to a quantity which does not depend on t. Since the ratio is always bounded by one, this implies that the difference in (<ref>) goes to 0 as n →∞ uniformly in t,t' and any φ with φ_∞≤ 1 and completes the proof.




 §.§ DGFF clusters


Next, we address the i.i.d. structure of the DGFF clusters. In order to simplify the notation, for any y ∈ and k ≥ 1 we shall identify _k(y) with _k, so that for any φ:^_k→ we may write φ(h_n(_k(y)) to denote its value on h_n(_k(y)) as an element of ^_k. With this in mind, we now prove,


For each r ≥ 1 there exists a measure ν_r on ^_r with Radon marginals such that, for all λ≥ 0 and M ∈ (0,∞), 

    lim_n →∞sup__n-rsup_(φ_n,y)_y ∈_n-r| exp(-λ∑_y ∈_n-rφ_n,y(h_n(_r(y))) )  
    
    - exp(- 1√(n)∑_y ∈_n-r∫_^_r(1-^-λφ_n,y(ω)) ν_r(ω) ) | = 0  ,
 where the first supremum is taken over all sets _n-r⊆_n-r such that |y ∧ y'| < r_n for y ≠ y' ∈_n-r, and the second is over all families (φ_n,y:y ∈_n-r) of measurable functions φ_n,y: ^_r→_+ satisfying  

    φ_n,y_∞≤ M 
       ;   (φ_n,y) ⊆{ω∈^_r : min_x ∈_r	|ω(x)| ≤ M } .



Conditional on h_n(_r_n), the first expectation in the statement of the lemma is equal to

    ∏_y ∈_n-r( 1 - ∫(1-^-λφ_n,y(ω)) ν_n,r(h_n([y]_r_n)  ; ω))  ,

where the probability measure ν_n,r(v  ; ω) above is given by

    ν_n,r(v  ; ω) = (W_v + h_r(_r) ∈ω)  ,

where h_r is a DGFF on _r and W_v is scalar Gaussian with mean v and variance (n-r_n-r)/2, independent of h_r.

Now for any ψ which obeys the same bounds as φ_n,y, we have

    | ∫ψ(ω) ν_n,r(v  ; ω) -
    ∫_|u| ≤ r_n log r_n∫ψ(u+ω) (W_v ∈ u) (h_r(_r) ∈ω) | 
    ≤ M ∑_x ∈_r(|h_r(x)| > r_n log r_n - M)  ,

Since h_r(x) is Gaussian with mean 0 and variance r/2, the right hand side above is at most C ^-C' (r_nlog r_n)^2 = o(n^-1/2) for all n large enough, for some C, C' > 0 depending on r and M. Similarly, we have that (W_v ∈ u)/ u = π^-1/2 n^-1/2 (1+o(1)) uniformly in |u|,|v| ≤ r_n log r_n. Since also

    |∫_|u| > r_n log r_n∫ψ(u+ω) (h_r(_r) ∈ω)  u  |
    
    ≤ M ∑_x ∈_r∫_|u| > r_n log r_n(|h_r(x)| > |u| - M)  u= o(n^-1/2)  ,

if we set,

    ν_r(ω) := 1√(π)∫(h_r(_r) + u ∈ω)  u  ,

then

    ∫ψ(ω) ν_n,r(v  ; ω) = (1+o(1)) 1√(n)∫ψ(ω) ν_r(ω) 
      as  n →∞ ,

uniformly in |v|<r_n log r_n and all measurable functions ψ satisfying the same bounds as φ_n,y. 
Moreover, since h_r(x) is Gaussian with mean 0 and variance r/2 for each x ∈_r, it is easy to check that all marginals of ν_r are a constant multiple of the Lebesgue measure and therefore Radon as desired. In particular, the second integral in (<ref>) is bounded by M ∑_x ∈_rν_r^(x)([-M, M]) := C(M,r) < ∞ for all such functions ψ, where ν^(x)_r denotes the x-th marginal of ν_r.

Since 1-^-λφ_n,y has the same support as φ_n,y and 1-^-λφ_n,y_∞≤λ M, it follows that on the event

    {max_y ∈_n-r |h_n([y]_r_n)| ≤ r_n log r_n } ,

the product in (<ref>) is equal to

    exp( ∑_y ∈_n-rlog( 1 - 1+o(1)√(n)∫(1-^-λφ_n,y(ω)) ν_r(ω) )) 
    
    =
    exp( -1√(n)∑_y ∈_n-r∫(1-^-λφ_n,y(ω)) ν_r(ω) )) + o(1)  .

Above we have used Taylor expansion for the log together with the fact that the first integral is uniformly bounded by C(λ M,r), as well as the inequality |^-α-^-(1+ϵ)α| ≤ 2^-1|ϵ| valid for all α≥ 0 and |ϵ| ≤12. Since the probability of (<ref>) goes to 1 as n →∞, thanks to Proposition <ref>, the lemma now follows by taking expectation.





§ PHASE A: PROOF OF THEOREM <REF>


In this section we prove Theorem <ref>, which is the key result for phase A.
Thanks to Theorem <ref>, we can restrict our attention to _n^[n-r, n] instead of _n(u), namely to those leaves which belong to r_n-clusters whose root is essentially at a finite distance from the leaves. This is because the remaining leaves do not survive the isomorphism. For the sake of proving Theorem <ref>, it will be useful to take into consideration only such clusters where, in addition, the local time trajectory of their root is properly repelled.

To this end, recall the definition of _n,t^K,η(u) from (<ref>) and for r ∈ [0,n/2] let us set,

    _n,t^r, η(u) := _n,t^[n-r, n](u) ∩_n,t^[n/2, n-r], η(u)   .

As usual, whenever t is omitted from the notation, its value is assumed to be t_n^. Our first task is therefore to extend Theorem <ref> to the set _n^r,η(u).


Let η∈ (0,1/2). For any u ≥ 0,

    lim_r →∞lim sup_n →∞( _n(u) ∖_n^r,η(u) ≠∅) = 0  .

and, in addition, for any δ > 0, 

    lim_r →∞lim sup_n →∞( | [_n(u) ∖_n^r,η(u) ]_r_n| > δ√(n)) = 0  .



Next, we will need the following result to assert the non-triviality of the limit in Theorem <ref>. This result will also be used in the proofs of Propositions <ref> and Proposition <ref> below.


Let η∈ (0,1/2). For any u ≥ 0,

    lim_r →∞lim_δ→ 0lim sup_n →∞( |[_n^r,η(u) ∩_n(0) ]_n-r| ≤δ√(n)) = 0  .



The main two ingredients in the proof of Theorem <ref> are the following two propositions:


Fix η > 0 to be small enough and let u ≥ 0. For all r ≥ 1, there exists C_A_1^r  = C_A_1^r(u) ∈ [0,∞) such that for any δ > 0,

    lim_r →∞lim sup_n →∞(|
    |[_n^r,η(u) ∩_n(0)]_n-r|/|[_n^r,η(u) ]_n-r| - C_A_1^r| > δ) = 0  .





Fix η > 0 to be small enough and let u ≥ 0. For all r ≥ 1, there exists C_A_2^r  = C_A_2^r(u) ∈ [0,∞) such that for all λ≥ 0 

    lim_r →∞lim sup_n →∞| exp(-λ|[_n^r,η(u) ∩_n(u) ]_n-r| ) 
    - exp(-C_A_2^r1√(n)|[_n^r,η(u)]_n-r| (1-^-λ) ) | = 0  .



Let us first prove the theorem.

We fix η > 0 small enough and an arbitrary u > 0, omitting as usual the dependency on these parameters in the sequel. Thanks to the first part of Proposition <ref>, 

    |[_n]_n-r| -  
    |[_n^r ∩_n ]_n-r|  0

in probability as n →∞ followed by r →∞. 
Using that |^-α - ^-β| ≤ |α-β| for α, β≥ 0 and the bounded convergence theorem, it then follows that for any λ≥ 0, under the same limits we have,

    exp(-λ|[_n^r ∩_n ]_n-r| ) 
    - exp(-λ|[_n]_n-r| )
     0  .

On the other hand, thanks to the second part of Proposition <ref> and the fact that ^r_n is (r_n,n-r)-clustered by definition, under the same limits we have

    1√(n)(|[_n]_r_n| - 
    |[_n^r]_n-r| )  0  ,

in probability, which implies as before that for any λ≥ 0, and C_A_2^r ≥ 0,

    exp(-C_A_2^r1√(n)|[_n^r]_n-r| (1-^-λ) ) - 
    exp(-C_A_2^r1√(n)|[_n]_r_n| (1-^-λ) )  0  ,

under the same limits.

Using now Proposition <ref> and Proposition <ref> for the first, resp. second expectation in (<ref>) and combining with (<ref>), we get 

    lim_r →∞lim sup_n →∞|
    exp(-C_A_2^r1√(n)|[_n]_r_n| (1-^-λ) ) -
    exp(-C_u Z̅ (1-^-λ) ) | = 0  .

Thanks to Lemma <ref>, we know that the sequence (1√(n)|[_n]_r_n| : n ∈) is tight and hence admits a subsequential weak limit, which we can denote temporarily by ||. Taking a limit along this subsequence, for any r ≥ 0, the first expectation therefore converges to exp(-C_A_2^r || (1-^-λ)). Plugging this back in (<ref>), we obtain

    lim_r →∞exp(-C_A_2^r || (1-^-λ) ) =
    exp(-C_u Z̅ (1-^-λ) )  .

Since this holds for all λ≥ 0, it follows that C_A_2^r ||  C_u Z̅ as r →∞. Since Z̅ is positive and finite with positive probability and C_u > 0, we must have that C_A_2^r → C_A_2 as r →∞ for some C_A_2∈ (0,∞) and that || = C_u C_A_2^-1Z̅ in law. Since this holds for any choice of a sub-sequence, we get
that as n →∞,

    1√(n)|[_n]_r_n| 
     C_u C_A_2^-1Z̅ .


Since Z̅ is positive almost surely the above convergence together with (<ref>) yields 
    |[_n]_r_n|/|[_n^r]_n-r| 1
      ,     |[_n(0)]_r_n| - |[_n^r ∩_n(0)]_n-r|/|[_n^r ]_n-r| 0 ,

both in probability as n →∞ followed by r →∞, where we have also used that the numerator in the second ratio is bounded by |[_n]_r_n| - |[_n^r]_n-r|. Using this together with Proposition <ref> then gives

    1√(n)|[_n(0)]_r_n|/1√(n)|[_n]_r_n| - C_A_1^r 0  ,

in probability under the same limits. In particular, the sequence r ↦ C_A_1^r is Cauchy and hence must converge to a limit, which we denote by C_A_1∈ [0,∞). 

Taking this into consideration, using (<ref>) together with (<ref>) then gives that, as n →∞,

    1√(n)|[_n(0)]_r_n|
    ⟹ C_A_1 C_A_2^-1 C_u Z̅ .
 
Setting C_A to be the product of the constants on the right hand side, noting that thanks to Proposition <ref> it cannot be zero, this completes the proof of the first part of the theorem.

Turning to the second part of the theorem, we need to prove that for any δ > 0,

    lim_n →∞( |^[r_n,n-r_n]_n,t^_n(0)| > δ√(n))=0 .

To this end, we use the soft entropic repulsion of local time trajectories of non-visited leaves, as stated in Proposition <ref>. Accordingly, we fix η' > 0 small enough for the condition in the proposition to hold, and notice that by the union bound and Markov's inequality, we can bound the probability in (<ref>)
from above by

    ( |_n∖𝒪^[r_n,n-r_n], η'_n| > δ/2√(n)) + 2/δ√(n)|^[r_n,n-r_n]_n,t^_n(0)∩𝒪^[r_n,n-r_n], η'_n| .
 Since the first term in (<ref>) tends to zero as n →∞ by Proposition <ref>, in order to obtain (<ref>) it will suffice to show that the second one does as well. 

To this end, observe that any x ∈^[r_n,n-r_n]_n,t^_n(0) belongs to some r_n-cluster with root [x]_k(x) having depth k(x) ∈ [r_n,n-r_n]. Furthermore, that the root has depth exactly k(x) means that, if ^x([x]_k) denotes the sub-tree rooted at [x]_k(x) not containing x, the intersection _n ∩^x([x]_k(x)) cannot be empty. Finally, if x also belongs to 𝒪^[r_n,n-r_n], η'_n then we must have 

    √(L_t^_n([x]_k(x)))≥√(log 2)(n-k(x)) + n^η' .

Therefore, if we set √(s_n(k)):=√(log 2)(n-k) + n^η', by gathering all these facts we can bound the expectation in (<ref>) from above by 

    ∑_x ∈_n∑_k=r_n^n-r_n (x ∈_n)(_n ∩^x([x]_k)≠∅ |  L_t^_n([x]_k) ≥ s_n(k) , x ∈_n) .
 Furthermore, since the local time fields L_t^_n(^l_n-k([x]_k)) and L_t^_n(^r_n-k([x]_k)) are independent given L_t^_n([x]_k), one can further bound (<ref>) by 

    ∑_x ∈_n∑_k=r_n^n-r_n (x ∈_n)(_n-k,s_n(k)≠∅) .
 A straightforward computation using Lemma <ref> then shows that, for all n sufficiently large,  (<ref>) is at most

    C n ^-√(log 2) n^η'|_n| ≤ C^2 n^7/4^-√(log 2) n^η'
 for some constant C > 0, which implies that the second term in (<ref>) also tends to 0 as n →∞, thus yielding (<ref>).




 §.§ Proof of Proposition <ref> and Proposition <ref>


Fixing u, η as in the statement of the proposition, we henceforth omit them from the notation as usual. Since _n ∖_n^r ⊆_n^[r_n, n-r]∪_n^[r_n, n-r), thanks to Lemma <ref>, the second part of Theorem <ref> and the union bound, we readily 
have the second claim in the proposition.

Turning to the first, for any n/2 > r > r' ≥ 1, we can write,

    _n ∖_n^r  ⊆ (_n ∩_n^[r_n, n-r'))
    ∪(_n ∩^[r_n, n-r]_n ∩_n^[n-r', n])  .

For the second set on the right hand side, conditioning on L_t^_n(_n), we can write

    (|[_n ∩^[r_n, n-r]_n ∩_n^[n-r', n]]_r_n|
     |   L_t^_n(_n)) 
    ≤∑_y ∑_x ∈(y) ∩_n(|h_n(x)| ≤√(u))  
     ,

where y ∈ [^[r_n, n-r]_n ∩_n^[n-r', n]]_n-r' in the outer sum.

By definition, there are at most 2^r' terms in the inner sum and since h_n(x) is Gaussian with variance n/2, each of the terms is at most C √(u)/√(n). It follows that the right hand side above is bounded by C_r',u |[_n^[r_n, n-r]]_r_n| / √(n) for some C_r', u > 0.
Therefore, for any δ > 0,  on the event that |[_n^[r_n, n-r]]_r_n| ≤δ√(n), by Markov's inequality we shall have

    ([_n ∩^[r_n, n-r]_n ∩_n^[n-r', n]]_r_n≠∅ |  L_t^_n(_n) ) ≤ C_r', uδ .

Taking expectation and using the union bound, the probability that the second set on the right hand side of (<ref>) is not empty is at most

    C_r', uδ + (|[_n^[r_n, n-r]]_r_n| > δ√(n))  .

But then, thanks to Lemma <ref>, for any r' the above will go to zero as n →∞ followed by r →∞ and then δ→ 0. 

At the same time, by Theorem <ref> the probability that the first set on the right hand side of (<ref>) is not empty tends to 0 when n →∞ followed by r' →∞.
Combining the two and using the union bound, the result follows.



Fixing η as in the statement of the proposition, we suppress the dependency on this parameter in the sequel. For any u > 0, r ∈ [0, n/2] the event {_n(u) ≠∅} is always included in 

    {_n(u) ∖_n^r(u) ≠∅}∪{[ _n(u) ∩_n^r(u) ]_n-r≠∅} .

As in the proof of Proposition <ref> (display (<ref>)), the probability of the second event is at most 

    C_r, uδ + (|[_n^r(u)]_n-r| > δ√(n))  ,

for some C_r,u > 0 and any δ > 0. 

At the same time, by Proposition <ref>, the probability of the first event in (<ref>) can be made arbitrarily small by choosing r large enough and then n large enough. It follows that

    lim sup_r →∞lim_δ→ 0lim sup_n →∞( (_n(u) ≠∅) - 
    (|[_n^r(u)]_n-r| > δ√(n)) )
    ≤ 0  .

Thanks to the second part of Proposition <ref> the first probability aboves tends to 1 as n →∞ followed by u →∞. Combined with the above statement, this gives

    lim_u →∞lim sup_r →∞lim_δ→ 0lim sup_n →∞( |[_n^r(u) ]_n-r| ≤δ√(n)) = 0  ,

but then also,

    lim_u →∞lim_δ→ 0lim sup_n →∞( |[_n(u) ]_r_n| ≤δ√(n)) = 0  ,


Now, by the Markov property of local time, for any u > 0 and conditional on L_t^_n-1(_n-1), the distribution of |[_n, t^_n-1(0)]_r_n| dominates a Binomial distribution with |[_n-1, t^_n-1(u)]_r_n-1| trials, each having success probability 2^-u - ^-2u. Therefore, by Chebyshev's inequality, 
on {|[_n-1, t^_n-1(u)]_r_n-1| > δ^u √(n-1)} the conditional probability,

    ([|_n,t^_n-1(0)]_r_n| ≤δ√(n) ,|  L_t^_n(_n-1) )

goes to 0 as n →∞ uniformly in L_t^_n-1(_n-1). 
Taking expectation and using the union bound, in light of (<ref>) we get

    lim_δ→ 0lim sup_n →∞(|[_n,t^_n-1(0)]_r_n| ≤δ√(n)) = 0  .


To replace t_n-1^ by t_n^ in (<ref>), we observe that Δ_n = t_n^ - t_n-1^≤ 2n for all n large enough. Consequently it is enough to argue that within such additional local time, a uniformly positive fraction of the clusters of [_n,t^_n-1(0)]_r_n will not be entirely visited with probability tending to 1 with n. To this end, we first observe that the probability that x ∈_n is not visited within Δ_n time is equal to the probability that a Poisson random variable with rate Δ_n/n ≤ 2 is equal to zero. This probability is at least ^-2. To see how this computation implies that at least a ^-6 fraction of the clusters in [_n,t^_n-1(0)]_r_n are not entirely visited with high probability, we proceed as in many of the proofs in Section <ref>. We pick one leaf from each of the clusters, condition on the local time field (for a random walk run up to time Δ_n) on _r_n and exclude the event that max_x ∈_r_n L_Δ_n(x) > 2Δ_n as in Lemma <ref>. Then the events of no-visit become (conditionally) independent and occur with probability at least ^-2Δ_n/(n-r_n)≥^-5 (this bound can be obtained using the same argument leading to the bound ^-2 from before). Chebyshev's inequality then completes the argument. We omit the details as this argument was used many times in the past.

Turning to the statement of the proposition, for any u ≥ 0 and δ > 0, the probability in (<ref>) is bounded above by

    (|[_n,t^_n(0)]_r_n| ≤ 2δ√(n)) 
    + 
    (|[_n,t^_n(u) ∖_n^r(u) ]_r_n| > δ√(n))  .
 
Using (<ref>) for the first term (with t^_n instead of t^_n-1) and Proposition <ref> for the second one then completes the proof.




 §.§ Proof of Proposition <ref> and Proposition <ref>

Using the results in the previous subsection, we can now give proofs for Proposition <ref> and Proposition <ref>.


We fix u ≥ 0 and let η > 0 to be as small as needed for Lemma <ref> to hold, omitting the dependence on both parameters from the notation henceforth. We let also r ≥ 1 and for any l ∈ (r, n/2), observe that conditional on L_t^_n(_n-l) and [_n^r]_n-r, the clusters

    { L_t((y)) :  y ∈ [_n^r]_n-r-1}

are independent, with the law of L_t^_n(y) given by P_l^l-r-1(L_t^_n([y]_n-l) ; ·) from (<ref>). In particular, the events {_n(0) ∩(y) ≠∅} for y as above are conditionally independent and each occur with probability

    ∫(_r+1, v(0) ≠∅ | _r+1,v(u) ≠∅) 
    _l^l-r-1(L_t^_n([y]_n-l)  ;  v)  .


Since [y]_n-l∈ [_n^[n/2, n-r]]_n-l, we must have √(L_t^_n([y]_n-l))∈√(log 2) l + _l. Then, thanks to Lemma <ref>, the difference between the integral in (<ref>) and

    C_A_1^r,l := ∫(_r+1, v(0) ≠∅ | _r+1,v(u) ≠∅) 
    μ_l^l-r-1 ( v)  .

can be made smaller than δ / 2, for any δ > 0, uniformly in n by choosing l large enough. It follows that under the conditioning, the law of 
|[_n^r∩_n(0)]_n-r
is stochastically smaller, resp. larger than that of a Binomial with |[_n^r]_n-r| trials and probability (C_A_1^r,l + δ/2) ∧ 1, resp. (C_A_1^r,l - δ/2) ∨ 0 for success. It follows by standard arguments (e.g. Chebyshev's inequality), that for any arbitrary fixed δ' > 0, on

    {|[_n^r]_n-r| > δ' √(n)} ,

the conditional probability of

    {|
    |[_n^r(u) ∩_n(0)]_n-r|/|[_n^r(u) ]_n-r| - C_A_1^r,l| > δ} ,

will go to 0 as n →∞, uniformly in the random variables on which we condition.

Taking expectation to get rid of the conditioning, using Proposition <ref> to bound the probability of the complement of the event in (<ref>) this shows that by choosing r large enough and then δ' small enough, for any δ > 0 there exists l_0 > 0 such that whenever l > l_0 and n is chosen large enough, the (unconditional) probability of (<ref>) is less than 1/2.
Fixing any such r and using the union bound, this shows that for all δ > 0, there exists l_0 such that if l ∧ l' > l_0 and n is large enough, the ratio above is δ-close to both C_A_1^r,l and C_A_1^r,l' with positive probability. This can only happen if
|C_A_1^r,l - C_A_1^r,l'| < 2δ. Therefore the sequence l ↦ C_A_1^r, l is Cauchy and hence must converge to a finite limit, which we denote by C_A_1^r. 

Going back to (<ref>), we can now assert that for any δ > 0, if l is chosen large enough, then on (<ref>), the probability of (<ref>) with C_A_1^r,l replaced by C_A_1^r will also go to 0 as n →∞ uniformly as before. Rerunning the previous argument, this shows 

    lim_r →∞lim sup_n →∞(|
    |[_n^r(u) ∩_n(0)]_n-r|/|[_n^r(u) ]_n-r| - C_A_1^r| > δ) = 0   ,

which is what we wanted to prove.



Let u ≥ 0 and λ≥ 0. Omitting the dependence on u as usual, for any 1 ≤ r ≤ n, we write the first exponent in (<ref>) as

    -λ∑_y ∈ [_n^r]_n-r 1_A_r,t_n^(y)(h_n(_r(y)) )  ,

with 

    A_r,t(y) := {ω∈^_r(y) : ∃ x ∈_r(y) :  L_t(x) + ω(x)^2 ∈ [0,u] } .

Identifying _r(y) with _r as in Subsection <ref>, we note that 1_A_r,t^_n(y), which is a random function, is supported on {ω∈^_r : min_x ∈_r |ω(x)| ≤√(u)} for any n, y and any realization of L_t^_n(_n).


Thanks to Lemma <ref>, conditional on [_n^r]_n-r and L_t^_n(_r(y)) for all y ∈ [_n^r]_n-r, the first expectation in (<ref>) is then equal to

    exp(- 1√(n) (1-^-λ) ∑_y ∈ [_n^r]_n-rν_r(A_r,t_n^(y)) ) + o(1)  ,

with the o(1) tending to 0 as n →∞ uniformly in L_t^_n(_n).
Moreover since the marginals of ν_r are Radon, in view of the support of 1_A_r,t(y), we have

    ν_r(A_r,t_n^(y)) ≤∑_x ∈_rν_r ( ω∈^_r : ω(x) ∈ [-√(u), √(u)]) =: C(r,u) < ∞ ,

for all n and y and any realization of L_t^_n(_n).

As in the proof of Proposition <ref>, for any l ∈ (r, n/2), if we now just condition on L_t^_n(_n-l) and [_n^r]_n-r, 
then the clusters

    { L_t^_n((y)) :  y ∈ [_n^r]_n-r-1}

are independent, with the law of L_t^_n(y) given by P_l^l-r-1(L_t^_n([y]_n-l) ; ·). 
In particular, under this conditioning, the random variables ν_r(A_r,t_n^(y)) for y ∈ [_n^r]_n-r are independent and have mean

    ∫(ν_r (A_r,v(1))   | _r+1,v≠∅)_l^l-r-1(L_t^_n([y]_n-l)  ;  v)  ,

where we write '1' to denote the (single) child of the root of _r+1.

Therefore, if we set

    C_A_2^r,l := 
    ∫(ν_r (A_r,v(0))   | _r+1,v≠∅) μ_l^l-r-1 ( v)

then, since the expectation above 
is bounded uniformly in v in view of (<ref>) and also √(L_t^_n([y]_n-l))∈√(log 2)l + _l because [y]_n-l∈[_n^[n/2, n-r]]_n-l, we can use Lemma <ref> to claim that the integrals in (<ref>) and (<ref>) can be made arbitrarily close to each other, uniformly in n and L_t^_n(_n-l), by choosing l large enough.

Using again that the ν_r(A_r,t_n^(y)) are bounded uniformly, it then follows from Chebyshev's inequality that for any δ, δ' > 0 on

    {|[_n^r]_n-r| > δ' √(n)} ,

the conditional probability of

    {|
    ∑_y ∈ [_n^r]_n-rν_r(A_r,t_n^(y))/|[_n^r]_n-r| - C_A_2^r,l| > δ} ,

goes to 0 when n →∞, as long as l is chosen large enough. Proceeding exactly as in the proof of Proposition <ref>, we assert that for any r large enough, the limit as l →∞ of C_A_2^r,l must exist, and that if we denote it by C_A_2^r ∈ [0,∞) then

    lim_r →∞lim sup_n →∞( |
    ∑_y ∈ [_n^r]_n-rν_r(A_r,t_n^(y))/|[_n^r]_n-r| - C_A_2^r| > δ) = 0  ,


Using that |^-α - ^-β| ≤ |α - β| for all α,β≥ 0, on the complement of the event in (<ref>) we have that the difference between the first term in (<ref>) and

    exp(- 1√(n) (1-^-λ) C_A_2^r | [_n^r]_n-r| )
 is less or equal than 

    δ(1-^-λ)| [_n^r]_n-r|/√(n)≤δ(1-^-λ)| [_n]_r_n|/√(n) .
 In particular, by the tightness of the sequence (1√(n)| [_n]_r_n| : n ≥ 1) as given by Lemma <ref>, we see that this difference tends to 0 in probability as n →∞ followed by r →∞. Since this difference is also always bounded by 2, taking expectation and using the bounded convergence theorem then yields the desired claim.





§ PHASE B: PROOF OF THEOREM <REF>


The goal in this section is to prove Theorem <ref>, which is the key result for phase B.


Let y ∈ [_n]_n-r_n and set _n(y) := _r_n(y) ∩_n.
Writing t_n(s) as a short for t_n^+sn, we first claim that 

    q_n,t_n(s)(y) := 
    (_n,t_n(s)(0) ∩_n(y) ≠∅)
    = 1/√(n)^-s (1+o(1))  ,

where the o(1) tends to 0 as n →∞ uniformly in _n(y).

Indeed, for a lower bound, observe that a random walk starting at [y]_1, has probability 1/(n-r_n) of hitting y before hitting the root. Therefore, since the number of visits from 0 to [y]_1 until time ^-1_t_n(s)(0) is Poisson with rate t_n(s), the probability that {L_t_n(s)(y)=0} is the same as the probability that a Poisson with rate t_n(s)/(n-r_n) = (log n)/2 + s + o(1) is zero. This gives

    (_n,t_n(s)(0) ∩_n(y) ≠∅) ≥(L_t(s)(y) = 0) = ^-s/√(n) (1+o(1))  .
 

For a matching upper bound, let p_n be the probability that a random walk starting at [y]_1 visits all sites in _r_n(y) before returning to the root. Such an event occurs for example if, given some fixed η' ∈ (0,1), the random walk spends at least  n^1-η' time at y before returning to the root and while accumulating this time also visits all sites in _r_n(y). We have already seen that the probability of reaching y before returning to the root is 1/(n-r_n). By the same reasoning, upon reaching y the local time accumulated at y before returning to the root is Exponential with rate 1/(n-r_n) < 2/n for all n large enough. Consequently the time accumulated will be at least n^1-η' with probability at least 1-2n^-η'. Then, recalling that _r_n(y) is the union of two trees isomorphic to _r_n, by Lemma <ref> the probability of not visiting all of _r_n(y) is, for all n large enough, bounded from above by 

    2(_r_n, n^1-η'(0) ≠∅) ≤ C ^-C' n^1/2 - η'/2 ,

whenever η'/2 < η, with η as in (<ref>). Combining all of the above, we get

    p_n ≥1/n-r_n(1-2n^-η') ( 1- C ^-C' n^1/2 - η'/2)
    ≥1/n(1-O(n^-η') )  .

Arguing as for the lower bound, the probability that {_r_n(y) ∩_n,t_n(s)(0) ≠∅} is therefore at most the probability that a Poisson with rate t_n(s) p_n ≥ (log n)/2 + s + o(1) is equal to zero. This gives

    (_n,t_n(s)(0) ∩_n(y) ≠∅) ≤(_r_n(y) ∩_n,t_n(s)(0) ≠∅)
    ≤^-t_n(s) p_n = ^-s/√(n) (1+o(1))  ,

and proves the claim in (<ref>).

Now, conditional on L_t_n(s)(_r_n), by the Markov property and the fact that _n is (r_n, n-r_n)-clustered, for any λ≥ 0, the expectation in (<ref>) is equal to

    exp( ∑_y ∈ [_n]_n-r_nlog( 1 - (q_n-r_n, L_t_n(s)([y]_r_n)(y))
    (1-^-λ) ) )

Therefore, for any given η”∈ (0,η), on the event

    {max_z ∈_r_n |L_t_n(s)(z) - t_n(s)| < n^1-η”}

we have L_t_n(s)([y]_r_n) = t_n-r_n(s + O(n^-η”)), so that by (<ref>) 

    q_n-r_n, L_t_n(s)([y]_r_n)=1/√(n-r_n)^-(s+O(n^-η”))(1+o(1))=^-s/√(n)(1+o(1)),
 where the o(1)-term tends to 0 as n →∞ uniformly in _n(y).
Plugging this in (<ref>) and using Taylor expansion for the log shows that, on the event in (<ref>), (<ref>) is equal to

    exp(- ^-s√(n)|[_n]_r_n| (1-^-λ) (1+o(1)) )  ,
 where we have also used that |[ℒ_n]_n-r_n|=|[ℒ_n]_r_n| since ℒ_n is (r_n,n-r_n)-clustered. Moreover, since |^-α-^-α(1+ϵ)| ≤ 2^-1|ϵ| for all α≥ 0 and |ϵ|< 12, we have that (<ref>) is in fact

    exp(- ^-s√(n)|[_n]_r_n| (1-^-λ) )+o(1)  .


Lastly, we note that the probability of (<ref>) tends to 1 as n →∞. Indeed, by the isomorphism we have that for all z ∈_r_n

    |L_t_n(s)(z)-t_n(s)| ≤ 2√(t_n(s))|h'_r_n(z)| + |h'_r_n(z)|^2 +  |h_r_n(z)|^2,
 so that, for n large enough, (<ref>) is implied by the intersection 

    {max_z ∈_r_n|h_r_n(z)| ≤ r_n log r_n }∩{max_z ∈_r_n|h'_r_n(z)| ≤ r_n log r_n } ,
 whose probability goes to 1 as n →∞ thanks to Proposition <ref>. Hence, by taking expectation in (<ref>), combining all of the above we arrive at (<ref>) with C_B := 1.

The proof of (<ref>) is even easier. As we have argued above, for any x ∈_n, the probability that {L_t_n(s)(x) = 0} is the probability that a Poisson with rate t_n(s)/n = (log n)/2 + s is 0. This probability is equal to ^-t_n(s)/n = ^-s/√(n). Consequently,

    |_n ∩_n,t_s(n)(0) | = |_n| ^-s√(n) ,

and (<ref>) now follows by Markov's Inequality.






§ FROM LOCAL TIME AT THE ROOT TO REAL TIME: PROOF OF THEOREM <REF>



In this section we prove Theorem <ref>, which is the key statement needed for the proof of Theorem <ref>. To this end, we shall need several preparatory results and a few new definitions. Recall that the over-lined tree notations, such as _k or _k, concern the “normal” binary tree . For any n ≥ 1 and t ≥ 0, we set

    S_n,t := ∑_x ∈_n L_t(x)
      ,   S_n,t := 2^-n S_n,t     ;      
    R_n,t := ∑_k=0^n S_k,t ,   R_n,t := 2^-n R_n,t .

Observe that, with these definitions, the total real time spent by the walk when the local time at the root is t is therefore,

    R_n,t = ^-1_n,t(0) .


In the next lemma we compute the mean and covariance structure of the above quantities. These are easy computations whose result will be needed in the near sequel.


For all t ≥ 0, n ≥ 1 and x,y ∈_n,

    S_n,t    = 2^n t        S_n,t    = 2^2n+1 t (1+o(1))  , 
     R_n,t    = (2^n+1-1) t      R_n,t    = 2^2n+3 t (1+o(1))

and

    (L_t(x) - S_n,t ,  L_t(y) - S_n,t) = 2(|x∧ y| - 1 + o(1))t  ,

where all the o(1)-terms depend only on n and tend to 0 as n →∞.


For each n ≥ 1 and x ∈_n we have that

    L_t(x) ∑_i=1^N E_i ,
 where the E_i are i.i.d. Exponentials  with rate 1/n and N is an independent Poisson of rate t/n. It then follows that L_t(x)= (t/n) n = t and L_t(x) =2(t/n) n^2 = 2nt. 
Now, set z := x ∧ y. 
Then, conditional on L_t(z) = u, L_t(x) and L_t(y) are independent and equal in law to L_u(x') and L_u(y') respectively, where x', y' are any  vertices in  satisfying |x'| = |x|-|z| and |y'| = |y|-|z|. From this it follows that (L_t(x) L_t(y)) =  L_t(z)^2 = 2t|z| + t^2 which, by subtracting the product of the means L_t(x)  L_t(y)=t^2, yields that

    (L_t(x), L_t(y) ) = 2|x ∧ y|t  ,

for any x,y ∈.

Summing the means of L_t(x) over all x ∈_n gives S_n,t = 2^n t. For the variance of S_n,t, by grouping all pairs of vertices according to the depth of their common ancestor, we can write S_n,t as 

    ∑_x,y ∈_n(L_t(x), L_t(y) ) = ∑_k=0^n 2^k 2^(2(n-k)-1) ∨ 0 2t k = 
    2^2n t ∑_k=0^n 2^-k + 1_{k=n} k = 2^2n+1 t (1+o(1))  ,

in accordance with (<ref>).

Now, to check (<ref>), by summing the means of S_k,t over k=0,…,n, we immediately obtain R_n,t = (2^n+1 - 1)t. To compute the variance of R_n,t, we again sum all covariances as in (<ref>), only that the term 2^(2(n-k)-1) ∨ 0 is now replaced by 2(2^n-k - 1)^2 + 1_{k=n}, to account for leaves at different depths. This gives an additional factor of 4 in the asymptotic expression for R_n,t and completes the proof of (<ref>).

Finally, to show (<ref>) we first observe that for all n ≥ 1 and x ∈_n,

    (L_t(x) - S_n,t , S_n,t) = 0 .

Indeed, summing L_t(x) - S_n,t over all x ∈_n gives 0, which implies that the sum of the covariance in (<ref>) over all such x-s is 0 as well. Then, by symmetry, this must also be the case for each x individually. Writing (L_t(x) - S_n,t ,  L_t(y) - S_n,t) as 

    (L_t(x) ,  L_t(y)) - 
    (L_t(x) - S_n,t, S_n,t) 
    - (S_n,t,  L_t(y) - S_n,t) -
     S_n,t ,

we can use (<ref>), (<ref>) and (<ref>) to evaluate the terms in the last display and thus obtain (<ref>).


The next step is to derive analogous formulas for S_n,τ and R_n,τ when τ is a stopping time of the local time field (L_t(_n) : t ≥ 0).

 For k ≥ 1, let (𝔉_k,t : t ≥ 0) be the filtration given by 𝔉_k,t:= σ(L_s(_k) : 0≤ s ≤ t). Then, for any (not necessarily integrable) stopping time τ with respect to (𝔉_k,t : t ≥ 0) which is finite almost-surely,

    S_k,τ = 2^k τ and  R_k,τ = (2^k+1-1)τ .



 Since by the Markov property of X_n and Lemma <ref> we have that the processes (S_k,t - 2^k t : t ≥ 0) and (R_k,t - (2^k+1-1)t : t ≥ 0) are martingales with respect to (𝔉_k,t : t ≥ 0), it then follows from the optional stopping theorem that for any M>0 

    S_k,τ∧ M = 2^k  (τ∧ M) 
     and  R_k,τ∧ M = (2^k+1-1) (τ∧ M).

Thus, since τ∧ M ↗τ almost surely as M →∞ and the trajectory u ↦ L_u(x) is nonnegative and increasing for all x ∈, by taking M →∞ in (<ref>) the monotone convergence theorem then yields (<ref>).	


Next, we claim that, for all n ≥ 1, R_n,t can be well approximated by 2S_k,t if k is large enough.


There exists C > 0 such that for all 1 ≤ k ≤ n, ϵ > 0 and any stopping time τ with respect to (𝔉_k,t: t ≥ 0) (where 𝔉_k,t is as in Lemma <ref>), which is finite almost-surely,

    (|R_n,τ - 2S_k,τ|  > ϵ)
    ≤ C  (ϵ^-22^-k +ϵ^-1 2^-(n-k))S_k,τ .



Conditional on L_t(_k), the law of R_n,t is the same as that of

    2^-n(R_k-1,t + ∑_x ∈_k R^(x)_n-k, L_t(x))  ,

where (R^(x)_n-k, L_t(x): x ∈_k) are independent and satisfy R^(x)_n-k, L_t(x) R_n-k, L_t(x) for each x ∈_k. It then follows from Lemma <ref>
that the conditional mean and variance of R_n,t are respectively

    2^-n R_k-1, t + 2 S_k,t(1 - 2^-(n-k+1))
        ,     
    2^-k+3S_k,t (1+o(1)) ,

with the o(1)-term tending to 0 as n-k →∞. Therefore. for any ϵ > 0, whenever 2^-n R_k,t≤ϵ/2 we can use Chebyshev's inequality to conclude that

    ( |R_n,t - 2S_k,t| > ϵ |  L_t(_k) ) 
    ≤ C' ϵ^-2 2^-kS_k,t

for some properly chosen C' > 0. Now, by the Markov property of local times, (<ref>) also holds if t is replaced by any stopping time as in the statement of the lemma. By taking expectation and then using the union bound together with Markov's inequality, we obtain that 

    (|R_n,τ - 2S_k,τ|  > ϵ)
    ≤ C' ϵ^-2 2^-kS_k,τ +  2 ϵ^-1 2^-n R_k,τ ,

which, by Lemma <ref>, is at most the right hand side of (<ref>) if C is chosen correctly.


When n,n-k are large, the previous lemma shows that 2S_k,t acts as a good approximation of R_n,t = ^-1_n,t(0). Consequently, instead of running the walk until real time s ≥ 0 we can run it until the local time at the root is τ_k,s, where τ_k,s is the stopping time

    τ_k,s := inf{t ≥ 0 :  2S_k,t > s  } .

The advantage of this is that τ_k,s depends only the random walk restricted to _k and, moreover, that the asymptotic law of L_τ_k,s(_k) can be easily derived. In order to do this, we first need to obtain a suitable control on the mean of S_k,τ_k,s. 

 For any k ≥ 1 and s ≥ 0, we have S_k,τ_k,2^k+1s≥ s and

    S_k,τ_k,2^k+1s≤ s+ 1 .
 
In particular, for any fixed k ≥ 1, as s →∞, in probability,

    S_k,τ_k,2^k+1s -s /√(s)⟶ 0 .
 


 First, notice that, since t ↦ L_t(x) is right-continuous for any x ∈ by definition of L_t, one has that t ↦ S_k,t is right-continuous as well. In particular, by definition of τ_k,2^k+1s it follows that S_k,τ_k,2^k+1s≥ 2^k s and consequently that S_k,τ_k,2^k+1s≥ s. Moreover, S_k,τ_k,2^k+1s - 2^ks is precisely the additional local time collected at the leaves in _k from the moment the sum of their local times reached 2^ks and until the walk returns to the root for the first time after. That is, if we set

    𝒯^1_k,s:= inf{ t ≥ 0 : ∑_x ∈_k_k,t(x) ≥ 2^k s} and 𝒯^2_k,s:= inf{ t ≥𝒯^1_k,s : X_k,t=0} ,
 then 

    S_k,τ_k,2^k+1s - 2^ks = ∑_x ∈_k( _k,𝒯^2_k,s(x) - _k,𝒯^1_k,s(x)) .
 

Now, by the strong Markov property of the random walk on _k, the right hand side of (<ref>) is equal in law to the total local time accumulated at _k for a random walk starting at one of these leaves, and run until reaching the root. Since the depth of such a walk forms a standard Gambler's ruin problem on {0, …, k} with probability 2/3 of winning a game, it follows by standard computations that the mean number of returns to the leaves before getting to the root is 2^k-1. Since at each visit to the leaves, the sum of their local times increases by an Exponential with mean 1, it follows that 

    ( S_k,τ_k,2^k+1s - 2^ks) = 2^k - 1  ,
 from where (<ref>) readily follows. To conclude the proof we observe that, since  S_k,τ_k,2^k+1s≥ s, Markov's inequality and (<ref>) together yield that for any ϵ>0

    ( |S_k,τ_k,2^k+1s-s|> √(s)ϵ) ≤ (S_k,τ_k,2^k+1s -s)/√(s)ϵ≤1/√(s)ϵ⟶ 0
 as s →∞, from where (<ref>) now follows. 


In order to derive the asymptotic law of L_τ_k,s(_k) we shall need a generalization of the central limit theorem for a càdlàg martingale stopped at a random (not necessarily stopping) time. Such a statement can be found, e.g. in <cit.>, however in a discrete time setting. In order to obtain a version of this result in continuous time, it is enough to replace a key step in the proof there with the following lemma.
 Let (W_s : s ≥ 0) be a càdlàg martingale with respect to some filtration (𝔉_s : s ≥ 0), satisfying W_s^2 = C s for some fixed C>0 and all s ≥ 0. Then, for any collection (τ_s : s ≥ 0) of finite random times such that 

    τ_s/s⟶ 1
 in probability as s →∞, we have that 

    W_τ_s - W_s/√(s)⟶ 0
 in probability as s →∞.


 To prove this result we can essentially mimic the proof of  <cit.>, substituting the use of Kolmogorov's inequality there by Doob's maximal inequality for càdlàg martingales. The straightforward details are left to the reader. 

We are now ready to derive the asymptotic law of L_τ_k,s(_k).



Let k ≥ 1. Then as s →∞,

    (L_τ_k,2^k+1 s(x) - s/√(s) :  x ∈_k )
    ⟹(0, (2(|x∧ y| - 1) + o(1))_x,y ∈_k)  ,

where the o(1)-term tends to 0 as k →∞.


 Abbreviating s':=2^k+1s, by (<ref>) in Lemma <ref> it will suffice to show that as s →∞

    (L_τ_k,s'(x) - S_k,τ_k,s'/√(s) :  x ∈_k )
    ⟹(0, (2(|x∧ y| - 1) + o(1))_x,y ∈_k)  .


To this end, we notice that, by definition of τ_k,s, for all ϵ > 0 we have

    (τ_k,s' > s(1+ϵ))  = 
    (S_k,s(1+ϵ) < s ) = 
    (S_k,s(1+ϵ) < s(1+ϵ) - ϵ s )  .

By Lemma <ref>, the mean and variance of S_k,s(1+ϵ) are s(1+ϵ) and 2s(1+ϵ)(1+o(1)), respectively. It then follows from Chebyshev's inequality that the probabilities in (<ref>) go to 0 as s →∞. Since the same holds for 
(τ_k,s' < s(1-ϵ)) via a similar argument, it follows that τ_k,s'/s → 1 in probability as s →∞. 

Now, for each x ∈_k the process (W_s(x) : s ≥ 0) given by W_s(x):=L_s(x)-S_k,s is a càdlàg martingale which, by Lemma <ref>, satisfies (W_s(x))^2 = 2(k-1 +o(1))s. We may then use Lemma <ref> (applied to each x separately) to conclude that showing (<ref>) is equivalent to proving that

    L_s(_k) - S_k,s/√(s):=	(L_s(x) - S_k,s/√(s) :  x ∈_k )
    ⟹(0, (2(|x∧ y| - 1) + o(1))_x,y ∈_k)  ,
 as s →∞. But this is now a straightforward consequence of the multivariate central limit theorem. Indeed, by splitting time into intervals of length 1 we can write 

    L_s(_k) - S_k,s/√(s) = √(⌊ s ⌋/s)( 1/√(⌊ s ⌋)∑_u=1^⌊ s ⌋ W^(u)_1(_k) )+ W^(⌈ s ⌉)_⌈ s ⌉ -s(_k)/√(s) ,
 where, for each u ≥ 1 and any δ∈ [0,1], we define W^(u)_δ(_k) := (W_u(x) - W_u-δ(x) : x ∈_k). Since W^(⌈ s ⌉)_⌈ s ⌉ -s(_k)_∞ is stochastically dominated by S_k,1, the second term in the right hand side of (<ref>) tends to zero in probability as s →∞. Therefore, upon noticing that ( W^(u)_1(_k) : u ≥ 1) are i.i.d. centered random vectors with covariance matrix equal to that on the right hand side of (<ref>), the limit in (<ref>) now follows from (<ref>) by the multivariate central limit theorem. 


With all the results above, we can now show Theorem <ref>.



Given any k ≥ 1 and s ≥ 0, from (<ref>) applied to L_t, we have 

    L_s(_k) - s/√(s) - 2h'_k(_k) _∞≤ h'^2_k(_k)_∞ + h^2_k(_k)_∞/√(s) .

By letting s →∞ on the right hand side, we see that the left hand side tends to 0 in probability as s →∞, and therefore that under the same limit,

    L_s(_k) - s/√(s)⟹ 2h'_k(_k)  .

Since h'_k is the DGFF on _k, the right hand side of (<ref>) has a Gaussian law with mean 0 and covariance matrix (2|x ∧ y|)_x,y ∈_k.

On the other hand, consider a random variable ξ∼(0,1/2) independent of the walk X_n (without loss of generality, we may assume that our current probability space is large enough to support such a ξ), as in the statement of the theorem, and for s ≥ 0 set θ_s := s - 2√(s)ξ∼(s, 2s). If we write ν_k,s:=τ_k,2^k+1θ_s then, conditional on ξ, by Proposition <ref> we have as s →∞,

    L_ν_k,s(_k ) - s/√(s) = 
    L_ν_k,s(_k ) - θ_s/√(θ_s)√(θ_s/s) - 2ξ⟹(-2ξ, (2(|x∧ y| - 1) + o(1))_x,y ∈_k)  .

It then follows from the bounded convergence theorem that unconditionally,

    L_ν_k,s(_k ) - s/√(s)⟹(0, (2(|x∧ y|) + o(1))_x,y ∈_k)  .

Since the distribution on the right hand side above tends, as k →∞, to the limiting law in (<ref>), for any 1 ≤ k ≤ n and s ≥ 0 we can find a coupling (L'_ν_k,s(_k),L”_s(_k)) of L_ν_k,s(_k) and L_s(_k) such that 

    L'_ν_k,s(_k) - s/√(s)
    - L”_s(_k) - s/√(s)_∞ 0  ,

in probability as s →∞ followed by k →∞. But then, by doing a Taylor expansion around s, under the same limits we have

    √(L'_ν_k,s)(_k) - √(L”_s)(_k) _∞ 0  ,
 
in probability, so that (<ref>) holds.

At the same time, for ν_k,s chosen in this way we have, in light of Lemma <ref> and (<ref>), that for any ϵ∈ (0,1) and s large,

    (|√(2^-(n+1)^-1_n, ν_k,s(0)) - √(θ_s)| > ϵ)     = 
    (|√(R_n, ν_k,s) - √(2θ_s)| > √(2)ϵ) 
       ≤ (θ_s ≤ s/2) + 
    (|R_n,ν_k,s - 2θ_s|  > √(s)ϵ) .
 By the standard Gaussian tail estimate, we have that (θ_s ≤ s/2) ≤^-C's for some C'>0 and all sufficiently large s. On the other hand, by the union bound and Lemmas <ref> and <ref> we have for all large enough s,

    (|R_n,ν_k,s - 2θ_s|  > √(s)ϵ)   ≤(|R_n,ν_k,s - 2S_k,ν_k,s|  > √(s)ϵ/2)+
    (|S_k,ν_k,s - θ_s|  > √(s)ϵ/4)
       ≤ Cϵ^-2((2^-k/s + 2^-(n-k)/√(s))S_k,ν_k,s + 1/√(s)(S_k,ν_k,s - θ_s))
       ≤ Cϵ^-2((2^-k/s + 2^-(n-k)/√(s)) (s+1) + 1/√(s))

which goes to 0 as s →∞ followed by k →∞ uniformly in n ≥√(s), so that the same limit holds for the probability on the left hand side of (<ref>). Notice that to obtain the upper bound on S_k,ν_k,s in (<ref>) we  first conditioned on the value of ξ and then used the bound in Lemma <ref>. 

Finally, observe that since √(θ_s) - √(s) + ξ 0 almost surely as s →∞, we can replace √(θ_s) in the left hand side of (<ref>) by √(s) - ξ, with the limit still holding. This shows (<ref>) and completes the proof.




§ CONSTRUCTION OF THE NEGATIVELY CORRELATED DGFFS: PROOF OF PROPOSITION <REF>
 

This section includes the proof of Proposition <ref>, which is the main ingredient in the proof of Theorem <ref>. 

We will show that  exists by constructing it “by hand”. To describe the construction, let  be the set of edges in  and for n ≥ 1, let also _n be the subset of , which includes all edges leading from a vertex in _n-1 to a vertex in _n. Adapting this notation to ^1 and ^2 in the obvious way, suppose that we can construct a centered Gaussian field ω = (ω(e) :  e ∈^1 ∪^2) whose covariances satisfy

    ω(e) ω(f) =
    12	   if   e = f  , 
    
    -2^-(n+1)   if   e ∈^1_n ,  f ∈^2_n  , n ≥ 1 
    
    0 			   otherwise.

We can then define (x^1) on x^1 ∈^1 to be the sum of the values under ω of the edges leading from the root of ^1 to x^1 and similarly for x^2 ∈^2. Then, it is not difficult to see that  as constructed satisfies both (<ref>) and (<ref>).

This leaves the task of showing that ω exists. To do this, we define yet another centered Gaussian field σ = (σ(e) :  e ∈). We set the variance of σ(e) for e ∈_k and k ≥ 1 to be 2^(k-2) ∨ 0. Furthermore, if e, e' ∈_k are attached to the same vertex, then σ(e) = -σ(e'), so that σ(e) σ(e') = -2^(k-2) ∨ 0. For all other pairs of edges e, e' we assume that σ(e) and σ(e') are independent of each other. Now, for x,y ∈_n with n ≥ 1, the reader can easily verify that the covariance between the sum of σ along the edges on the path from the root to x with the corresponding sum along the edges on the path from the root to y is equal to

    2^n-1   if  |x ∧ y| = n  , 
    
    0    if  0 < |x ∧ y| < n  ,
    
    -1    if  |x ∧ y| = 0  .


Now letting z^1, z^2 be the two children of the root of , we identify (z^1) and (z^2) with ^1 and ^2 respectively, so that for all n ≥ 2, we have _n = ^1_n-1∪^2_n-1. We also take an i.i.d. sequence of fields (σ_n :  n ≥ 1) all having the same law as σ. Then we define ω(e) for e ∈_n with n ≥ 2, as 2^-n/2 times the sum under σ_n of the path leading from the root of  to the vertex in _n to which e leads. It is not difficult to verify using (<ref>) that such ω satisfies (<ref>) as required.

To show (<ref>) we let Z^1_n and Z^2_n be the derivative martingales at depth n ≥ 0 for the restrictions of  to _n^1 and _n^2 respectively.
We also let ξ, ξ^1, ξ^2 ∼(0,1/2) be independent of each other and of  and set ξ^1_n := √(1-2^-n)ξ + √(2^-n)ξ^1 and ξ^2_n := √(1-2^-n)ξ + √(2^-n)ξ^2. Now,

    2^-2n∑_x ∈^1_n(√(log 2)  n - ((x) + ξ^1_n)) ^2 √(log 2)  ((x) + ξ^1_n)
    
    = ^2 √(log 2)ξ^1_n(
    2^-2n∑_x ∈^1_n(√(log 2)  n - (x) ) ^2 √(log 2) (x)
    - ξ^1_n 2^-2n∑_x ∈^1_n^2 √(log 2) (x))  .

Since  restricted to ^1 has the same law as that of h on , it follows from (<ref>) and (<ref>), that the first term in the parenthesis above converges almost surely to a random variable Z^1, which has the same law as Z. 

At the same time, it is well known that the critical exponential martingale (without the “derivative term”) vanishes in the limit (c.f. <cit.>), namely

    lim_n →∞ 2^-2n∑_x ∈_n^2 √(log 2)  h(x) = 0
      a.s.

It follows that the second term in the parenthesis of (<ref>) tends to 0 almost surely.
Lastly, since ξ^1_n →ξ as n →∞, we obtain altogether that the left hand side of (<ref>) tends almost-surely to ^2√(log 2)ξ Z^1.
Replacing ^1_n and ξ^1_n with ^2_n and ξ^2_n in (<ref>), we may apply the same reasoning to obtain the almost convergence to ^2√(log 2)ξ Z^2, where Z^2 is the limit of the derivative martingale with respect to  restricted to ^2. 
Combining both claims we get

    2^-2n(∑_x ∈^1_n(√(log 2)  (n + 1) - ((x) + ξ^1_n)) ^2 √(log 2)  ((x) + ξ^1_n) + 
    ∑_x ∈^2_n(√(log 2)  (n + 1) - ((x) + ξ^2_n)) ^2 √(log 2)  ((x) + ξ^2_n))
    ^2√(log 2)ξ ,

almost surely as n →∞, where = Z^1 + Z^2 as in (<ref>). 

Next, in view of (<ref>) and (<ref>), we observe that 

    ((x) +ξ^1_n 1_^1_n(x) + ξ^2_n 1_^2_n(x) :  x ∈^1_n ∪^2_n )

is a centered Gaussian vector with the covariance between its values at x and y given by

    (x^1) (y^1) +  (ξ_n^1)^2 = 
    12(|x^1 ∧ y^1| + 1)    if  x=x^1 ∈^1_n ,  y=y^1 ∈^1_n  , 
    (x^2) (y^2) +  (ξ_n^2)^2 = 
    12(|x^2 ∧ y^2| + 1)    if  x=x^2 ∈^2_n ,  y=y^2 ∈^2_n  , 
    (x^1) (y^2) + ξ_n^1 ξ_n^2 =
    0    if  x=x^1 ∈^1_n ,  y=y^2 ∈^2_n  ,

where |x^1 ∧ y^1| is the depth of the common ancestor of x^1 and y^1 in ^1 and similarly for |x^2 ∧ y^2|. 

We now identify as before _n(z^1) and _n(z^2) in  with
^1_n in ^1 and ^2_n in ^2 respectively, so that _n(z^1) ∪_n(z^2) =  _n+1. Then, the covariances above are equal in all cases to |x ∧ y|/2, where |x ∧ y| is the depth of the common ancestor of x,y ∈_n+1 in . This shows that the Gaussian vector in (<ref>) has exactly the same law as that of (h(x) :  x ∈_n+1). In view of (<ref>) and (<ref>), we see that the left hand side in (<ref>) tends in law to 4 Z. But then in conjunction with the full statement in (<ref>) this gives

    ^-2 log 2 + 2√(log 2)ξ  Z  .

Since the law of Λ: = ^-2 log 2 + 2√(log 2)ξ is Log-normal(-2 log 2, 2 log 2) and ξ is independent of , this shows (<ref>). Then, positivity and almost-sure finiteness of  follows immediately, since the same applies to Λ and Z.





§ APPENDIX: PROOFS OF PRELIMINARY STATEMENTS
 

This appendix includes proofs for various preliminary statements from Section <ref>. As these proofs are rather standard in the subject, we allow ourselves to be brief.



 §.§ DGFF preliminaries



Fix u ≥ 0 and η∈ (0,1/2) and set h_n^* := minh_n(_n).
For any v > √(u), we can write

    (|_n(u)| : h_n^* ≥ -v )
    
     = ∑_x ∈_n∫_-√(u)^√(u)(h_n(x) ∈ w ) 
    (min_k ∈ (0,n)(h_n([x]_k) + h_n-k^(n-k)* - m_n-k) ≥ -v  | h_n(x) = w ) ,

where h_k^(k) are independent copies of the DGFF on _k for k ∈ (0,n).

Recall that h_n(x) = h_n(x) + m_n and that (h_n([x]_k) :  k ∈ [0,n] ) is a random walk with centered Gaussian steps. Tilting by k ↦ -m_n (k/n) and setting m_n,k := m_n(k/n) - m_k, the second probability above is therefore equal to

    ( min_k ∈ (0,n)(h_n([x]_k) + h_n-k^(n-k)* + m_n,n-k) ≥ -v  |  h_n(x) = w) .

Now h_k^(k)* are exponentially tight for all k ≥ 1 <cit.> and 
m_n,k≤ 1+ log∧_n(k) <cit.>.  It then follows from considerations similar to that in the proof of Lemma 2.7 in <cit.> and Proposition 1.5 in <cit.> that 

    lim_r →∞lim sup_n →∞( min_k ∈ [r,n-r] h_n([x]_k) ≤ 0
     |  h_n(x) = w , min_k ∈ (0,n)(h_n([x]_k) + h_n-k^(n-k)* + m_n,n-k) ≥ -v ) = 0

uniformly in |w| ≤√(u).

At the same time, it follows from Theorem 2 in <cit.> and stochastic monotonicity w.r.t. boundary conditions of a random walk conditioned to stay positive <cit.> that

    lim_r' →∞lim sup_n →∞( min_k ∈ [r', n/2](h_n([x]_k) - k^1/2-η) ≤ 0
     | min_k ∈ [r, n/2] h_n([x]_k) > 0 ) = 0 .

To convert this into a bridge estimate, for any ϵ > 0, we can use stochastic monotonicity again to lower bound the last probability by  

    ( min_k ∈ [r', n/2](h_n([x]_k) - k^1/2-η) ≤ 0
     |  h_n([x]_n/2) = ϵ√(n),  min_k ∈ [r, n/2] h_n([x]_k) > 0 )  
    ×( h_n([x]_n/2) ≤ϵ√(n) | min_k ∈ [r, n/2] h_n([x]_k) > 0 )  .

Since standard random walk estimates show that the second probability stays uniformly bounded away from 0 for all n ≥ 1, it follow from (<ref>) that
the first probability in the last display must also go to zero in the limit when n →∞ followed by r' →∞ for any fixed ϵ > 0.

But then by monotonicity again,

    ( min_k ∈ [r', n-r'](h_n([x]_k) - ∧_n(k)^1/2-η) ≤ 0
     |  h_n(x) = w , min_k ∈ [r,n-r] h_n([x]_k) > 0  )
    ≤
    (( min_k ∈ [r', n](h_n([x]_k) - k^1/2-η) ≤ 0
     |  h_n([x]_n/2) = ϵ√(n),  min_k ∈ [r, n/2] h_n([x]_k) > 0 ) )^2 
    
    +
    ( h_n([x]_n/2) ≤ϵ√(n) |  h_n(x) = w  , min_k ∈ [r,n-r] h_n([x]_k) > 0  )  .
 
Now, similar random walk estimates show the the second probability on the right hand side tend to 0 as n →∞ followed by ϵ→ 0. Consequently, if we take n →∞ followed by r' →∞ and finally ϵ→ 0, the right hand side will vanish, yielding that 

    lim_r' →∞lim sup_n →∞( min_k ∈ [r', n-r'](h_n([x]_k) - ∧_n(k)^1/2-η) ≤ 0
     | h_n(x) = w , min_k ∈ [r,n-r] h_n([x]_k) > 0  ) = 0  ,

uniformly in |w| ≤√(u).

To handle deviations above ∧_n(k)^1/2+η, we observe that conditional on h_n(x) = w, 
the law of h_n([x]_l) is Gaussian with mean w l/n and variance l(n-l)/(2n) ≤∧_n(l)/2. Therefore for l ∈ [r, n/2],

    ( h_n([x]_l) > l^1/2+η, min_k ∈ [r,n-r] h_n([x]_k) > 0  |  h_n(x) = w) 
    ≤( h_n([x]_l) > l^1/2+η |  h_n(x) = w )
    (min_k ∈ [l,n-r] h_n([x]_k) > 0  | h_n([x]_l) = l^1/2+η, h_n(x) = w)

which is at most C ^-l^2η l^1/2+η n^-1 for C > 0 depending on u and r. Above we have used monotonicity, the Gaussian tail formula and standard estimates for a random walk conditioned to stay positive. Since 

    (min_k ∈ [r,n-r] h_n([x]_k) > 0  |  h_n(x) = w) > C' n^-1 ,

for some C' >0, we get for all l large,

    ( h_n([x]_l) > l^1/2+η | min_k ∈ [r,n-r] h_n([x]_k) > 0 ,  h_n(x) = w) ≤^-l^η .

A symmetric argument gives the same bound for the conditional probability of {h_n([x]_n-l) > l^1/2+η}. 
Invoking the union bound, we then get

    ( max_k ∈ [r', n-r'](h_n([x]_k) - ∧_n(k)^1/2+η) ≥ 0  | min_k ∈ [r,n-r] h_n([x]_k) > 0 ,  h_n(x) = w) 
    ≤∑_l=r'^n-r'^-∧_n(l)^η ,

which is at most C ^-r'^η/2 and therefore the probability on the left hand side goes to 0 as n →∞ followed by r' →∞ uniformly in |w| ≤√(u) as well.

Combining this with (<ref>) and (<ref>) and using monotonicity and the union bound, the conditional probability

    ( ∃ k ∈ [r, n-r] :  h_n([x])_k ∉_∧_n(k)^η)  
     |  h_n(x) = w  , min_k ∈ (0,n)(h_n([x]_k) + h_n-k^(n-k)* + m_n,n-k) ≥ -v ) ,

must go to 0 in the limit when n →∞ followed by r →∞. Tilting back by k ↦ m_n k/n = √(log 2) k + O(log k), the last probability is at least

    ( ∃ k ∈ [r, n-r] : h_n([x])_k ∉√(log 2)(n-k) + _∧_n(k)^2η)  
     | h_n(x) = w  , min_k ∈ (0,n)(h_n([x]_k) + h_n-k^(n-k)* - m_n-k) ≥ -v ) .

Assuming that we started with η/2 in the first place, we can then plug this back in (<ref>) and get

    (_n^[r, n-r], η(u) : h_n^* ≥ -v ) = 
    (_n(u) : h_n^* ≥ -v ) o(1)  ,

with the o(1) term tending to 0 when n →∞ followed by r →∞.

Finally, we use Proposition 1.1 in <cit.>, to bound the probability in (<ref>) by
C v(√(u))/n. Plugging this in (<ref>) and using that h_n(x) is a Gaussian with mean m_n and variance n/2, we get 

    (_n(u) : h_n^* ≥ -v ) ≤ C' 2^n v^2 n^-3/2^-m_n^2/n≤ C” v^2  ,

with all constants depending on u. We then use Markov's inequality and the union bound to write

    (_n^[r, n-r], η(u) ≠∅)  ≤ (h^*_n < -v) + (_n^[r, n-r], η(u) : h_n^* ≥ -v ) 
     ≤ (h^*_n < -v) + C” v^2 o(1)  ,

with the o(1) term as in (<ref>).
In view of Proposition <ref>, the right hand side vanishes as n →∞ followed by r →∞ and finally v →∞. This implies the same for the left hand side.



Let _0() denote the space of all boundedly finite measures on  and for u > 0, define

    A_u := { (x, ω) ∈×_0() : ω(-x + [-√(u), √(u)]) > 0 }

Then |[_n(u)]_n-r| = χ_n,r(A_u).
Denoting by χ_∞ the limiting process in (<ref>), conditional on Z̅ the intensity measure of A_u is given by

    C_♢Z̅∫_-∞^√(u) x ^2 √(log 2)x∫ 1_{ω(-x + [-√(u), √(u)]) > 0}ν(ω)  .

Setting C_u to be the integral above, which is finite as the inner integral is bounded by 1, 
it follows that χ_∞(A_u) has a law as in the right hand side of (<ref>). It is therefore sufficient to show the convergence in law of χ_n,r(A_u) to χ_∞(A_u) under the stated limits. 

To this end, it is not difficult to see that

    ∂ A_u := { (x, ω) ∈×_0() : ω(-x + {√(u), √(u)}) ≥ 1 } .

An expression for the conditional intensity measure of ∂ A_u can be written as in (<ref>). Using Fubini to exchange the order of integrals and observing that ω charges countably many points, ν-almost surely, we get that the double integral must be zero and hence that ∂ A_u is a stochastic continuity set of χ_∞.

The trouble is that A_u is not a bounded set. To remedy this, for any δ > 0, we consider the processes χ_n,r^δ and χ_∞^δ, obtained from χ_n,r and χ_∞ respectively, by restricting the first coordinate to [-δ^-1, δ^-1] and the second to finite measures on [0, 2δ^-1]. For ϵ > 0 we then define also 

    B^δ_ϵ := { (x, ω) :  |x| ≤δ^-1 ,  ω([0, 2δ^-1]) ≤ϵ^-1}

Then A_u ∩ B^δ_ϵ is a bounded stochastic continuity set under χ_∞^δ
and therefore the law of its mass under χ^δ_n,r converges to that under χ^δ_∞. It therefore remains to verify that the random variables

    χ_n,r (A_u ∖ B_ϵ^δ)
       ,     χ_∞ (A_u ∖ B_ϵ^δ)

tend to 0 in probability as ϵ→ 0 followed by δ→ 0, and in the case of 
χ_n,r (A_u ∖ B_ϵ^δ), that this limit is uniform in n ∈ [1,∞) and r ≥ 1.

Indeed, the probability that the first quantity in (<ref>) is not zero is bounded from above by

    (max_x ∈_n |h_n(x)| > δ^-1)
    + (|_n(2δ^-1/2)| > ϵ^-1)   .

But then by Proposition <ref> and Proposition <ref>, both terms must go to 0 uniformly in n and r, when ϵ→ 0 followed by δ→ 0. Since a similar argument shows that the same holds for the second quantity in (<ref>), the proof is complete.




 §.§ Soft entropic repulsion of local time trajectories
 

In this subsection we prove Proposition <ref>. The first step is to show that, with high probability, every vertex in _n has a local time trajectory which is not too low. To make this more precise, for each n ≥ 1 and k=1,…,n, let us define with η' as in the proposition,

    α_n(k):= √(log 2)(n-k) - r'_n
      ;     
    r'_n := ⌈ n^η'⌉ .
 
The statement we wish to prove first is contained in the following lemma.

 
For any η' > 0,

    lim_n →∞( ∃ x ∈_n  : ∃ k ∈ [1,n-2r'_n] , √(L_t^_n([x]_k))≤α_n(k)) = 0.
	
 

 By using the union bound first over k ∈ [1,n-2r'_n] and then over all the vertices in _k, given any fixed x ∈_n we can bound the probability in (<ref>) from above by 

    ∑_k=1^n-2r'_n 2^k(√(L_t^_n([x]_k))≤α_n(k)) .
  

To give an upper bound for the probability in (<ref>), we can use Lemma <ref> to write, for any k=1,…,n-2r'_n,

    ( √(L_t^_n([x]_k))≤α_n(k)) = ( Y_k ≤α^2_n(k))  = exp(- t^_n/k) + ∫_0^α^2_n(k) f_k(y)dy ,
 
where f_k is as in the lemma.
Since t^_n≥ (log 2)n^2 - 3/2nlog n, we have that

    exp(-t^_n/k) ≤exp( -(log 2)n + 3/2log n) = n^3/22^-n.
 
For the second term in (<ref>), since √(t^_n)≤ n and k ≥ 1, we can use (<ref>) to upper bound it by

    C n ∫_0^α^2_n(k)1/2 √(π k y)exp(-(√(y)-√(t^_n))^2/k)dy,
 
for some C>0. 
Now, let Φ(· ;μ ,σ^2) 
denote the cumulative distribution function associated with a Gaussian random variable of mean μ and variance σ^2. Since the function y ↦Φ(√(y) ;√(t^_n) ,k/2) defined for y≥ 0 is the anti-derivative of the integrand in (<ref>), the integral is at most

    Φ(α_n(k) ;√(t^_n) ,k/2)
    ≤Φ(-√(2)( √((log2)k) + r'_n/2√(k)) ;0 ,1) ,
 
for all n sufficiently large.
Then, by the standard Gaussian tail estimate Φ(-y ;0 ,1) ≤ e^-y^2/2, the latter is at most 2^-(k+r'_n), 
for all large enough n. Combining this with (<ref>) and (<ref>) gives the estimate

    ( √(L_t^_n([x]_k))≤α_n(k)) ≤ n^3/22^-n + C n 2^-(k+r'_n) .
 Using this bound, a straightforward computation shows that (<ref>) is bounded by C' n^2 2^-2r'_n for some C'>0 and all sufficiently large n, from where the lemma now immediately follows.		


We now complete the proof of Proposition <ref>. 

For each n ≥ 1 and x ∈_n, take η'<η in (<ref>), with η from (<ref>) and for α_n(k) as in (<ref>) define the event  

    A_n(x):={∀ k ∈ [1,n-2r'_n] , √(L_t^_n([x]_k))> α_n(k)} .
 Observe that A_n:=∩_x ∈_n A_n(x) is the complement of the event in Lemma <ref>.

Now, by the union bound and Markov's inequality, for any δ > 0 we have that the probability in (<ref>) is bounded from above by 

    (A_n^c) + 1/δ√(n)(| _n ∖𝒪^[r_n,n-r_n], η'|  ;  A_n) .
 Thus, by Lemma <ref>, in order to obtain (<ref>) it will suffice to show that the second term in (<ref>) tends to zero as n →∞. To this end, we first bound the expectation in (<ref>) from above by 

    ∑_x ∈_n∑_k=r_n^n-r_n( {L_t^_n(x)=0 }∩{√(L_t^_n([x]_k)) < √(log 2)(n-k)+r'_n}∩ A_n(x)) .
 Now, fix any x ∈_n and for each k' ∈ [1,n] let us abbreviate L(k'):=L_t^_n([x]_k') for simplicity. Then, by conditioning on L(k), the k-th term of the second sum can be expressed as 

    ∫_(√(log 2)(n-k)-r'_n)^2^(√(log 2)(n-k)+r'_n)^2φ_1(w)φ_2(w)(L(k) ∈ w) ,
 where 

    φ_1(w):= ( L(n) =0  , min_k'=k+1,…,n-2r'_n (√(L(k')) -α_n(k'))>0  |  L(k) = w)
 and

    φ_2(w):=( min_k'=1,…,k-1 (√(L(k'))-α_n(k'))>0 | L(k) = w).

(Note that 2r'_n < r_n for all n large, so that the minimum in (<ref>) is over a nonempty set of k'.)

By Lemma <ref>, we can bound φ_2(w)(L(k) ∈ w) from above by  

    (t^_n/w)^14( B_k' > α_n(k')  ∀  k'=1,…,k-1  |  B_0 = √(t^_n)  ,  B_k = √(w)) 
    ×( B^2_k ∈ w , B_k>0  |  B_0 = √(t^_n))  ,

where (B_s : s ∈ [0,k]) is a Brownian motion with variance 12 starting from √(t^_n) at time 0 (which we write formally as conditioning).
Now, we can rewrite the first conditional probability in (<ref>) as

    ( B_k' > (x-x') (1-k'k) + (y-y') (k'k) ,∀ k'=1,…,k-1  |  B_0 = 0 , B_k = 0)  ,
 with 

    {[ x:=√(log 2)n - r'_n;         x':=√(t^_n) ].  and {[ y:=√(log 2)(n-k) - r'_n;               y':=√(w). ].
 
Since (x-x') (1-k'/k) + (y-y') (k'/k) ≥ -2r'_n for all n large enough and any w in the domain of the integral in (<ref>), it follows from standard Brownian motion estimates (c.f. <cit.>), that this conditional probability is at most 

    C (r'_n)^2/k
 for some constant C >0 and all n sufficiently large, uniformly in k. 

On the other hand, we have that

    ( B^2_k ∈ w , B_k>0  |  B_0 = √(t^_n)) = 1/√(4π k w)exp( - (√(w)-√(t^_n))^2/k)  w ≤n^3/22^-k/√(kw)^2√(log 2)ŵ  w ,
 where ŵ:=√(w) - √(log 2) (n-k) ∈ (-r'_n,r'_n). In particular, for the range of √(w) we have in (<ref>), we can bound φ_2(w)(L(k) ∈ w) from above by 

    C(r'_n)^2 √(n)( n/(n-k)k)^322^-k^ 2√(log 2)ŵ  w ≤ C' √(n) (r'_n)^2  (∧_n(k))^-3/2 2^-k^ 2√(log 2)ŵ  w
 for some constants C, C'>0 and all n sufficiently large, uniformly in k.

We proceed in a similar fashion to treat φ_1(w).  Indeed, by first conditioning on L(n-2r'_n) and then using the Markov property, we can write φ_1(w) as 

    ∫_α^2_n(n-2r'_n)^∞ϕ_1(s)ϕ_2(s)(L(n-2r'_n) ∈ s  |  L(k)=w) ,
 
where

    ϕ_1(s):=( L(n) = 0  |  L(n-2r'_n) = s)

and

    ϕ_2(s):= ( min_k'=k+1,…,n -2r'_n (√(L(k'))-α_n(k'))>0 | L(k) = w , L(n-2r'_n)=s) .


If we write ŝ:=√(s) - 2√(log 2) r'_n > -r'_n then, by Lemma <ref>, we have that

    ϕ_1(s)=exp( - s/2r'_n) = 2^-2r'_nexp( -2√(log 2)ŝ-ŝ^2/2r'_n) .
 
On the other hand, by proceeding exactly as we did for the term φ_2(w) (which we  on the first event in (<ref>) we have L(n-2r'_n)>α_n(n-2r'_n)>0 and hence Lemma <ref> applies), we see that, for the range of √(w) under consideration in (<ref>) and all large enough n, we can bound the term  ϕ_2(s)(L(n-2r'_n) ∈ s |  L(k)=√(w)) from above (uniformly in k) by 

    C    (√(w)/√(s))^12(ŵ+r'_n)(ŝ+r'_n)/(n-2r'_n-k)1/√((n-2r'_n-k)s)exp( -(√(w)-√(s))^2/n-2r'_n-k)  s
       ≤ C'  r'_n2^-(n-2r'_n-k)/n-k (ŝ+r'_n) (√(s))^- 32^-2√(log 2)(ŵ-ŝ)  s
 for some C,C'>0. 
In particular, upon performing the change of variables s ↦ŝ in the integral in (<ref>), we obtain that φ_1(w) is at most 

    C”r'_n 2^-(n-k)/n-k^- 2√(log 2)ŵ∫_-r'_n^∞(ŝ+r'_n)/√(ŝ+2√(log 2) r'_n)^-ŝ^2/2r'_nŝ
 for some C”>0 and all n large enough, uniformly in k. Moreover, since it is straightforward to check that there exists C>0 such that

    ∫_-r'_n^∞(ŝ+r'_n)/√(ŝ+2√(log 2) r'_n)^-ŝ^2/2r'_nŝ≤ C r'_n  ,
 for all n sufficiently large, we conclude that φ_1(w)φ_2(w)(L(k) ∈ w) is at most 

    C' √(n)2^-n(r'_n)^4/n-k(∧_n(k))^- 32
 for some C' >0 and all w in the domain of the integral in (<ref>), so that (<ref>) is then bounded from above by

    C √(n) 2^-n (r'_n)^5 (∧_n(k))^- 32
 for some C > 0 and all n sufficiently large. Recalling (<ref>) and (<ref>), we see that 

    1/δ√(n)(| _n ∖𝒪^[r_n,n-r_n], η'|  ;  A_n) ≤C/δ(r'_n)^5 ∑_k=r_n^n-r_n (∧_n(k))^- 32≤3C/δ(r'_n)^5 (r_n)^-12
 for all n large enough. Therefore, by choosing η' small enough (depending on η in the definition of r_n), the rightmost term in (<ref>) tends to zero as n →∞, from which the result follows.





§ ACKNOWLEDGMENTS

The work of A.C. was supported by the Swiss National Science Foundation 200021 163170.
The work of O.L. was supported by the Israeli Science Foundation grant no. 1382/17 and by the German-Israeli Foundation for Scientific Research and Development grant no. I-2494-304.6/2017.
The work of S.S. was supported in part at the Technion by a fellowship from the Lady Davis Foundation and also by the Israeli Science Foundation grants no. 1723/14 and 765/18.
abbrv



