betaFeedback

WorksMathematics

Cover times of random recursive trees and linear preferential attachment trees

Abstract

We study the cover times of uniform random recursive trees and linear preferential attachment trees, including the negative-parameter models corresponding to random dd-ary increasing trees. We prove explicit limits in probability and expectation when the cover times are rescaled by n(log⁡n)2n (\log n)^2. In particular, for the uniform random recursive tree the cover time is close to en(log⁡n)2e n (\log n)^2 with high probability.

A recursive tree on nn vertices is a rooted tree labelled by [n]:={1,2,…,n}[n] := \{1,2,\ldots,n\} such that the root has label 1 and the labels increase along every path away from the root. We study a sequence of random recursive trees defined as follows. Fix a≥0a \ge0, or a=−1/da = -1/d for an integer d≥2d \ge2. The tree T1T_1 consists of the single vertex 1. For i≥1i \ge1, the tree Ti+1T_{i+1} is obtained from TiT_i by adding vertex i+1i+1 and attaching it to some j∈[i]j \in[i] with probability proportional to 1+adeg⁡Ti+(j)1 + a\deg_{T_i}^{+}(j), where deg⁡Ti+(j)\deg_{T_i}^{+}(j) is the out-degree (i.e., the number of children) of jj in TiT_i. We write Ta(n)T_a(n) for the law of TnT_n. For a=0a = 0, vertex i+1i+1 attaches to one of the ii earlier vertices, each of which is chosen with probability 1/i1/i; this generates the uniform random recursive tree (URRT). For a>0a > 0, this model is known as a linear preferential attachment tree.

This model can be defined also for certain a<0a < 0. The construction is well-defined for every nn exactly when a=−1/da = -1/d for an integer d≥1d \ge1. Our results extend naturally to every nondegenerate such case, namely d≥2d \ge2. For a=−1/da = -1/d, a vertex with kk children has attachment weight 1−k/d1-k/d, which vanishes when k=dk=d. Equivalently, give each vertex dd distinguishable child positions and place each new vertex in a position chosen uniformly from all those currently vacant. (This is easily seen to be equivalent to the Eden model on the dd-ary tree.) A vertex with kk children contributes d−kd-k such positions, so forgetting the selected positions and keeping only the tree structure gives exactly the attachment probabilities above. With the positions retained, this gives the random dd-ary increasing tree studied in [6 p. 513]. We exclude from this paper the case a=−1a = -1 in which the tree TnT_n is not random but is just a path on nn vertices. In this case, the cover time is of order n2n^2 and is not concentrated. This collection of models has been much studied in the literature; for background on recursive and preferential-attachment trees, see for example [23, 26, 18].

For a finite connected graph GG, let EG,v\mathbb{E}_{G,v} denote expectation for a discrete-time simple random walk (Xt)t≥0(X_t)_{t \ge0} on GG started at vv. For v∈V(G)v \in V(G), define the hitting time $\tau_v := \inf{t \ge 0 : X_t = v}v\}, and write τcov(G):=max⁡v∈V(G)τv\tau_{\mathrm{cov}}(G):=\max_{v\in V(G)}\tau_v for the cover time. Note that the distribution of the cover time depends, in general, on the starting point of the random walk. We denote the expectations of the cover and hitting times from the worst starting points by

tcov(G):=max⁡u∈V(G)EG,u[τcov(G)]t_{\mathrm{cov}}(G):=\max_{u\in V(G)}\mathbb{E}_{G,u}[\tau_{\mathrm{cov}}(G)]

and

thit(G):=max⁡u,v∈V(G)EG,u[τv].t_{\mathrm{hit}}(G):=\max_{u,v\in V(G)}\mathbb{E}_{G,u}[\tau_v].

Cover times of finite graphs have been studied extensively since at least the work of Kahn, Linial, Nisan and Saks [20]. For random graphs, there is by now a substantial literature, including results for Erdős–Rényi graphs [19, 9, 10], random regular graphs [8], random geometric graphs [11], and random graphs with given degree sequence [1]. Specializing to trees, Aldous [2] studied balanced dd-ary trees and uniform random labelled trees (Cayley trees); Brightwell and Winkler [5] showed that, among all choices of an nn-vertex tree and starting vertex, the minimum expected cover time is attained by a star started from a leaf, while Feige [15] showed that the maximum is attained by a path started from a middle vertex. More generally, Feige [14] proved that every connected nn-vertex graph has expected cover time at least (1+o(1))nlog⁡n(1+o(1))n\log n.

The purpose of this note is to find the asymptotic behaviour of τcov(Tn)\tau_{\mathrm{cov}}(T_n) for the recursive tree models defined above. Let us emphasise that there are two layers of randomness in this model: the underlying randomness of the tree TnT_n and the randomness associated with the random walk. Some of our results on the cover time will be quenched, that is conditional on the underlying tree TnT_n, and others will be annealed, that is where both tree and walk are taken to be random. Our primary interest is in the annealed behaviour, but several of the technical tools we use apply only in the quenched setting. The natural starting point for the random walk in our setting is the root of the tree.

To state our results, let us introduce WW for the principal branch of the Lambert WW function (sometimes denoted W0W_0). This is the unique continuous solution to x=W(x)eW(x)x=W(x)e^{W(x)} for x≥−1/ex\geq-1/e which satisfies W(0)=0W(0)=0. Note that WW takes values in [−1,∞)[-1,\infty), and is increasing to infinity on its domain (roughly as log⁡x\log x). We write op(1)o_p(1) for any quantity that converges to 00 in probability as n→∞n\to\infty. Our main result can now be stated.

Theorem 1. Fix a≥0a\geq0, or a=−1/da=-1/d for an integer d≥2d\geq2. For each nn, let Tn∼Ta(n)T_n\sim\mathcal{T}_a(n), and let τcov(Tn)\tau_{\mathrm{cov}}(T_n) be the cover time of a simple random walk on TnT_n started at the root. Then, as n→∞n\to\infty,

τcov(Tn)=(1+op(1))γ2(1+a)2n(log⁡n)2.\tau_{\mathrm{cov}}(T_n)=(1+o_p(1))\frac{\gamma^2}{(1+a)^2}n(\log n)^2.

where

γ=γ(a)=eexp⁡(W(a2e))1+2W(a2e).\gamma=\gamma(a)=\sqrt{e}\exp\left(W\left(\frac{a}{2\sqrt{e}}\right)\right)\sqrt{1+2W\left(\frac{a}{2\sqrt{e}}\right)}.

In particular we have γ(0)=e\gamma(0)=\sqrt{e} and so for the URRT,

τcov(Tn)=(e+op(1))n(log⁡n)2.\tau_{\mathrm{cov}}(T_n)=(e+o_p(1))n(\log n)^2.

See Figure 1 for an illustration of the relevant constants as functions of aa. Note that for a<0a<0 not of the form −d−1-d^{-1} we do not have any model realizing the specified constants. Interpolating between dd-ary graphs, e.g. with random degrees would be one option, though we do not pursue this here.

Figure 1. The functions γ(a)\gamma(a) and (γ(a)/(1+a))2(\gamma(a)/(1+a))^2 from Theorem 1.

Corollary 2. Under the assumptions of Theorem 1, as n→∞n \to\infty,

E[tcov(Tn)]=(1+o(1))γ2(1+a)2n(log⁡n)2.\mathbb{E}\left[t_{\mathrm{cov}}(T_n)\right] = (1+o(1))\frac{\gamma^2}{(1+a)^2}n(\log n)^2.

In particular for the URRT,

E[tcov(Tn)]=(e+o(1))n(log⁡n)2.\mathbb{E}\left[t_{\mathrm{cov}}(T_n)\right] = (e+o(1))n(\log n)^2.

Here the expectation is over TnT_n.

