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 -ary increasing trees. We prove explicit limits in probability and expectation when the cover times are rescaled by . In particular, for the uniform random recursive tree the cover time is close to with high probability.
A recursive tree on vertices is a rooted tree labelled by 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 , or for an integer . The tree consists of the single vertex 1. For , the tree is obtained from by adding vertex and attaching it to some with probability proportional to , where is the out-degree (i.e., the number of children) of in . We write for the law of . For , vertex attaches to one of the earlier vertices, each of which is chosen with probability ; this generates the uniform random recursive tree (URRT). For , this model is known as a linear preferential attachment tree.
This model can be defined also for certain . The construction is well-defined for every exactly when for an integer . Our results extend naturally to every nondegenerate such case, namely . For , a vertex with children has attachment weight , which vanishes when . Equivalently, give each vertex 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 -ary tree.) A vertex with children contributes 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 -ary increasing tree studied in [6 p. 513]. We exclude from this paper the case in which the tree is not random but is just a path on vertices. In this case, the cover time is of order 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 , let denote expectation for a discrete-time simple random walk on started at . For , define the hitting time $\tau_v := \inf{t \ge 0 : X_t = , and write 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
and
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 -ary trees and uniform random labelled trees (Cayley trees); Brightwell and Winkler [5] showed that, among all choices of an -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 -vertex graph has expected cover time at least .
The purpose of this note is to find the asymptotic behaviour of 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 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 , 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 for the principal branch of the Lambert function (sometimes denoted ). This is the unique continuous solution to for which satisfies . Note that takes values in , and is increasing to infinity on its domain (roughly as ). We write for any quantity that converges to in probability as . Our main result can now be stated.
Theorem 1. Fix , or for an integer . For each , let , and let be the cover time of a simple random walk on started at the root. Then, as ,
where
In particular we have and so for the URRT,
See Figure 1 for an illustration of the relevant constants as functions of . Note that for not of the form we do not have any model realizing the specified constants. Interpolating between -ary graphs, e.g. with random degrees would be one option, though we do not pursue this here.
Figure 1. The functions and from Theorem 1.
Corollary 2. Under the assumptions of Theorem 1, as ,
In particular for the URRT,
Here the expectation is over .
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 . 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 at level is known [17] to be , and the maximum of that many i.i.d. variables is concentrated around . This is maximized at , and so the maximum of the GFF is at most , heuristically attained at some vertices of height . It is possible to get a matching lower bound (which we do). Typically two vertices of 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 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 , we write for the maximum graph distance from the root to a vertex of and for the diameter of (that is, the largest graph distance between any two of its vertices). Then
For preferential attachment trees, the first-order height asymptotic was proved for by Pittel [23, Theorem 1], and for by Broutin et al. [6, Theorem 3]. We use below the following result giving convergence in .
Theorem 3 [18], Theorem 13.19 and Example 13.9). Suppose that , or that for an integer . Then
where is the unique root in of the equation .
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 , and Holmgren and Janson [18] for the -ary case. We recap this construction for completeness. Throughout, for , let denote the exponential distribution with rate . (Here we take with probability .) We embed the sequence in continuous time as follows. Consider a continuous-time pure birth process that generates a sequence of growing trees. For , denote by the tree at time . The process starts at with consisting of a single root vertex, labelled 1. Each vertex in the tree is endowed with an independent exponential clock. At time , the rate of its clock is . When the clock belonging to vertex rings, a new vertex (with the next free label) is created, and attached to as a child. The rate of 's clock is then updated, and an independent clock is started for the new vertex. Let be the random time at which vertex first appears in the tree.
Claim 4. Set for . Then the random variables are independent, with . Moreover, the embedded chain has the same joint law as .
Proof. Fix and consider the process at time , when has vertex set . Conditional on the evolution up to this time, the times from until the clocks next ring are, by the memoryless property, independent exponential random variables with respective rates , for . Since the out-degrees in sum to , the total clock rate is . Hence their minimum has distribution , while vertex attaches to with probability proportional to . Since the total clock rate depends only on , the conditional law of does not depend on the evolution up to time . In particular, is independent of , so the variables are independent. Since , induction shows that the embedded chain has the same joint law as . Finally, , so .
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 , pinned at a vertex , has a particularly simple description. Root at and set . Then, recursively, whenever is the parent of in the tree, let have a standard normal distribution, with these increments independent over the edges of .
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 such that the following holds. Let be a tree with at least two vertices and let . Let be the GFF on pinned at . Then, for the random walk started at and every ,
Corollary 6 [12], Corollary 1.3). There exist universal constants such that, for every finite rooted tree with at least two vertices and every ,
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 . Then, recursively, when a new vertex is born to a parent at time , its position is set to be , where the are independent and identically distributed standard normal random variables. The sequence 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 has the same law as the Gaussian free field on 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 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
The offspring point process for a vertex gives the spatial displacement and relative birth times of its children. In our case, this is
where are independent standard normal random variables. The birth times are defined in terms of which are independent exponential random variables with , and . For and , let be the number of particles present at time whose positions are at least . The rightmost particle is given by
The analysis of the branching random walk relies on the two-dimensional Laplace transform of the intensity measure of on the domain , which is defined by
Following Biggins, define for this BRW,
Set . The following consequence of Biggins [4 Corollary 2.2] shows that converges almost surely to . 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
almost surely as .
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 , let denote its position. Write for the set of vertices born by time , and define
It is generally the case for branching random walks that such quantities grow (or decay) exponentially with . Let us posit that this occurs at some rate , i.e.
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 th child of the root, which is born at time , is the root of a new, equally distributed branching process. The time and spatial shift from the root imply this sub-process contributes on average, shifted by to account for its starting position. We obtain the equation
Using the approximate exponential growth, we then get
for large . Cancelling a factor of from both sides yields that should be chosen so that
This gives rise to the definition of given above.
Now consider . Then, for ,
and so
Since this holds for all , we may optimise to get a tighter bound on the right-hand side by taking . A large deviations argument shows that this, in fact, captures the correct exponential rate, so that indeed
The right edge of the population at large time is then to be found approximately at the point where is such that (i.e. the point where tips from growing exponentially to decaying exponentially). This is precisely .
We now compute these quantities explicitly in our setting: in Claim 8, and in Corollary 9, and finally in Claim 10.
Claim 8. For and ,
Proof. By linearity of expectation and by independence,
The law of does not depend on , and . The remaining identity
is implicit, when , in [23 proof of Theorem 1, p. 340]; for completeness, and to include the case , we derive it explicitly here. If , then for every , so
Therefore
which is the required formula when .
Assume henceforth that . Letting and defining and , we have
If , then and , so Gauss’ hypergeometric summation formula gives
If , then and . Moreover, for , since . The terminating form of Gauss’ formula therefore gives
Thus, in either case,
Subtracting the term, which is equal to 1, we obtain
and the statement follows. □
Corollary 9. For all , , and for all ,
where is the principal branch of the Lambert function.
Proof. By Claim 8, for fixed and we have , which is strictly decreasing in with as and as . Thus iff , and the infimum is attained at equality, giving .
Fix and consider for . The function is strictly convex since , so the minimum over is attained at the unique point where . We find that point:
Let . Squaring gives , hence . From and we get . Evaluating at the minimiser,
Claim 10. Let . Then
In particular, .
Proof. Writing , we know by Corollary 9 that . Thus we have if and only if . Now, is strictly decreasing in on . Thus there is a unique solving the equation . By the previous equivalence, if and only if . Writing , we have , so , and . This implies , hence , from which the statement follows. □
By Proposition 7 and Claim 10, we obtain the following.
Proposition 11. The position of the rightmost particle satisfies almost surely, with as in Theorem 1.
Proof. By Proposition 7,
almost surely. Finally, by Claim 10 we have , so almost surely. □
We will need the following law of large numbers for (the time at which the growing tree first has vertices). This lets us apply Proposition 11 at the random time .
Lemma 12. As ,
almost surely.
We follow the proof of [23 Theorem 1]: First and second moments give concentration of near ; monotonicity and restriction to a lacunary sequence strengthen to a.s. convergence.
Proof. By Claim 4, with independent . Thus,
and
Let . For any fixed , Chebyshev gives
for some constant . Since , the Borel–Cantelli lemma implies almost surely. For we have and , hence
and both bounds tend to almost surely.
The next statement follows easily.
Corollary 13. The GFF on the growing tree satisfies
almost surely as .
Proof. By Proposition 11, almost surely. By Lemma 12, almost surely. On the intersection of these probability-1 events,
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 be a finite centred Gaussian process, and set
Suppose that , and let satisfy . Then, for every ,
where is a standard normal random variable.
Lemma 15. Let be a rooted tree with at least three vertices and height , let be the pinned GFF on , and set
Let be a median of . Then for every ,
where is a standard normal random variable. In particular, there is a universal constant such that
Proof. Since has at least three vertices, (consider any two distinct non-root vertices), while has no atoms on . Hence the median is well defined, positive and .
The process is a discrete centred Gaussian process. For each ,
where is the graph distance from the root. Hence,
By Lemma 14, applied to the Gaussian process ,
for every . Integrating this bound yields
for a universal constant . □
For brevity, set
The next lemma is a quenched concentration result for the maximum of the GFF on .
Lemma 16. There exists such that, for every fixed , with probability tending to as , the tree satisfies
and the maximum of the GFF satisfies
Proof. By Theorem 3, there exists such that
Let
Under the joint law of , Corollary 13 implies
By definition,
Taking expectations and using the tower property gives
So in probability. In particular,
Combining this with the height bound completes the proof.
Lemma 17. With conditional expectation given ,
Proof. Write
Let be any median of the conditional law of given . Fix , and let be as in Lemma 16. Let be the event that
and
On , the second condition implies
Since , this implies
By Lemma 15, for some universal constant ,
on . Let
Since , we also have
Therefore, on
Since and
we obtain on that
By (1), (2), and (3), we find that on ,
Given , choose so small that . By Lemma 16, . Since , (4) implies
Since was arbitrary, this means that
We may now prove our main result.
Proof of Theorem 1. Condition on and recall that
By Theorem 5, for any ,
with probability at least . By and Theorem 3,
and by Lemma 17,
Since , the deviation term is at most
Choose with and . Then and the deviation is . Therefore,
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 and every ,
In particular, if has vertices, then
We will also use the following bound of Matthews.
Lemma 19 (Matthews’ bound [22]). For every finite connected graph on vertices,
Proof of Corollary 2. Set . By (5) and Lemma 19,
By (5), (6) and Theorem 3, and . Choose with ; for example, take . Conditionally on , Corollary 6 gives
Since and , it follows that
Together with Theorem 1, this yields
We next justify taking expectations. Put . By Theorem 3, converges in . In particular, the family is uniformly integrable. Since , the family is therefore uniformly integrable. Moreover, (6) gives
The two deterministic factors on the right are bounded uniformly in . Hence the normalised cover times form a uniformly integrable family, and (7) yields
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 as follows: is the offspring point process introduced in the text, , and . Thus, writing for Biggins’ random measure (denoted in [4]), places one atom at the birth position of each particle that has been born by time . Therefore, for each , we have , and his right edge is our .
We now check the hypotheses of [4 Corollary 2.2]. First, is a 0-1 characteristic. Second, by Corollary 9,
for every ; in particular for every , 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 with one must have
In our setting and , so the expression inside the supremum becomes simply for . Hence Biggins’ well-regulated condition reduces to
Again by Corollary 9, for every , so the function is decreasing on , and therefore
Hence the process is well-regulated. Thus all hypotheses of [4 Corollary 2.2] are satisfied. Therefore [4 Corollary 2.2] yields
almost surely. The quantity on the right is by definition, so this is exactly the stated conclusion. ∎
References
- [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]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]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]———, 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]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]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]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]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]———, The cover time of sparse random graphs, Random Structures & Algorithms 30 (2007), no. 1–2, 1–16.
- [10]———, The cover time of the giant component of a random graph, Random Structures & Algorithms 32 (2008), no. 4, 401–439.DOI
- [11]———, The cover time of random geometric graphs, Random Structures & Algorithms 38 (2011), no. 3, 324–349.
- [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]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]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]———, Collecting coupons on trees, and the cover time of random walks, Computational Complexity 6 (1996), no. 4, 341–356.DOI
- [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]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]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]Johan Jonasson, On the cover time for random walks on random graphs, Combinatorics, Probability and Computing 7 (1998), no. 3, 265–279.DOI
- [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]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]Peter Matthews, Covering problems for Markov chains, The Annals of Probability 16 (1988), no. 3, 1215–1228. MR 942764DOI
- [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]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]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]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