Before proceeding, let us briefly outline the idea behind Theorem 1. We start with a heuristic analysis. For clarity, we focus on the URRT at first. The proof is based on the well-known connection between cover times and Gaussian free fields, see [13, 12] and Theorem 5 below. To apply this we need to estimate the maximum of a GFF on TnT_n. Now, by the Sudakov–Fernique [24, 16] inequality, the expected maximum is at most the expected maximum of independent Gaussian variables indexed by the vertices, with each variable’s variance equal to the variance of the GFF value at that vertex. The number of vertices in TnT_n at level slog⁡ns\log n is known [17] to be ns−slog⁡(s)+o(1)n^{s-s\log(s)+o(1)}, and the maximum of that many i.i.d. N(0,slog⁡n)N(0,s\log n) variables is concentrated around slog⁡n⋅2(s−slog⁡s)log⁡n=s2(1−log⁡s)log⁡n\sqrt{s\log n}\cdot\sqrt{2(s-s\log s)\log n}=s\sqrt{2(1-\log s)\log n}. This is maximized at s=es=\sqrt{e}, and so the maximum of the GFF is at most (e+op(1))log⁡n(\sqrt{e}+o_p(1))\log n, heuristically attained at some vertices of height elog⁡n\sqrt{e}\log n. It is possible to get a matching lower bound (which we do). Typically two vertices of TnT_n have a nearest common ancestor which is quite close to the root. This implies that the values of the GFF are not too far from independent.

Our actual proof follows a different path: we construct the tree TnT_n simultaneously with the GFF on it, and observe that the maximum of the GFF can be viewed as the maximal displacement of a certain branching random walk. This in turn can be studied through the general associated theory developed by Biggins [3, 4].

Background

Properties of linear preferential attachment trees

For a tree TT, we write height⁡(T)\operatorname{height}(T) for the maximum graph distance from the root to a vertex of TT and diam⁡(T)\operatorname{diam}(T) for the diameter of TT (that is, the largest graph distance between any two of its vertices). Then

height⁡(T)≤diam⁡(T)≤2⋅height⁡(T).\operatorname{height}(T) \le\operatorname{diam}(T) \le2\cdot\operatorname{height}(T).

For preferential attachment trees, the first-order height asymptotic was proved for a≥0a \ge0 by Pittel [23, Theorem 1], and for a=−1/da=-1/d by Broutin et al. [6, Theorem 3]. We use below the following result giving convergence in L1L^1.

Theorem 3 [18], Theorem 13.19 and Example 13.9). Suppose that a≥0a \ge0, or that a=−1/da=-1/d for an integer d≥2d \ge2. Then

height⁡(Tn)log⁡n⟶1(1+a)ξˉin L1,\frac{\operatorname{height}(T_n)}{\log n} \longrightarrow\frac{1}{(1+a)\bar{\xi}} \quad\text{in } L^1,

where ξˉ\bar{\xi} is the unique root in (0,1)(0,1) of the equation aξˉ+log⁡ξˉ+1=0a\bar{\xi}+\log\bar{\xi}+1=0.

Continuous time construction

A well-known tool for studying random recursive trees and preferential attachment trees is their continuous-time construction as Crump–Mode–Jagers branching processes; see Pittel [23] for a≥0a \ge0, and Holmgren and Janson [18] for the dd-ary case. We recap this construction for completeness. Throughout, for λ≥0\lambda\ge0, let Exp⁡(λ)\operatorname{Exp}(\lambda) denote the exponential distribution with rate λ\lambda. (Here we take Exp⁡(0)=∞\operatorname{Exp}(0)=\infty with probability 11.) We embed the sequence (Tn)n≥1(T_n)_{n \ge1} in continuous time as follows. Consider a continuous-time pure birth process that generates a sequence of growing trees. For t≥0t \ge0, denote by T(t)T(t) the tree at time tt. The process starts at t=0t=0 with T(0)T(0) consisting of a single root vertex, labelled 1. Each vertex jj in the tree is endowed with an independent exponential clock. At time tt, the rate of its clock is 1+a⋅deg⁡T(t)+(j)1+a\cdot\deg^+_{T(t)}(j). When the clock belonging to vertex jj rings, a new vertex (with the next free label) is created, and attached to jj as a child. The rate of jj's clock is then updated, and an independent clock is started for the new vertex. Let βk\beta_k be the random time at which vertex kk first appears in the tree.

Claim 4. Set Ei:=βi+1−βiE_i:=\beta_{i+1}-\beta_i for i≥1i \ge1. Then the random variables (Ei)i≥1(E_i)_{i \ge1} are independent, with Ei∼Exp⁡((1+a)i−a)E_i \sim\operatorname{Exp}((1+a)i-a). Moreover, the embedded chain (T(βn))n≥1(T(\beta_n))_{n \ge1} has the same joint law as (Tn)n≥1(T_n)_{n \ge1}.

Proof. Fix i≥1i \ge1 and consider the process at time βi\beta_i, when T(βi)T(\beta_i) has vertex set [i][i]. Conditional on the evolution up to this time, the times from βi\beta_i until the clocks next ring are, by the memoryless property, independent exponential random variables with respective rates 1+adeg⁡T(βi)+(v)1+a\deg^+_{T(\beta_i)}(v), for v∈[i]v \in[i]. Since the out-degrees in T(βi)T(\beta_i) sum to i−1i-1, the total clock rate is (1+a)i−a(1+a)i-a. Hence their minimum Ei=βi+1−βiE_i=\beta_{i+1}-\beta_i has distribution Exp⁡((1+a)i−a)\operatorname{Exp}((1+a)i-a), while vertex i+1i+1 attaches to v∈[i]v \in[i] with probability proportional to 1+adeg⁡T(βi)+(v)1+a\deg^+_{T(\beta_i)}(v). Since the total clock rate depends only on ii, the conditional law of EiE_i does not depend on the evolution up to time βi\beta_i. In particular, EiE_i is independent of E1,…,Ei−1E_1,\ldots,E_{i-1}, so the variables (Ei)i≥1(E_i)_{i \ge1} are independent. Since T(β1)=T1T(\beta_1)=T_1, induction shows that the embedded chain has the same joint law as (Tn)n≥1(T_n)_{n \ge1}. Finally, β1=0\beta_1=0, so βn=∑i=1n−1Ei\beta_n=\sum_{i=1}^{n-1}E_i.

Gaussian free fields on trees

The Gaussian free field (GFF) on graphs has well known connections to random walks and cover times. See e.g. [21] for an introduction to discrete GFFs. The GFF on a tree TT, pinned at a vertex v0v_0, has a particularly simple description. Root TT at v0v_0 and set ηv0=0\eta_{v_0}=0. Then, recursively, whenever vv is the parent of uu in the tree, let ηu−ηv\eta_u-\eta_v have a standard normal distribution, with these increments independent over the edges of TT.

For general finite graphs, Ding, Lee and Peres [13] proved that the maximal expected cover time over starting vertices is, up to universal constant factors, the number of edges times the square of the expected maximum of the GFF. We use the following sharper tree-specific concentration estimates of Ding [12]. Ding states them for continuous-time random walks, but notes after his Corollary 1.3 that they also hold in discrete time.

Theorem 5 [12], Theorem 1.2). There exist universal constants C,c>0C,c>0 such that the following holds. Let T=(V,E)T=(V,E) be a tree with at least two vertices and let v0∈Vv_0\in V. Let {ηv}v∈V\{\eta_v\}_{v\in V} be the GFF on TT pinned at v0v_0. Then, for the random walk started at v0v_0 and every λ≥1\lambda\ge1,

P(∣τcov(T)−∣E∣E([sup⁡v∈Vηv]2)∣≥λ∣E∣diam⁡(T)E[sup⁡v∈Vηv])≤Ce−cλ.\mathbb{P}\left(\left|\tau_{\mathrm{cov}}(T)-|E|\mathbb{E}\left(\left[\sup_{v\in V}\eta_v\right]^2\right)\right|\ge\lambda|E|\sqrt{\operatorname{diam}(T)\mathbb{E}\left[\sup_{v\in V}\eta_v\right]}\right)\le Ce^{-c\lambda}.

Corollary 6 [12], Corollary 1.3). There exist universal constants C,c>0C,c>0 such that, for every finite rooted tree TT with at least two vertices and every λ≥0\lambda\ge0,

P(∣τcov(T)−tcov(T)∣≥λtcov(T)thit(T))≤Ce−cλ.\mathbb{P}\left(\left|\tau_{\mathrm{cov}}(T)-t_{\mathrm{cov}}(T)\right|\ge\lambda\sqrt{t_{\mathrm{cov}}(T)t_{\mathrm{hit}}(T)}\right)\le Ce^{-c\lambda}.

Here the random walk is started at the root.

Proofs

Branching random walks

We augment the continuous-time tree-growth process by assigning a spatial position to each vertex, thereby constructing the GFF on the tree at the same time. This defines a branching random walk (BRW). The root (vertex 1) is located at position η1=0\eta_1=0. Then, recursively, when a new vertex jj is born to a parent ii at time βj\beta_j, its position is set to be ηj=ηi+Nj\eta_j=\eta_i+N_j, where the {Nj}j≥2\{N_j\}_{j\ge2} are independent and identically distributed standard normal random variables. The sequence (Nj)j≥2(N_j)_{j\ge2} is independent of the tree-growth process. The joint process — comprising the tree’s evolution and the assignment of spatial positions — is a specific instance of a general continuous-time branching random walk model which has been studied extensively, including in seminal works of Biggins [3, 4]. Evidently, the set of positions {ηi}i∈[n]\{\eta_i\}_{i\in[n]} has the same law as the Gaussian free field on TnT_n pinned at vertex 1. Therefore, the maximum of the GFF corresponds to the rightmost position of a particle in this BRW.

Note that if instead of Gaussian displacements we take a deterministic +1+1 displacement between a particle and its parent, the position of a particle is the height of the corresponding vertex in the tree. This has been used in the past to study the height of the tree (see, e.g., [18]).

In order to relate our statements to the notation and terminology used by Biggins and Pittel, we let the maximal possible number of children of a vertex be denoted by

Ka:={∞,a≥0,d,a=−1/d.K_a:=\begin{cases} \infty, & a\ge0,\\ d, & a=-1/d. \end{cases}

The offspring point process for a vertex gives the spatial displacement and relative birth times of its children. In our case, this is

Z={(Nk,Sk)}k=1KaZ=\{(N_k,S_k)\}_{k=1}^{K_a}

where {Nk}1≤k≤Ka\{N_k\}_{1\le k\le K_a} are independent standard normal random variables. The birth times SkS_k are defined in terms of {Xk}1≤k≤Ka\{X_k\}_{1\le k\le K_a} which are independent exponential random variables with Xk∼Exp⁡(1+(k−1)a)X_k\sim\operatorname{Exp}(1+(k-1)a), and Sk=∑i=1kXiS_k=\sum_{i=1}^{k}X_i. For t≥0t\ge0 and x∈Rx\in\mathbb{R}, let Pt(x)P_t(x) be the number of particles present at time tt whose positions are at least xx. The rightmost particle is given by

Rt=sup⁡{x∈R:Pt(x)≥1}.R_t=\sup\{x\in\mathbb{R}:P_t(x)\ge1\}.

The analysis of the branching random walk relies on the two-dimensional Laplace transform of the intensity measure of ZZ on the domain R×(a,∞)\mathbb{R} \times(a,\infty), which is defined by

m(θ,ϕ):=E[∑k=1Kae−θNk−ϕSk].m(\theta,\phi) := \mathbb{E}\left[\sum_{k=1}^{K_a} e^{-\theta N_k-\phi S_k}\right].

Following Biggins, define for this BRW,

α(θ)=inf⁡{ϕ:m(θ,ϕ)≤1}andα∗(x)=inf⁡θ<0{xθ+α(θ)}.\alpha(\theta) = \inf\{\phi: m(\theta,\phi) \le1\} \qquad\text{and}\qquad \alpha^*(x) = \inf_{\theta<0}\{x\theta+ \alpha(\theta)\}.

Set γ0=inf⁡{x:α∗(x)<0}\gamma_0 = \inf\{x : \alpha^*(x) < 0\}. The following consequence of Biggins [4 Corollary 2.2] shows that Rt/tR_t/t converges almost surely to γ0\gamma_0. Biggins’ corollary is stated for a more general model; in Appendix § 5 we show how our process fits that model and verify the required hypotheses.

Proposition 7 (Right-edge theorem). For the branching random walk constructed above, we have

Rtt→γ0\frac{R_t}{t} \to\gamma_0

almost surely as t→∞t \to\infty.

Before proceeding, let us give some intuition for this result, which may seem somewhat obscure to readers not familiar with large deviations for branching random walks. For a vertex vv, let p(v)p(v) denote its position. Write AtA_t for the set of vertices born by time tt, and define

wt(θ)=E[∑v∈Ate−θp(v)].w_t(\theta) = \mathbb{E}\left[\sum_{v\in A_t} e^{-\theta p(v)}\right].

It is generally the case for branching random walks that such quantities grow (or decay) exponentially with tt. Let us posit that this occurs at some rate α(θ)\alpha(\theta), i.e.

wt(θ)≈eα(θ)t.w_t(\theta) \approx e^{\alpha(\theta)t}.

Note that the root is at position 0. Condition on the times of birth and relative positions of the offspring of the root individual, and note that the kkth child of the root, which is born at time SkS_k, is the root of a new, equally distributed branching process. The time and spatial shift from the root imply this sub-process contributes wt−Sk(θ)w_{t-S_k}(\theta) on average, shifted by e−θNke^{-\theta N_k} to account for its starting position. We obtain the equation

wt(θ)=1+E[∑k≥1wt−Sk(θ)e−θNk1{Sk≤t}].w_t(\theta) = 1 + \mathbb{E}\left[\sum_{k\ge1} w_{t-S_k}(\theta)e^{-\theta N_k}\mathbf{1}_{\{S_k\le t\}}\right].

Using the approximate exponential growth, we then get

eα(θ)t≈E[∑k≥1eα(θ)(t−Sk)e−θNk].e^{\alpha(\theta)t} \approx\mathbb{E}\left[\sum_{k\ge1} e^{\alpha(\theta)(t-S_k)}e^{-\theta N_k}\right].

for large tt. Cancelling a factor of eα(θ)te^{\alpha(\theta)t} from both sides yields that α(θ)\alpha(\theta) should be chosen so that

1=E[∑k≥1e−α(θ)Sk−θNk]=m(θ,α(θ)).1 = \mathbb{E}\left[\sum_{k\ge1}e^{-\alpha(\theta)S_k-\theta N_k}\right] = m(\theta,\alpha(\theta)).

This gives rise to the definition of α(θ)\alpha(\theta) given above.

Now consider Pt(tx)=∣{v∈At:p(v)≥tx}∣≈∣{v∈At:p(v)≈tx}∣P_t(tx) = |\{v \in A_t : p(v) \ge tx\}| \approx|\{v \in A_t : p(v) \approx tx\}|. Then, for θ<0\theta< 0,

E[Pt(tx)e−θtx]≲wt(θ)≈eα(θ)t\mathbb{E}\left[P_t(tx)e^{-\theta tx}\right] \lesssim w_t(\theta) \approx e^{\alpha(\theta)t}

and so

E[Pt(tx)]≲exp⁡((α(θ)+θx)t).\mathbb{E}[P_t(tx)] \lesssim\exp\left((\alpha(\theta)+\theta x)t\right).

Since this holds for all θ<0\theta< 0, we may optimise to get a tighter bound on the right-hand side by taking α∗(x)=inf⁡θ<0(α(θ)+θx)\alpha^*(x) = \inf_{\theta<0}(\alpha(\theta) + \theta x). A large deviations argument shows that this, in fact, captures the correct exponential rate, so that indeed

E[Pt(tx)]≈eα∗(x)t.\mathbb{E}\left[P_t(tx)\right] \approx e^{\alpha^*(x)t}.

The right edge of the population at large time tt is then to be found approximately at the point txtx where xx is such that α∗(x)=0\alpha^*(x) = 0 (i.e. the point where E[Pt(tx)]\mathbb{E}\left[P_t(tx)\right] tips from growing exponentially to decaying exponentially). This is precisely γ0\gamma_0.

We now compute these quantities explicitly in our setting: mm in Claim 8, α\alpha and α∗\alpha^* in Corollary 9, and finally γ0\gamma_0 in Claim 10.

Claim 8. For θ∈R\theta\in\mathbb{R} and ϕ>a\phi> a,

m(θ,ϕ)=1ϕ−a⋅eθ2/2.m(\theta,\phi) = \frac{1}{\phi-a}\cdot e^{\theta^2/2}.

Proof. By linearity of expectation and by independence,

m(θ,ϕ)=∑k=1Ka(E[e−θNk]⋅E[e−ϕSk]).m(\theta,\phi) = \sum_{k=1}^{K_a}\left(\mathbb{E}\left[e^{-\theta N_k}\right]\cdot\mathbb{E}\left[e^{-\phi S_k}\right]\right).

The law of NkN_k does not depend on kk, and E[e−θNk]=exp⁡(θ2/2)\mathbb{E}\left[e^{-\theta N_k}\right] = \exp(\theta^2/2). The remaining identity

∑k=1KaE[e−ϕSk]=1ϕ−a\sum_{k=1}^{K_a}\mathbb{E}\left[e^{-\phi S_k}\right] = \frac{1}{\phi-a}

is implicit, when a≥0a \geq0, in [23 proof of Theorem 1, p. 340]; for completeness, and to include the case a=−1/da=-1/d, we derive it explicitly here. If a=0a = 0, then Xi∼Exp⁡(1)X_i \sim\operatorname{Exp}(1) for every ii, so

γk:=E[e−ϕSk]=∏i=1kE[e−ϕXi]=(1+ϕ)−k.\gamma_k := \mathbb{E}\left[e^{-\phi S_k}\right] = \prod_{i=1}^{k}\mathbb{E}\left[e^{-\phi X_i}\right] = (1+\phi)^{-k}.

Therefore

∑k=1∞γk=∑k=1∞(1+ϕ)−k=1ϕ,\sum_{k=1}^{\infty}\gamma_k = \sum_{k=1}^{\infty}(1+\phi)^{-k} = \frac{1}{\phi},

which is the required formula when a=0a = 0.

Assume henceforth that a≠0a \ne0. Letting (x)(k)=∏i=0k−1(x+i)(x)^{(k)} = \prod_{i=0}^{k-1}(x+i) and defining A=1/aA = 1/a and B=(1+ϕ)/aB = (1+\phi)/a, we have

γk:=E[e−ϕSk]=∏i=1kE[e−ϕXi]=∏i=1k1+(i−1)a1+(i−1)a+ϕ=∏i=0k−1A+iB+i=A(k)B(k).\gamma_k := \mathbb{E}\left[e^{-\phi S_k}\right] = \prod_{i=1}^{k}\mathbb{E}\left[e^{-\phi X_i}\right] = \prod_{i=1}^{k}\frac{1+(i-1)a}{1+(i-1)a+\phi} = \prod_{i=0}^{k-1}\frac{A+i}{B+i} = \frac{A^{(k)}}{B^{(k)}}.

If a>0a > 0, then Ka=∞K_a = \infty and B−A−1=(ϕ−a)/a>0B-A-1 = (\phi-a)/a > 0, so Gauss’ hypergeometric summation formula gives

∑k=0∞A(k)B(k)=B−1B−A−1.\sum_{k=0}^{\infty}\frac{A^{(k)}}{B^{(k)}} = \frac{B-1}{B-A-1}.

If a=−1/da=-1/d, then A=−dA=-d and Ka=dK_a=d. Moreover, B(k)≠0B^{(k)} \ne0 for 0≤k≤d0 \leq k \leq d, since ϕ>−1/d\phi>-1/d. The terminating form of Gauss’ formula therefore gives

∑k=0dA(k)B(k)=B−1B−A−1.\sum_{k=0}^{d}\frac{A^{(k)}}{B^{(k)}} = \frac{B-1}{B-A-1}.

Thus, in either case,

∑k=0KaA(k)B(k)=B−1B−A−1.\sum_{k=0}^{K_a} \frac{A^{(k)}}{B^{(k)}} = \frac{B-1}{B-A-1}.

Subtracting the k=0k=0 term, which is equal to 1, we obtain

∑k=1Kaγk=B−1B−A−1−1=AB−A−1=1ϕ−a,\sum_{k=1}^{K_a} \gamma_k = \frac{B-1}{B-A-1}-1 = \frac{A}{B-A-1} = \frac{1}{\phi-a},

and the statement follows. □

Corollary 9. For all θ∈R\theta\in\mathbb{R}, α(θ)=a+eθ2/2\alpha(\theta)=a+e^{\theta^2/2}, and for all x>0x>0,

α∗(x)=a+exp⁡(12W(x2))−xW(x2)=a+(1−W(x2))exp⁡(12W(x2)),\alpha^*(x)=a+\exp\left(\frac{1}{2}W(x^2)\right)-x\sqrt{W(x^2)}=a+\left(1-W(x^2)\right)\exp\left(\frac{1}{2}W(x^2)\right),

where WW is the principal branch of the Lambert WW function.

Proof. By Claim 8, for fixed θ\theta and ϕ>a\phi>a we have m(θ,ϕ)=eθ2/2/(ϕ−a)m(\theta,\phi)=e^{\theta^2/2}/(\phi-a), which is strictly decreasing in ϕ\phi with m(θ,ϕ)→0m(\theta,\phi)\to0 as ϕ→∞\phi\to\infty and m(θ,ϕ)→∞m(\theta,\phi)\to\infty as ϕ→a\phi\to a. Thus m(θ,ϕ)≤1m(\theta,\phi)\le1 iff ϕ−a≥eθ2/2\phi-a\ge e^{\theta^2/2}, and the infimum is attained at equality, giving α(θ)=a+eθ2/2\alpha(\theta)=a+e^{\theta^2/2}.

Fix x>0x>0 and consider f(θ)=xθ+α(θ)=xθ+a+eθ2/2f(\theta)=x\theta+\alpha(\theta)=x\theta+a+e^{\theta^2/2} for θ<0\theta<0. The function ff is strictly convex since f′′(θ)=(1+θ2)eθ2/2>0f^{\prime\prime}(\theta)=(1+\theta^2)e^{\theta^2/2}>0, so the minimum over (−∞,0)(-\infty,0) is attained at the unique point θ∗\theta_* where f′(θ∗)=0f^\prime(\theta_*)=0. We find that point:

0=f′(θ∗)=x+θ∗eθ∗2/2⟺θ∗eθ∗2/2=−x.0=f^\prime(\theta_*)=x+\theta_*e^{\theta_*^2/2}\quad\Longleftrightarrow\quad\theta_*e^{\theta_*^2/2}=-x.

Let y=θ∗2>0y=\theta_*^2>0. Squaring gives x2=yeyx^2=ye^y, hence y=W(x2)y=W(x^2). From x=−θ∗ey/2x=-\theta_*e^{y/2} and θ∗<0\theta_*<0 we get ey/2=x/ye^{y/2}=x/\sqrt{y}. Evaluating ff at the minimiser,

α∗(x)=a+ey/2−xy=a+ey/2−yey/2=a+(1−y)ey/2.\alpha^*(x)=a+e^{y/2}-x\sqrt{y}=a+e^{y/2}-ye^{y/2}=a+(1-y)e^{y/2}.

Claim 10. Let w=W(a/(2e))w=W(a/(2\sqrt{e})). Then

γ0=e⋅exp⁡(w)⋅1+2w.\gamma_0=\sqrt{e}\cdot\exp(w)\cdot\sqrt{1+2w}.

In particular, γ0=γ(a)\gamma_0=\gamma(a).

Proof. Writing y=W(x2)y=W(x^2), we know by Corollary 9 that α∗(x)=a+(1−y)ey/2\alpha^*(x)=a+(1-y)e^{y/2}. Thus we have α∗(x)<0\alpha^*(x)<0 if and only if (y−1)ey/2>a(y-1)e^{y/2}>a. Now, α∗(x)\alpha^*(x) is strictly decreasing in yy on (−1,∞)(-1,\infty). Thus there is a unique y∗y_* solving the equation (y−1)ey/2=a(y-1)e^{y/2}=a. By the previous equivalence, α∗(γ0)=0\alpha^*(\gamma_0)=0 if and only if y∗=W(γ02)y_*=W(\gamma_0^2). Writing y∗=2z+1y_*=2z+1, we have zez=a/(2e)ze^z=a/(2\sqrt{e}), so z=wz=w, and y∗=1+2wy_*=1+2w. This implies W(γ02)=1+2wW(\gamma_0^2)=1+2w, hence γ02=(1+2w)e1+2w\gamma_0^2=(1+2w)e^{1+2w}, from which the statement follows. □

By Proposition 7 and Claim 10, we obtain the following.

Proposition 11. The position of the rightmost particle satisfies Rt/t→γ(a)R_t/t\to\gamma(a) almost surely, with γ(a)\gamma(a) as in Theorem 1.

Proof. By Proposition 7,

Rtt⟶γ0\frac{R_t}{t}\longrightarrow\gamma_0

almost surely. Finally, by Claim 10 we have γ0=γ(a)\gamma_0=\gamma(a), so Rt/t→γ(a)R_t/t\to\gamma(a) almost surely. □

We will need the following law of large numbers for βn\beta_n (the time at which the growing tree first has nn vertices). This lets us apply Proposition 11 at the random time t=βnt=\beta_n.

Lemma 12. As n→∞n \to\infty,

βnlog⁡n→11+a\frac{\beta_n}{\log n} \to\frac{1}{1+a}

almost surely.

We follow the proof of [23 Theorem 1]: First and second moments give concentration of βn\beta_n near log⁡n1+a\frac{\log n}{1+a}; monotonicity and restriction to a lacunary sequence strengthen to a.s. convergence.

Proof. By Claim 4, βn=∑k=1n−1Ek\beta_n=\sum_{k=1}^{n-1}E_k with independent Ek∼Exp⁡((1+a)k−a)E_k\sim\operatorname{Exp}((1+a)k-a). Thus,

E[βn]=∑k=1n−1E[Ek]=11+a∑k=1n−11k−a1+a=11+alog⁡n+O(1),\mathbb{E}[\beta_n]=\sum_{k=1}^{n-1}\mathbb{E}[E_k]=\frac{1}{1+a}\sum_{k=1}^{n-1}\frac{1}{k-\frac{a}{1+a}}=\frac{1}{1+a}\log n+O(1),

and

var⁡(βn)=∑k=1n−1var⁡(Ek)=∑k=1n−11((1+a)k−a)2=O(1).\operatorname{var}(\beta_n)=\sum_{k=1}^{n-1}\operatorname{var}(E_k)=\sum_{k=1}^{n-1}\frac{1}{((1+a)k-a)^2}=O(1).

Let nm=2mn_m=2^m. For any fixed ε>0\varepsilon>0, Chebyshev gives

P(∣βnm−E[βnm]∣>εlog⁡nm)≤var⁡(βnm)ε2log⁡2nm≤Cε2m2,\mathbb{P}\left(\left|\beta_{n_m}-\mathbb{E}[\beta_{n_m}]\right|>\varepsilon\log n_m\right)\leq\frac{\operatorname{var}(\beta_{n_m})}{\varepsilon^2\log^2 n_m}\leq\frac{C}{\varepsilon^2m^2},

for some constant C<∞C<\infty. Since ∑m≥1C/(ε2m2)<∞\sum_{m\geq1}C/(\varepsilon^2m^2)<\infty, the Borel–Cantelli lemma implies β2m/(mlog⁡2)→1/(1+a)\beta_{2^m}/(m\log2)\to1/(1+a) almost surely. For 2m≤n<2m+12^m\leq n<2^{m+1} we have β2m≤βn≤β2m+1\beta_{2^m}\leq\beta_n\leq\beta_{2^{m+1}} and mlog⁡2≤log⁡n≤(m+1)log⁡2m\log2\leq\log n\leq(m+1)\log2, hence

β2m(m+1)log⁡2≤βnlog⁡n≤β2m+1mlog⁡2,\frac{\beta_{2^m}}{(m+1)\log2}\leq\frac{\beta_n}{\log n}\leq\frac{\beta_{2^{m+1}}}{m\log2},

and both bounds tend to 1/(1+a)1/(1+a) almost surely.

The next statement follows easily.

Corollary 13. The GFF on the growing tree satisfies

sup⁡v∈V(Tn)ηvlog⁡n→γ1+a\frac{\sup_{v\in V(T_n)}\eta_v}{\log n}\to\frac{\gamma}{1+a}

almost surely as n→∞n\to\infty.

Proof. By Proposition 11, Rt/t→γR_t/t\to\gamma almost surely. By Lemma 12, βn/log⁡n→1/(1+a)\beta_n/\log n\to1/(1+a) almost surely. On the intersection of these probability-1 events,

sup⁡v∈V(Tn)ηvlog⁡n=Rβnlog⁡n=(Rβnβn)(βnlog⁡n)→γ⋅11+a.\frac{\sup_{v\in V(T_n)}\eta_v}{\log n}=\frac{R_{\beta_n}}{\log n}=\left(\frac{R_{\beta_n}}{\beta_n}\right)\left(\frac{\beta_n}{\log n}\right)\to\gamma\cdot\frac{1}{1+a}.

From annealed to quenched

Corollary 13 establishes that the maximum of the GFF converges on rescaling when both the tree and the GFF are treated as random. In order to apply Ding’s results from § 1.3, however, we need the analogous result conditioned on the tree.

The Borell inequality below (also discovered by Tsirelson, Ibragimov, and Sudakov) appears, for example, in [25 Lemma 4].

Lemma 14 (Borell inequality). Let (Xi)i∈I(X_i)_{i\in I} be a finite centred Gaussian process, and set

M:=sup⁡i∈IXiandθ:=sup⁡i∈Ivar⁡(Xi).M := \sup_{i\in I} X_i \qquad\text{and}\qquad\theta:= \sup_{i\in I} \sqrt{\operatorname{var}(X_i)}.

Suppose that θ>0\theta> 0, and let w∈Rw \in\mathbb{R} satisfy P(M≥w)≤1/2\mathbb{P}(M \ge w) \le1/2. Then, for every s≥0s \ge0,

P(M≥w+s)≤P(Y≥s/θ),\mathbb{P}(M \ge w+s) \le\mathbb{P}(Y \ge s/\theta),

where YY is a standard normal random variable.

Lemma 15. Let TT be a rooted tree with at least three vertices and height hh, let (ηv)v∈V(T)(\eta_v)_{v\in V(T)} be the pinned GFF on TT, and set

M(T):=sup⁡v∈V(T)ηv.M(T) := \sup_{v\in V(T)} \eta_v.

Let mTm_T be a median of M(T)M(T). Then for every s≥0s \ge0,

P(M(T)≥mT+s)≤P(Y≥s/h),\mathbb{P}(M(T) \ge m_T+s) \le\mathbb{P}(Y \ge s/\sqrt{h}),

where YY is a standard normal random variable. In particular, there is a universal constant C<∞C < \infty such that

E[(M(T)−mT)+]≤Ch.\mathbb{E}\left[(M(T)-m_T)^+\right] \le C\sqrt{h}.

Proof. Since TT has at least three vertices, P(M(T)=0)<1/2\mathbb{P}(M(T)=0)<1/2 (consider any two distinct non-root vertices), while M(T)M(T) has no atoms on (0,∞)(0,\infty). Hence the median mTm_T is well defined, positive and P(M(T)≥mT)=1/2\mathbb{P}(M(T)\ge m_T)=1/2.

The process (ηv)v∈V(T)(\eta_v)_{v\in V(T)} is a discrete centred Gaussian process. For each vv,

var⁡(ηv)=d(ρ,v)≤h,\operatorname{var}(\eta_v)=d(\rho,v)\le h,

where d(ρ,v)d(\rho,v) is the graph distance from the root. Hence,

sup⁡v∈V(T)var⁡(ηv)≤h.\sup_{v\in V(T)}\sqrt{\operatorname{var}(\eta_v)}\le\sqrt{h}.

By Lemma 14, applied to the Gaussian process (ηv)v∈V(T)(\eta_v)_{v\in V(T)},

P(M(T)≥mT+s)≤P(Y≥s/h)\mathbb{P}(M(T)\ge m_T+s)\le\mathbb{P}(Y\ge s/\sqrt{h})

for every s≥0s\ge0. Integrating this bound yields

E[(M(T)−mT)+]=∫0∞P(M(T)≥mT+s) ds≤h∫0∞P(Y≥u) du≤Ch\mathbb{E}\left[(M(T)-m_T)^+\right] =\int_0^\infty\mathbb{P}(M(T)\ge m_T+s)\,ds \le\sqrt{h}\int_0^\infty\mathbb{P}(Y\ge u)\,du \le C\sqrt{h}

for a universal constant CC. □

For brevity, set

κ=κ(a):=γ(a)1+a.\kappa=\kappa(a):=\frac{\gamma(a)}{1+a}.

The next lemma is a quenched concentration result for the maximum of the GFF on TnT_n.

Lemma 16. There exists C=C(a)<∞C=C(a)<\infty such that, for every fixed ε∈(0,1/2)\varepsilon\in(0,1/2), with probability tending to 11 as n→∞n\to\infty, the tree TnT_n satisfies

height⁡(Tn)≤Clog⁡n,\operatorname{height}(T_n)\le C\log n,

and the maximum of the GFF satisfies

P(∣M(Tn)−κlog⁡n∣>εlog⁡n∣Tn)≤ε.\mathbb{P}\left(\left|M(T_n)-\kappa\log n\right|>\varepsilon\log n\mid T_n\right)\le\varepsilon.

Proof. By Theorem 3, there exists C=C(a)C=C(a) such that

P(height⁡(Tn)≤Clog⁡n)→1.\mathbb{P}\left(\operatorname{height}(T_n)\le C\log n\right)\to1.

Let

qn(T):=P(∣M(T)−κlog⁡n∣>εlog⁡n).q_n(T):=\mathbb{P}\left(\left|M(T)-\kappa\log n\right|>\varepsilon\log n\right).

Under the joint law of (Tn,η)(T_n,\eta), Corollary 13 implies

P(∣M(Tn)−κlog⁡n∣>εlog⁡n)→0.\mathbb{P}\left(\left|M(T_n)-\kappa\log n\right|>\varepsilon\log n\right)\to0.

By definition,

qn(Tn)=P(∣M(Tn)−κlog⁡n∣>εlog⁡n∣Tn).q_n(T_n)=\mathbb{P}\left(\left|M(T_n)-\kappa\log n\right|>\varepsilon\log n\mid T_n\right).

Taking expectations and using the tower property gives

E[qn(Tn)]=P(∣M(Tn)−κlog⁡n∣>εlog⁡n).\mathbb{E}[q_n(T_n)]=\mathbb{P}\left(\left|M(T_n)-\kappa\log n\right|>\varepsilon\log n\right).

So qn(Tn)→0q_n(T_n)\to0 in probability. In particular,

P(qn(Tn)≤ε)→1.\mathbb{P}\left(q_n(T_n)\le\varepsilon\right)\to1.

Combining this with the height bound completes the proof. □\square

Lemma 17. With conditional expectation given TnT_n,

ETn[M(Tn)]=(κ+op(1))log⁡n.\mathbb{E}_{T_n}[M(T_n)]=(\kappa+o_p(1))\log n.

Proof. Write

Mn:=M(Tn).M_n:=M(T_n).

Let mnm_n be any median of the conditional law of MnM_n given TnT_n. Fix ε∈(0,1/2)\varepsilon\in(0,1/2), and let C=C(a)C=C(a) be as in Lemma 16. Let Gn,εG_{n,\varepsilon} be the event that

height⁡(Tn)≤Clog⁡n\operatorname{height}(T_n)\le C\log n

and

P(∣Mn−κlog⁡n∣>εlog⁡n∣Tn)≤ε.\mathbb{P}\left(\left|M_n-\kappa\log n\right|>\varepsilon\log n\mid T_n\right)\le\varepsilon.

On Gn,εG_{n,\varepsilon}, the second condition implies

P(Mn≤(κ−ε)log⁡n∣Tn)≤εandP(Mn≥(κ+ε)log⁡n∣Tn)≤ε.\mathbb{P}\left(M_n\le(\kappa-\varepsilon)\log n\mid T_n\right)\le\varepsilon \quad\text{and}\quad \mathbb{P}\left(M_n\ge(\kappa+\varepsilon)\log n\mid T_n\right)\le\varepsilon.

Since ε<1/2\varepsilon<1/2, this implies

∣mn−κlog⁡n∣≤εlog⁡n.(1)\left|m_n-\kappa\log n\right|\le\varepsilon\log n. \tag*{(1)}

By Lemma 15, for some universal constant C′>0C'>0,

ETn[(Mn−mn)+]≤C′height⁡(Tn)≤C′Clog⁡n(2)\mathbb{E}_{T_n}\left[(M_n-m_n)^+\right]\le C'\sqrt{\operatorname{height}(T_n)}\le C'\sqrt{C\log n} \tag*{(2)}

on Gn,εG_{n,\varepsilon}. Let

rn:=2εlog⁡n.r_n:=2\varepsilon\log n.

Since Mn≥0M_n \ge0, we also have

(mn−Mn)+≤rn+mn1{Mn≤mn−rn}.(m_n-M_n)^+ \le r_n+m_n\mathbf{1}_{\{M_n\le m_n-r_n\}}.

Therefore, on Gn,εG_{n,\varepsilon}

ETn[(mn−Mn)+]≤2εlog⁡n+mnP(Mn≤mn−2εlog⁡n∣Tn).\mathbb{E}_{T_n}[(m_n-M_n)^+] \le2\varepsilon\log n+m_n\mathbb{P}(M_n\le m_n-2\varepsilon\log n\mid T_n).

Since mn≤(κ+ε)log⁡nm_n\le(\kappa+\varepsilon)\log n and

mn−2εlog⁡n≤(κ−ε)log⁡n,m_n-2\varepsilon\log n\le(\kappa-\varepsilon)\log n,

we obtain on Gn,εG_{n,\varepsilon} that

ETn[(mn−Mn)+]≤2εlog⁡n+(κ+ε)εlog⁡n=(κ+ε+2)εlog⁡n.(3)\mathbb{E}_{T_n}[(m_n-M_n)^+] \le2\varepsilon\log n+(\kappa+\varepsilon)\varepsilon\log n=(\kappa+\varepsilon+2)\varepsilon\log n. \tag*{(3)}

By (1), (2), and (3), we find that on Gn,εG_{n,\varepsilon},

∣ETn[Mn]−κlog⁡n∣≤∣ETn[Mn]−mn∣+∣mn−κlog⁡n∣≤ETn[(Mn−mn)+]+ETn[(mn−Mn)+]+εlog⁡n≤C′Clog⁡n+(κ+ε+2)εlog⁡n+εlog⁡n=C′Clog⁡n+(κ+ε+3)εlog⁡n.(4)\begin{aligned} \left|\mathbb{E}_{T_n}[M_n]-\kappa\log n\right| &\le\left|\mathbb{E}_{T_n}[M_n]-m_n\right|+\left|m_n-\kappa\log n\right|\\ &\le\mathbb{E}_{T_n}[(M_n-m_n)^+]+\mathbb{E}_{T_n}[(m_n-M_n)^+]+\varepsilon\log n\\ &\le C'\sqrt{C\log n}+(\kappa+\varepsilon+2)\varepsilon\log n+\varepsilon\log n\\ &=C'\sqrt{C\log n}+(\kappa+\varepsilon+3)\varepsilon\log n. \tag*{(4)} \end{aligned}

Given δ>0\delta>0, choose ε∈(0,1/2)\varepsilon\in(0,1/2) so small that (κ+ε+3)ε<δ/2(\kappa+\varepsilon+3)\varepsilon<\delta/2. By Lemma 16, P(Gn,ε)→1\mathbb{P}(G_{n,\varepsilon})\to1. Since log⁡n=o(log⁡n)\sqrt{\log n}=o(\log n), (4) implies

P(∣ETn[Mn]−κlog⁡n∣>δlog⁡n)→0.\mathbb{P}\left(\left|\mathbb{E}_{T_n}[M_n]-\kappa\log n\right|>\delta\log n\right)\to0.

Since δ>0\delta>0 was arbitrary, this means that

ETn[Mn]log⁡n⟶pκ.\frac{\mathbb{E}_{T_n}[M_n]}{\log n}\overset{p}{\longrightarrow}\kappa.

We may now prove our main result.

Proof of Theorem 1. Condition on TnT_n and recall that

Mn:=sup⁡v∈V(Tn)ηv.M_n:=\sup_{v\in V(T_n)}\eta_v.

By Theorem 5, for any λ≥1\lambda\ge1,

∣τcov(Tn)−∣E(Tn)∣(ETn[Mn])2∣≤λ∣E(Tn)∣diam⁡(Tn)ETn[Mn]\left|\tau_{\mathrm{cov}}(T_n)-|E(T_n)|\left(\mathbb{E}_{T_n}[M_n]\right)^2\right| \le\lambda|E(T_n)|\sqrt{\operatorname{diam}(T_n)\mathbb{E}_{T_n}[M_n]}

with probability at least 1−Ce−cλ1-Ce^{-c\lambda}. By diam⁡(Tn)≤2⋅height⁡(Tn)\operatorname{diam}(T_n)\le2\cdot\operatorname{height}(T_n) and Theorem 3,

diam⁡(Tn)≤(1+op(1))(2(1+a)ξ)log⁡n,\operatorname{diam}(T_n)\le(1+o_p(1))\left(\frac{2}{(1+a)\xi}\right)\log n,

and by Lemma 17,

ETn[Mn]=(1+op(1))γ1+alog⁡n.\mathbb{E}_{T_n}[M_n]=(1+o_p(1))\frac{\gamma}{1+a}\log n.

Since ∣E(Tn)∣=n−1|E(T_n)|=n-1, the deviation term is at most

(1+op(1))λn(γ1+a)(2(1+a)ξ)1/2(log⁡n)3/2=Op(λn(log⁡n)3/2).(1+o_p(1))\lambda n\left(\frac{\gamma}{1+a}\right)\left(\frac{2}{(1+a)\xi}\right)^{1/2}(\log n)^{3/2} =O_p\left(\lambda n(\log n)^{3/2}\right).

Choose λ=λ(n)\lambda= \lambda(n) with λ→∞\lambda\to\infty and λ=o((log⁡n)1/2)\lambda= o\left((\log n)^{1/2}\right). Then Ce−cλ=o(1)Ce^{-c\lambda} = o(1) and the deviation is op(n(log⁡n)2)o_p\left(n(\log n)^2\right). Therefore,

τcov(Tn)=∣E(Tn)∣(ETn[Mn])2+op(n(log⁡n)2)=(1+op(1))γ2(1+a)2n(log⁡n)2,\tau_{\mathrm{cov}}(T_n) = \lvert E(T_n)\rvert\left(\mathbb{E}_{T_n}[M_n]\right)^2 + o_p\left(n(\log n)^2\right) = \left(1+o_p(1)\right)\frac{\gamma^2}{(1+a)^2}n(\log n)^2,

as claimed. □

Expected cover time

The following is the commute-time identity of [7], specialised to trees.

Lemma 18 (Commute-time identity). For every finite tree TT and every u,v∈V(T)u,v \in V(T),

Eu[τv]+Ev[τu]=2∣E(T)∣d(u,v).\mathbb{E}_u[\tau_v] + \mathbb{E}_v[\tau_u] = 2\lvert E(T)\rvert d(u,v).

In particular, if TT has nn vertices, then

thit(T)≤2(n−1)diam⁡(T).(5)t_{\mathrm{hit}}(T) \le2(n-1)\operatorname{diam}(T). \tag*{(5)}

We will also use the following bound of Matthews.

Lemma 19 (Matthews’ bound [22]). For every finite connected graph GG on nn vertices,

tcov(G)≤thit(G)∑k=1n−11k.t_{\mathrm{cov}}(G) \le t_{\mathrm{hit}}(G)\sum_{k=1}^{n-1}\frac{1}{k}.

Proof of Corollary 2. Set Dn:=diam⁡(Tn)D_n := \operatorname{diam}(T_n). By (5) and Lemma 19,

tcov(Tn)≤2(n−1)Dn∑k=1n−11k.(6)t_{\mathrm{cov}}(T_n) \le2(n-1)D_n\sum_{k=1}^{n-1}\frac{1}{k}. \tag*{(6)}

By (5), (6) and Theorem 3, thit(Tn)=Op(nlog⁡n)t_{\mathrm{hit}}(T_n) = O_p(n\log n) and tcov(Tn)=Op(n(log⁡n)2)t_{\mathrm{cov}}(T_n) = O_p\left(n(\log n)^2\right). Choose λn→∞\lambda_n \to\infty with λn=o((log⁡n)1/2)\lambda_n = o\left((\log n)^{1/2}\right); for example, take λn=(log⁡n)1/4\lambda_n = (\log n)^{1/4}. Conditionally on TnT_n, Corollary 6 gives

P(∣τcov(Tn)−tcov(Tn)∣≥λntcov(Tn)thit(Tn)∣Tn)≤Ce−cλn.\mathbb{P}\left(\left\lvert\tau_{\mathrm{cov}}(T_n)-t_{\mathrm{cov}}(T_n)\right\rvert\ge\lambda_n\sqrt{t_{\mathrm{cov}}(T_n)t_{\mathrm{hit}}(T_n)}\mathrel{\Big|}T_n\right) \le Ce^{-c\lambda_n}.

Since λntcov(Tn)thit(Tn)=op(n(log⁡n)2)\lambda_n\sqrt{t_{\mathrm{cov}}(T_n)t_{\mathrm{hit}}(T_n)} = o_p\left(n(\log n)^2\right) and Ce−cλn=o(1)Ce^{-c\lambda_n} = o(1), it follows that

∣τcov(Tn)−tcov(Tn)∣=op(n(log⁡n)2).\left\lvert\tau_{\mathrm{cov}}(T_n)-t_{\mathrm{cov}}(T_n)\right\rvert= o_p\left(n(\log n)^2\right).

Together with Theorem 1, this yields

tcov(Tn)n(log⁡n)2→pγ2(1+a)2.(7)\frac{t_{\mathrm{cov}}(T_n)}{n(\log n)^2} \xrightarrow{\mathrm{p}} \frac{\gamma^2}{(1+a)^2}. \tag*{(7)}

We next justify taking expectations. Put Hn:=height⁡(Tn)H_n := \operatorname{height}(T_n). By Theorem 3, Hn/log⁡nH_n/\log n converges in L1L^1. In particular, the family (Hn/log⁡n)n≥2(H_n/\log n)_{n\ge2} is uniformly integrable. Since Dn≤2HnD_n \le2H_n, the family (Dn/log⁡n)n≥2(D_n/\log n)_{n\ge2} is therefore uniformly integrable. Moreover, (6) gives

tcov(Tn)n(log⁡n)2≤2n−1nDnlog⁡n∑k=1n−11/klog⁡n.\frac{t_{\mathrm{cov}}(T_n)}{n(\log n)^2} \le2\frac{n-1}{n}\frac{D_n}{\log n}\frac{\sum_{k=1}^{n-1}1/k}{\log n}.

The two deterministic factors on the right are bounded uniformly in nn. Hence the normalised cover times form a uniformly integrable family, and (7) yields

E[tcov(Tn)]=(1+o(1))γ2(1+a)2n(log⁡n)2.\mathbb{E}\left[t_{\mathrm{cov}}(T_n)\right] = (1+o(1))\frac{\gamma^2}{(1+a)^2}n(\log n)^2.

Acknowledgements

This note was begun at the 19th Annual Workshop on Probability and Combinatorics, held at the Bellairs Institute, Barbados, March 28–April 4, 2025. We are very grateful to Tom Hutchcroft and James Martin for discussions at an early stage of the project. Some further work on it took place while O.A. and C.G. were in residence at the Simons Laufer Mathematical Sciences Institute in Berkeley, California, during the Spring 2025 semester, and they gratefully acknowledge the support of the National Science Foundation under Grant No. DMS-1928930. O.A. further thanks the Clay Institute for a Clay Senior Fellowship while at SLMath, and Magdalen College, Oxford for a visiting fellowship in Michaelmas Term 2025.

The proofs and manuscript were written by the authors. AI tools were only used for literature research and to check the final draft for typographical and other errors.

References

Biggins in the immortal immobile case

In this appendix we explain why the specialised statement used in the text follows from Biggins’ more general framework.

Proof of Proposition 7. Start from the immortal branching random walk of Proposition 7. To match Biggins’ notation, take his basic triple (Z,M,χ)(Z,M,\chi) as follows: ZZ is the offspring point process introduced in the text, M(s)≡0M(s) \equiv0, and χ(s)=1s≥0\chi(s) = \mathbb{1}_{s\geq0}. Thus, writing Nt\mathcal{N}_t for Biggins’ random measure (denoted NtN_t in [4]), Nt\mathcal{N}_t places one atom at the birth position of each particle that has been born by time tt. Therefore, for each x∈Rx \in\mathbb{R}, we have Nt([x,∞))=Pt(x)\mathcal{N}_t([x,\infty)) = P_t(x), and his right edge is our RtR_t.

We now check the hypotheses of [4 Corollary 2.2]. First, χ\chi is a 0-1 characteristic. Second, by Corollary 9,

α(θ)=a+eθ2/2\alpha(\theta) = a + e^{\theta^2/2}

for every θ∈R\theta\in\mathbb{R}; in particular α(θ)<∞\alpha(\theta) < \infty for every θ<0\theta< 0, which is stronger than the finiteness assumption in [4 Corollary 2.2]. Third, the process is well-regulated. By the definition just before [4 Corollary 2.1], this means that for each θ≤0\theta\leq0 with α(θ)<∞\alpha(\theta) < \infty one must have

E[sup⁡s≥0{e−α(θ)se−θM(s)χ(s)}]<∞.\mathbb{E}\left[\sup_{s\geq0}\left\{e^{-\alpha(\theta)s}e^{-\theta M(s)}\chi(s)\right\}\right] < \infty.

In our setting M(s)≡0M(s) \equiv0 and χ(s)=1s≥0\chi(s) = \mathbb{1}_{s\geq0}, so the expression inside the supremum becomes simply e−α(θ)se^{-\alpha(\theta)s} for s≥0s \geq0. Hence Biggins’ well-regulated condition reduces to

sup⁡s≥0e−α(θ)s<∞.\sup_{s\geq0} e^{-\alpha(\theta)s} < \infty.

Again by Corollary 9, α(θ)>0\alpha(\theta) > 0 for every θ\theta, so the function s↦e−α(θ)ss \mapsto e^{-\alpha(\theta)s} is decreasing on [0,∞)[0,\infty), and therefore

sup⁡s≥0e−α(θ)s=1.\sup_{s\geq0} e^{-\alpha(\theta)s} = 1.

Hence the process is well-regulated. Thus all hypotheses of [4 Corollary 2.2] are satisfied. Therefore [4 Corollary 2.2] yields

Rtt⟶inf⁡{x:α∗(x)<0}\frac{R_t}{t} \longrightarrow\inf\{x : \alpha^*(x) < 0\}

almost surely. The quantity on the right is γ0\gamma_0 by definition, so this is exactly the stated conclusion. ∎

References

  1. [1]Mohammed Abdullah, Colin Cooper, and Alan M. Frieze, Cover time of a random graph with given degree sequence, Discrete Mathematics 312 (2012), no. 21, 3146–3163.
  2. [2]David J. Aldous, Random walk covering of some special trees, Journal of Mathematical Analysis and Applications 157 (1991), no. 1, 271–283. MR 1109456DOI
  3. [3]J. D. Biggins, The growth and spread of the general branching random walk, Ann. Appl. Probab. 5 (1995), no. 4, 1008–1024. MR 1384364DOI
  4. [4]———, How fast does a general branching random walk spread?, Classical and modern branching processes (Minneapolis, MN, 1994), IMA Vol. Math. Appl., vol. 84, Springer, New York, 1997, pp. 19–39. MR 1601689DOI
  5. [5]Graham R. Brightwell and Peter Winkler, Extremal cover times for random walks on trees, Journal of Graph Theory 14 (1990), no. 5, 547–554.DOI
  6. [6]Nicolas Broutin, Luc Devroye, Erin McLeish, and Mikael de la Salle, The height of increasing trees, Random Structures & Algorithms 32 (2008), no. 4, 494–518. MR 2423922DOI
  7. [7]Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari, The electrical resistance of a graph captures its commute and cover times, Computational Complexity 6 (1996/97), no. 4, 312–340. MR 1613611
  8. [8]Colin Cooper and Alan M. Frieze, The cover time of random regular graphs, SIAM Journal on Discrete Mathematics 18 (2005), no. 4, 728–740.
  9. [9]———, The cover time of sparse random graphs, Random Structures & Algorithms 30 (2007), no. 1–2, 1–16.
  10. [10]———, The cover time of the giant component of a random graph, Random Structures & Algorithms 32 (2008), no. 4, 401–439.DOI
  11. [11]———, The cover time of random geometric graphs, Random Structures & Algorithms 38 (2011), no. 3, 324–349.
  12. [12]Jian Ding, Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees, Ann. Probab. 42 (2014), no. 2, 464–496. MR 3178464DOI
  13. [13]Jian Ding, James R. Lee, and Yuval Peres, Cover times, blanket times, and majorizing measures, Ann. of Math. (2) 175 (2012), no. 3, 1409–1471. MR 2912708
  14. [14]Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms 6 (1995), no. 4, 433–438.DOI
  15. [15]———, Collecting coupons on trees, and the cover time of random walks, Computational Complexity 6 (1996), no. 4, 341–356.DOI
  16. [16]Xavier Fernique, Régularité des trajectoires des fonctions aléatoires gaussiennes, École d’Été de Probabilités de Saint-Flour IV—1974, Lecture Notes in Mathematics, vol. 480, Springer, Berlin, 1975, pp. 1–96. MR 0413238DOI
  17. [17]Michael Fuchs, Hsien-Kuei Hwang, and Ralph Neininger, Profiles of random trees: limit theorems for random recursive trees and binary search trees, Algorithmica 46 (2006), no. 3-4, 367–407.DOI
  18. [18]Cecilia Holmgren and Svante Janson, Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees, Probab. Surv. 14 (2017), 53–154. MR 3626585arxiv.org/abs/1601.03691
  19. [19]Johan Jonasson, On the cover time for random walks on random graphs, Combinatorics, Probability and Computing 7 (1998), no. 3, 265–279.DOI
  20. [20]Jeff D. Kahn, Nathan Linial, Noam Nisan, and Michael E. Saks, On the cover time of random walks on graphs, Journal of Theoretical Probability 2 (1989), no. 1, 121–128.DOI
  21. [21]Russell Lyons and Yuval Peres, Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. MR 3961205DOI
  22. [22]Peter Matthews, Covering problems for Markov chains, The Annals of Probability 16 (1988), no. 3, 1215–1228. MR 942764DOI
  23. [23]Boris Pittel, Note on the heights of random recursive trees and random m-ary search trees, Random Structures & Algorithms 5 (1994), no. 2, 337–347. MR 1262983DOI
  24. [24]Vladimir N. Sudakov, Gaussian random processes and measures of solid angles in Hilbert space, Doklady Akademii Nauk SSSR 197 (1971), no. 1, 43–45, English translation in Soviet Math. Dokl. 12 (1971), 412–415. MR 0288832
  25. [25]Michel Talagrand, Small tails for the supremum of a Gaussian process, Annales de l’Institut Henri Poincaré. Probabilités et Statistiques 24 (1988), no. 2, 307–315. MR 953122
  26. [26]Remco van der Hofstad, Small-world phenomena in preferential attachment models, Random graphs and complex networks. Vol. 2, Cambridge University Press, Cambridge, 2024, pp. 326–380.DOI

Paper details

vlnc:W_bxwhxje9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents