# Estimating the history of a random recursive tree

Simon Briend, Christophe Giraud, Gábor Lugosi, Déborah Sulem

► To cite this version:

Simon Briend, Christophe Giraud, Gábor Lugosi, Déborah Sulem. Estimating the history of a random recursive tree. Bernoulli, In press. hal-04884909

HAL Id: hal-04884909

https://hal.science/hal-04884909v1

Submitted on 13 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Estimating the history of a random recursive tree

SIMON BRIEND*¹,ª, CHRISTOPHE GIRAUD²,ᵇ, GÁBOR LUGOSI³,ᶜ and DÉBORAH SULEM⁴,ᵈ

¹Department of Mathematics, Unidistance, Brig, Switzerland, asimon.briend@unidistance.ch

²Laboratoire de Mathématiques d'Orsay, Université Paris-Salcay, Orsay, France,

ᵇchristophe.giraud@université-paris-saclay.fr

³ICREA, Pg. Lluís Companys 23, 08010 Barcelona,
Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain,
Barcelona School of Economics, Barcelona, Spain, c gabor.lugosi@gmail.com

⁴Università de la Svizzera Italiana, Switzerland, d deborah.sulem@usi.ch

This paper studies the problem of estimating the order of arrival of the vertices in a random recursive tree. Specifically, we study two fundamental models: the uniform attachment model and the linear preferential attachment model. We propose an order estimator based on the Jordan centrality measure and define a family of risk measures to quantify the quality of the ordering procedure. Moreover, we establish a minimax lower bound for this problem, and prove that the proposed estimator is nearly optimal. Finally, we numerically demonstrate that the proposed estimator outperforms degree-based and spectral ordering procedures.

**Keywords:** Latent variable estimation; network archaeology; seriation

## 1. Introduction

Recursive random trees are often used to model the evolution of relational data over time, with applications ranging from epidemiology to information technology. A rooted labelled tree is said to be recursive when the labels are strictly increasing on every path starting at the root. When the history of the network is not observed, the task of inferring past states of the network is often termed *network archaeology* (Navlakha and Kingsford (2011)). Recovering hidden states of the growing network informs on the underlying spreading process and can explain the current network structure. One of the most studied problems in network archaeology is finding the root of the recursive network, that is, the vertex that first appeared and “started” the growing process. This task is closely related to the rumor source detection problem. It has been extensively analyzed for random recursive tree models, see Banerjee and Bhamidi (2022), Brandenberger, Devroye and Goh (2022), Bubeck, Devroye and Lugosi (2017), Bubeck et al. (2017), Contat et al. (2024), Devroye and Reddad (2019), Haigh (1970), Jog and Loh (2017, 2018), Lugosi and Pereira (2019), Shah and Zaman (2011, 2016).

In this paper, we consider the problem of estimating the entire history of the network, that is, the arrival times of all the vertices in a random recursive tree. This problem was previously studied by Magner et al. (2018) in the case of the preferential attachment tree. They conduct their analysis in a setting where the position of vertex 1 is known. This assumption simplifies the problem, as will be discussed in this paper. More recently, Young et al. (2019) studied a related problem, where they estimate the arrival time of edges in a slightly modified preferential attachment graph. They provide numerical experiments suggesting a phase transition in the parameter of their model, depending on which the history of the graph is recoverable or not. In both of these previous works, the authors remark that the problem is made hard by the presence of a large set of vertices (or edges) that cannot be ordered better than at random. In this paper, we introduce a class of measures of the quality of an ordering (2) which assign more importance to the error made on early vertices. These risk measures define a non-trivial and meaningful goal. As was done in Young et al. (2019), one may consider this as a question
of latent variable estimation. A related statistical problem is the so-called seriation. Seriation is the problem of inferring an ordering of points, based on pairwise similarity or on the adjacency information between two points. This similarity measure is assumed to statistically decrease with the distance in a latent space and informs on the latent global order of the points. The seriation problem has been studied in various fields, such as in archaeology (Robinson (1951)), bioinformatics (Recanati, Brüls and d'Aspremont (2017)), and matchmaking (Bradley and Terry (1952)). It has been theoretically analyzed in random graph models such as geometric graphs and graphons (Giraud, Issartel and Verzelen (2023), Janssen and Smith (2022)). In recursive trees, the pairwise affinity between nodes is encoded in the adjacency matrix, and the latent space and latent positions are respectively the temporal line and the arrival times of the vertices. Estimating the temporal order of the vertices in a recursive tree can therefore be interpreted as an instance of the seriation problem.

To estimate the vertices' order, we propose a procedure based on a centrality measure, specifically on the *Jordan centrality*. We prove that this procedure is nearly optimal in two random recursive tree models, namely, the uniform random recursive tree (URRT) and the preferential attachment (PA) model. In these models, a tree of $n \ge 1$ vertices is grown by adding and connecting one vertex at each time step. To describe the growing process, we assume that the vertices have intrinsic *labels* from 1 to $n$. At each step $t = 1, \dots, n$ of the growth, a new vertex, say of label $j_t$, is picked arbitrarily among the set of nodes not yet in the tree, and added to the tree with the *rank* $t$. At $t = 1$, the first sampled vertex is the root of the tree. We denote by $\sigma: \{1, \dots, n\} \to \{1, \dots, n\}$ the ordering (or, ranking) map of vertices such that $\sigma(j_t) = t$. In other words, $\sigma$ is a permutation.

The URRT and PA models differ by the attachment rule used to connect a new vertex at each step $t = 2, \dots, n$ of the growth process. In the URRT model, the vertex $j_t$ is connected by an undirected edge to a vertex sampled uniformly among the vertices of the current tree. In the PA model, the vertex of the tree is sampled with a probability proportional to its degree. We denote by $T = T_n$ the obtained tree structure, that is, the set of nodes with labels in $\{1, \dots, n\}$ and the undirected edges between them. In the statistical problem considered in this paper, after the tree is grown, the rank or arrival time $\sigma(i)$ of each node $i$ is not observed on $T$. The random growing process defines a probability distribution on trees. We denote by $\mathbb{P}$ the corresponding probability distribution and $\mathbb{E}$ the associated expectation.

We note that in these random models, the sampling process is independent of the labels chosen to identify the vertices, here $\{1, \dots, n\}$. Therefore, any coherent ordering procedure should be *label invariant*, that is, independent of these labels. Saying that $\hat{\sigma}$ is label invariant means that for any fixed $T$ and ranking $\sigma$,

$$ \hat{\sigma}(T, \sigma) \stackrel{\mathcal{L}}{=} \hat{\sigma}(T^{\sigma'}, \sigma \circ \sigma'), \quad (1) $$

for a permutation $\sigma'$, where $T^{\sigma'}$ denotes the tree with label $i$ replaced by $\sigma'(i)$. Note that the equality in distribution is a simple equality if the ordering procedure $\hat{\sigma}$ is deterministic. Let us also remark that an easy way to transform any ordering procedure into a label invariant ordering procedure is by applying a random permutation to the labels of the tree before feeding it to the ordering procedure.

In order to measure the quality of an estimator of the history, we introduce a family of risk measures that takes into account the error in the estimated arrival time of each vertex, weighted by a function of the arrival time. We define the following family of risk measures

$$ R_{\alpha}(\hat{\sigma}) \stackrel{\text{def}}{=} \mathbb{E} \left[ \sum_{i=1}^{n} \frac{|\hat{\sigma}(i) - \sigma(i)|}{\sigma(i)^{\alpha}} \right], \quad (2) $$

where $\alpha > 0$. The expectation is taken with respect to the randomness arising both from the tree and the ordering procedure $\hat{\sigma}$, which can be non-deterministic. The parameter $\alpha$ tunes the importance given to vertices with small true rank $\sigma(i)$: the higher $\alpha$, the more weight is given to vertices with low rank.
Perhaps the most natural choice is $\alpha = 1$. In that case the risk corresponds to normalizing the error on the estimation of the arrival time of a vertex by its true arrival time. We note that it is often the early stages of a propagation phenomenon that are more relevant, for example, for designing prevention strategies. Additionally, in random growing trees, it is harder to accurately order the high-rank vertices, due to the inherent model symmetries (Sreedharan et al. (2019)).

One way to construct an estimator $\hat{\sigma}$ of the ranking map is to choose a score function on the set of vertices, and order vertices by increasing (or decreasing) values. Such a score function could be based on the likelihood under the tree model. However, the latter is generally difficult to compute, see Bubeck, Devroye and Lugosi (2017). Instead, score functions based on the degree (Navlakha and Kingsford (2011)) or the so-called rumor centrality (Cantwell, St-Onge and Young (2019)) can be computed in polynomial time.

Another approach are iterative algorithms that recursively infer previous states of the tree such as the history sampling algorithms (Cantwell, St-Onge and Young (2019), Crane and Xu (2021)) and the Peeling procedure (Sreedharan et al. (2019)), which is related to the depth centrality score. These methods are guaranteed to recover a recursive ordering of the vertices. Moreover, Crane and Xu (2021) show that the history sampling algorithm outputs confidence sets for the arrival time of a single vertex with valid frequentist coverage. Besides, Sreedharan et al. (2019) demonstrate that the partial ordering retrieved by the Peeling procedure has good properties in settings where the root of the tree can be unambiguously identified. Nonetheless, there are not yet guarantees on the quality of the global ordering provided by these methods.

The ordering procedure we propose is based on the Jordan centrality, defined, for a vertex $u \in T$ belonging to a tree $T$, as

$$ \psi_T(u) = \max_{v \in V(T), v \sim u} |(T, u)_v|, \qquad (3) $$

where $(T, u)$ denotes the tree $T$ rooted at $u$, where $u \sim v$ means that $u$ and $v$ are neighbors in $T$, and where $(T, u)_v$ denotes the subtree of $T$ containing all vertices $w$ such that $v$ lies on the path connecting $w$ to $u$ (see Figure 1). Somewhat informally, we call $(T, u)_v$ the subtree hanging from $v$ in the rooted tree $(T, u)$. The maximum in (3) is taken over vertices $v$ of the tree that are connected to vertex $u$ by an edge. Intuitively, if a vertex is central, then none of the subtrees hanging from it can be too large. Therefore, the lower $\psi_T(i)$, the more central is vertex $i$. It is straightforward to see that $(\psi_T(u))_{u \in T}$ only depends on the structure of the tree and not on the labels of its vertices. We then define $\hat{\sigma}_J : \{1, \dots, n\} \to \{1, \dots, n\}$ the ordering obtained by ranking the vertices by increasing value of Jordan centrality-breaking ties at random. This estimator is label invariant. An equivalent formulation of this algorithm is to estimate the position of vertex 1 by the Jordan centroid, rooting the tree at this vertex and then ordering vertices by the size of their hanging subtree in the rooted tree. Thus, if the exact position of vertex 1 was known, we would be ordering vertices by the number of their descendants.

While the risk defined in (2) can be computed for any value $\alpha > 0$, we restrict $\alpha$ to a range of values which are relevant for our ordering problem. Specifically, we only consider $\alpha \ge 1$, since for $\alpha < 1$ the problem becomes trivial, since even a random permutation has a risk which is minimax optimal up to constant factor (see Appendix A). In Theorems 1 and 7, we provide minimax lower bounds for the risk $R_\alpha(\hat{\sigma})$ in the URRT and PA model, for any label-invariant estimator $\hat{\sigma}$. Then, in Theorems 4 and 8 upper bounds for the risk of the Jordan ordering are obtained. Finally, in Corollaries 5 and 9 we prove that our proposed estimator is minimax optimal up to constant factors, in a non-trivial range of parameters $\alpha$. In the following table, we summarise our findings. For $\alpha \ge 1$, we denote by $R_\alpha^*$ the optimal risk, and $R_\alpha(\hat{\sigma}_J)$ the risk of the Jordan ordering.
<figure><img src="image_2.png" /><figcaption>**Figure 1.** An illustration of the subtree $(T, u)_v$, corresponding to nodes highlighted in red.</figcaption></figure>

<table><thead><tr><th></th><th>URRT</th><th>PA</th></tr></thead><tbody><tr><td>R<sup>*</sup><sub>&alpha;</sub></td><td>&ge; n<sup>2-&alpha;</sup>/70 &or; 1/2</td><td>&ge; n<sup>2-&alpha;</sup>/70 &or; 1/2</td></tr><tr><td>R<sub>&alpha;</sub>(&sigma;&#770;<sub>J</sub>)</td><td>= O(n<sup>2-&alpha;</sup> + log<sup>4</sup>(n))</td><td>= O(n<sup>2-&alpha;</sup> + n<sup>3/4</sup>)</td></tr></tbody></table>

We also compare numerically the performance of the Jordan estimator with other ordering procedures in a simulation study.

In the rest of this section, we review previous works and introduce some notation. Then, in Section 2, we analyze the Jordan ordering in the URRT model. Next, we consider the PA model and prove analogous results in Section 3. Finally, in the Supplementary Material, we report the results of our simulation study and compare the empirical performance of the Jordan estimator to alternative methods based on the degree centrality, a peeling method (Navlakha and Kingsford (2011, Section 2.3)) and a spectral method commonly used in seriation problems (Recanati, Kerdreux and d'Aspremont (2018)).

## 1.1. Related work

Most methods for ranking the vertices of a random recursive tree have been introduced for the root-finding problem, that is, recovering a vertex (or a set of vertices) that is (contains) the root. For this problem, maximum likelihood estimators (Brandenberger, Devroye and Goh (2022), Bubeck, Devroye and Lugosi (2017), Haigh (1970)) and estimators based on rumor centrality (Shah and Zaman (2011, 2016)) have been proposed and analyzed. Jordan centrality is another measure of centrality used by Bubeck, Devroye and Lugosi (2017), Bubeck et al. (2017) to construct confidence sets. Banerjee and Bhamidi (2022), Jog and Loh (2017, 2018) study the persistence of the most central nodes in random recursive trees. Furthermore, while the vertex with maximum degree is generally not a good estimator of the root in the URRT model, in the PA model pairs degree centrality is useful for retrieving the first vertex (Banerjee and Bhamidi (2021), Contat et al. (2024)). Some recent work studies root-finding in Galton-Walton trees (Brandenberger, Devroye and Goh (2022)) and more general graphs (Briend, Calvillo and Lugosi (2023), Crane and Xu (2023)).
Crane and Xu (2021) propose a general history-sampling procedure for network archaeology, which can be applied to the problem of estimating arrival times. The history sampling algorithm outputs a confidence set of rankings that contains the true one with high probability. However, there is no known bound of the size nor the average global error of an ordering in this confidence set.

The vertex arrival-time estimation problem bears some similarity to the seriation problem, though in the former, the dependence is intrinsically related to the tree structure. For example, in a random geometric graph (Gilbert (1961)), the seriation problem is to estimate the position of the random points. Since there is no time structure in seriation, different metrics for the error are used, such as the maximum distance between the true and estimated latent position. Examples of methods are provided by Giraud, Issartel and Verzelen (2023). Another widely studied seriation method consists in ordering latent points by a spectral method on the graph Laplacian (see Supplementary material and Recanati, Kerdreux and d'Aspremont (2018) for details). They give guarantees for the quality of their method when the observed adjacency matrix is a perturbed Robinson matrix. The expected adjacency matrices of both URRT and PA trees are Robinson, and therefore the models studied here can be viewed as perturbed Robinson matrices. Nonetheless, none of the above-mentioned papers gives any insight about seriation in URRT and PA trees.

## 1.2. Notation

Let $\pi_n$ be the set of permutations of $[n] := \{1, 2, \dots, n\}$, and let $\mathbb{T}_n$ be the set of un-labelled trees of size $n$. We denote by URRT($n$) the distribution of a tree $\mathcal{T}_n$ of size $n \ge 1$, generated from the uniform attachment model. Similarly, we denote by PA($n$) the distribution of a tree sampled from the preferential attachment model. Moreover, we decompose the tree as $\mathcal{T}_n = (T_n, \sigma_n)$, where $T_n$ is the shape of the tree and $\sigma_n$ is the recursive ordering of the vertices in $\mathcal{T}_n$. For simplicity, we drop the subscript $n$ when the size of the tree is fixed and clear from the context. We denote by $\mathbb{P}$ the probability distribution under the tree growing process and $\mathbb{E}$ the corresponding expectation.

Recall that for a tree $T$ and a vertex $u \in T$, we denote by $(T, u)$ the tree rooted at $u$. For a rooted tree $(T, u)$ and a vertex $v$ we denote by $(T, u)_v$ the subtree of $T$ consisting of all vertices $w$ such that $v$ lies on the path connecting $w$ to $u$ (see Figure 1). For two vertices $u, v \in T$, $u \sim v$ means that $u$ is a neighbor of $v$ in $T$ (and reciprocally). In a rooted tree $(T, u)$, we say that $w$ is a child of $v$ if $w$ is in $(T, u)_v$. We denote by $\text{de}_n(u) = |(\mathcal{T}_n, 1)_u| - 1$ the number of descendants of $u$ in $\mathcal{T}_n$. For simplicity, we drop the subscript $n$ and use $\text{de}(u)$ when the size of the tree is fixed and clear from the context.

Recall the definition of the Jordan centrality; for a tree $T$ and vertex $u \in T$,

$$ \psi_T(u) = \max_{v \in T, v \sim u} |(T, u)_v|. \qquad (4) $$

We denote by $c$ a centroid of $T$, defined as $c = \arg \min_{u \in T} \psi_T(u)$. It is well-known that any tree has at least one and at most two centroids. Moreover, for a vertex $u \in T$ that is not a centroid, the subtree $(T, u)_v$, $v \sim u$ with maximum size, contains all centroids.

The Jordan ordering procedure consists in ordering points by increasing values of $\psi$ (ties being broken randomly). Equivalently, it consists in rooting the tree at $c$ and order vertices by $|(T, c)|_u$. We use $\hat{\sigma}_J$ to refer to the Jordan ordering of $T_n$. As noted in the introduction, the Jordan centrality does not depend on the labelling of the tree (only on its shape), and so is a label invariant ordering.
## 2. The uniform attachment model

In this section, we focus on the uniform attachment model as the random growing process of the tree. We first present a lower bound for the risk $R_\alpha(\hat{\sigma})$ of any label-invariant estimator $\hat{\sigma}$ of the vertices order.

### 2.1. A lower bound

In the next proposition, we provide a lower bound for the risk $R_\alpha(\hat{\sigma})$ for any label-invariant estimator of the recursive ordering in the URRT model. Define, for any $n \ge 1$, the optimal risk by

$$R_{\alpha}^{*} := \min_{\hat{\sigma} \in \Pi_{n}} R_{\alpha}(\hat{\sigma}),$$

where $\Pi_n$ is the set of label-invariant recursive orderings.

**Theorem 1.** In the URRT model, we have, for all $\alpha > 0$ and $n \ge 200$,

$$R_{\alpha}^{*} \geq \frac{n^{2-\alpha}}{70}.$$

**Proof.** For a tree $T$ and an ordering of its vertices $\sigma$, let $\tau = \sigma^{-1}$ (i.e, $\tau(i)$ is the label of the vertex that arrives at time $i$). We start by recalling that

$$R_{\alpha}(\hat{\sigma}) = \mathbb{E} \left[ \sum_{j=1}^{n} \frac{|\hat{\sigma}(j) - \sigma(j)|}{\sigma(j)^{\alpha}} \right] = \mathbb{E} \left[ \sum_{j=1}^{n} \frac{|\hat{\sigma} \circ \tau(j) - j|}{j^{\alpha}} \right],$$

which is lower bounded as follows

$$R_{\alpha}(\hat{\sigma}) \geq \sum_{j=[n/2]+1}^{\lfloor 3n/4 \rfloor} \mathbb{E} \left[ \frac{|\hat{\sigma} \circ \tau(j) - j|}{j^{\alpha}} \right] + \sum_{j=[3n/4]+1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma} \circ \tau(j) - j|}{j^{\alpha}} \right] \quad (5)$$

$$\geq \frac{1}{n^{\alpha}} \sum_{j=[n/2]+1}^{\lfloor 3n/4 \rfloor} \mathbb{E} \left[ |\hat{\sigma} \circ \tau(j) - j| + \left| \hat{\sigma} \circ \tau \left( \lfloor \frac{n}{4} \rfloor + j \right) - \lfloor \frac{n}{4} \rfloor - j \right| \right]. \quad (6)$$

The problem is reduced to a control of each term of the summand. For a labelled tree $T$ and a permutation $\gamma$, we denote by $T^\gamma$ the tree with $\gamma$ applied to its labels. For $\lfloor n/2 \rfloor + 1 \le j \le \lfloor 3n/4 \rfloor$, fix $\gamma = (\tau(j), \tau(\lfloor n/4 \rfloor + j))$, that is, the permutation sending $j$ to $\lfloor n/4 \rfloor + j$ and vice versa, while keeping all other elements of $[n]$ in place. Introduce the event

$$\Omega_j := \{\tau(j) \text{ and } \tau(\lfloor n/4 \rfloor + j) \text{ are leaves, connected to vertices of rank } \le n/2\}.$$

First, we check that $\Omega_j$ is an event whose probability is bounded away from 0. We note that for $\Omega_j$ to occur, it suffices that

* vertex $\tau(j)$ connects to a vertex of rank at most $n/2$. This happens with probability $\lfloor n/2 \rfloor / (j-1)$.
* For times ranging from $j + 1$ to $\lfloor n/4 \rfloor + j - 1$ new vertices connect to vertices different from $\tau(j)$. This happens with probability

$$ \prod_{k=j+1}^{\lfloor n/4 \rfloor + j - 1} \frac{k-2}{k-1}. $$

* Vertex $\tau(\lfloor n/4 \rfloor + j)$ connects to a vertex of rank at most $n/2$. This happens with probability $\lfloor n/2 \rfloor / (\lfloor n/4 \rfloor + j - 1)$.

* For times ranging from $\lfloor n/4 \rfloor + j + 1$ to $n$ new vertices connect to vertices different from $\tau(j)$ and $\tau(\lfloor n/4 \rfloor + j)$. This happens with probability

$$ \prod_{k=\lfloor n/4 \rfloor + j + 1}^{n} \frac{k-3}{k-1}. $$

Finally, note that from the definition of the URRT model, the four events corresponding to the four items above are independent. Thus

$$ \begin{aligned} \mathbb{P}\{\Omega_j\} &= \frac{\lfloor n/2 \rfloor}{j-1} \cdot \frac{\lfloor n/2 \rfloor}{\lfloor n/4 \rfloor + j - 1} \cdot \prod_{k=j+1}^{\lfloor n/4 \rfloor + j - 1} \frac{k-2}{k-1} \cdot \prod_{k=\lfloor n/4 \rfloor + j + 1}^{n} \frac{k-3}{k-1} \\ &= \frac{\lfloor n/2 \rfloor}{j-1} \cdot \frac{\lfloor n/2 \rfloor}{\lfloor n/4 \rfloor + j - 1} \cdot \frac{j-1}{\lfloor n/4 \rfloor + j - 2} \cdot \frac{(\lfloor n/4 \rfloor + j - 2)(\lfloor n/4 \rfloor + j - 1)}{(n-2)(n-1)}, \end{aligned} $$

which simplifies to

$$ \mathbb{P}\{\Omega_j\} \geq \frac{1}{4} \left(1 - \frac{1}{n-1}\right). \qquad (7) $$

The first step is to use (7) to control one of the summands in (5) by conditioning on $\Omega_j$.

$$ \begin{aligned} & \mathbb{E}[|\hat{\sigma} \circ \tau(j) - j| + |\hat{\sigma} \circ \tau(\lfloor n/4 \rfloor + j) - (\lfloor n/4 \rfloor + j)|] \\ & \geq \frac{1}{4} \left(1 - \frac{1}{n-1}\right) \mathbb{E}\left[\left|\hat{\sigma} \circ \tau(j) - j\right| + \left|\hat{\sigma} \circ \tau\left(\lfloor \frac{n}{4} \rfloor + j\right) - \left(\lfloor \frac{n}{4} \rfloor + j\right)\right|\right] \Omega_j. \end{aligned} $$

We then decompose on each possible realization of a recursive tree

$$ \begin{aligned} & \mathbb{E}\left[\left|\hat{\sigma} \circ \tau(j) - j\right| + \left|\hat{\sigma} \circ \tau\left(\lfloor \frac{n}{4} \rfloor + j\right) - \left(\lfloor \frac{n}{4} \rfloor + j\right)\right|\right] \Omega_j \\ &= \sum_{t \in \mathcal{T}} \mathbb{P}\{T = t \mid \Omega_j\} \mathbb{E}\left[\left|\hat{\sigma} \circ \tau(j) - j\right| \mid \Omega_j, T = t\right] \\ &\quad + \sum_{t \in \mathcal{T}} \mathbb{P}\{T = t^{\gamma} \mid \Omega_j\} \mathbb{E}\left[\left|\hat{\sigma} \circ \tau\left(\lfloor \frac{n}{4} \rfloor + j\right) - \left(\lfloor \frac{n}{4} \rfloor + j\right)\right|\right] \Omega_j, T = t^{\gamma}, \end{aligned} $$

which is a valid decomposition since $t \mapsto t^{\gamma}$ is a bijection from $\mathcal{T}$ to itself. Theorem 4 of Crane and Xu (2021) states that, in the URRT model, two trees having the same shape but different recursive orders have the same probability. Since on the event $\Omega_j$, $t$ is recursive if and only if $t^{\gamma}$ is recursive, then
$$ \mathbb{P}\{T=t | \Omega_j\} = \mathbb{P}\{T=t^{\gamma} | \Omega_j\}. $$

As a consequence, the above expression factorizes to

$$ \mathbb{E}[|\hat{\sigma} \circ \tau(j) - j| + |\hat{\sigma} \circ \tau(\lfloor \frac{n}{4} \rfloor + j) - \lfloor \frac{n}{4} \rfloor - j| | \Omega_j] = \sum_{t \in T} \mathbb{P}\{T=t | \Omega_j\} \times \\ \left( \mathbb{E}[|\hat{\sigma} \circ \tau(j) - j| | \Omega_j, T=t] + \mathbb{E}[|\hat{\sigma} \circ \tau(\lfloor \frac{n}{4} \rfloor + j) - \lfloor \frac{n}{4} \rfloor + j| | \Omega_j, T=t^{\gamma}] \right). \quad (8) $$

The label invariant condition implies that

$$ \hat{\sigma}[T^{\gamma}] \circ \gamma \stackrel{\mathcal{L}}{=} \hat{\sigma}[T], $$

and in particular,

$$ (\hat{\sigma} \circ \tau(j) | \Omega_j, T=t) \stackrel{\mathcal{L}}{=} (\hat{\sigma} \circ \tau(\lfloor n/4 \rfloor + j) | \Omega_j, T=t^{\gamma}), $$

which directly implies that

$$ \mathbb{E}[|\hat{\sigma} \circ \tau(j) - j| | \Omega_j, T=t] + \mathbb{E}[|\hat{\sigma} \circ \tau(\lfloor \frac{n}{4} \rfloor + j) - \lfloor \frac{n}{4} \rfloor - j| | \Omega_j, T=t^{\gamma}] \geq \lfloor n/4 \rfloor. $$

By plugging the above inequality in (8)

$$ \mathbb{E}[|\hat{\sigma} \circ \tau(j) - j| + |\hat{\sigma} \circ \tau(\lfloor \frac{n}{4} \rfloor + j) - \lfloor \frac{n}{4} \rfloor - j|] \geq \frac{n-4}{16} \left(1 - \frac{1}{n-1}\right). $$

Now, plugging the above inequality in (5) yields

$$ R_{\alpha}(\hat{\sigma}) \geq \frac{n^{2-\alpha}}{70}, $$

for all $n \geq 200$.

□

**Remark 1.** In the URRT, vertices 1 and 2 are indistinguishable. Indeed, when the tree has size 2, vertices 1 and 2 have exactly the same properties. Thus, no label invariant ordering procedure can assign order 1 to vertex 1 with probability higher than 1/2. As a result, we obtain, for any $\alpha$, the trivial lower bound

$$ R_{\alpha}^{*} \geq \frac{1}{2}, $$

which improves the bound of Theorem 1 for $\alpha \geq 2$, and therefore Theorem 1 is non-trivial when $\alpha < 2$.

## 2.2. An auxiliary “descendant-ordering” procedure

In the sequel, we establish upper bounds for the risk of Jordan ordering. Since this is a label-invariant procedure, we may assume, without loss of generality, that $\sigma = \text{Id}$ is the identity permutation. In other
words, the arrival time of a vertex and its label are the same. When the context is clear, vertex labels and arrival times are used interchangeably.

In order to analyze the Jordan ordering, we introduce an auxiliary centrality measure and the corresponding estimator of vertex arrival times. As observed in the introduction, the Jordan ordering procedure consists in estimating the position of vertex 1 by the Jordan centroid $c$ and ordering vertices according to the values of $|(T, c)_u|$. If $c$ was replaced by vertex 1, this measure minus 1 would correspond to the number of descendants of $u$. Thus, a natural ordering is to order vertices by the number of their descendants, that is, the ordering according to the values of $|(T, 1)_u| - 1$ (i.e., by the value of $|(T, 1)_u|$). We call this *descendant ordering*, noting that, as before, ties are broken at random. Note that descendant ordering is not a valid procedure, since the location of the root vertex is not known. On the other hand, the number of descendants is easily analyzed by Pólya urns, and our approach is based on comparing Jordan ordering to this auxiliary procedure. In this section we prove an upper bound for difference of the risk of both procedures. For a tree $T$ and for each $u \in T$, we define the descendant centrality

$$ \psi'_{T}(u) = n + 1 - \mathrm{de}(u), $$

where $\mathrm{de}(u) = |(T, 1)_u| - 1$ is the number of descendants of $u$, as defined in Section 1.2. We denote by $\tilde{\sigma}'$ the ordering of the vertices induced by sorting the values of $\psi'_{T}$ in increasing order.

In the following lemma, we first prove that for the URRT model, the Jordan centrality $\psi_T$, defined in (3), and the descendant centrality $\psi'_T$ coincide for most vertices. Furthermore, we prove bounds on both the number of nodes for which $\psi_T$ may differ from $\psi'_T$ and the estimated rank of vertex 1. We recall that 1 and $c$ denote respectively the root and the rank of a centroid of the tree.

**Lemma 2.** Let $T \sim \mathrm{URRT}$, let $c \in [n]$ be a centroid of $T$ and let $\{1 \to c\}$ be the set of vertices on the path connecting 1 to $c$ in $T$. Then

* for any $v \in [n] \setminus \{1 \to c\}$, we have

$$ \psi_T(v) = \psi'_T(v); $$

* there exists a universal constant $K$ such that $c$ is stochastically dominated by an exponential random variable with mean $K$;

* for $\epsilon \le 0.2$, with probability at least $1 - 5\epsilon$

$$ \tilde{\sigma}_J(1) \le 2.5 \frac{\log(1/\epsilon)}{\epsilon}. $$

**Proof.** Let $T \sim \mathrm{URRT}$. First, we decompose the vertices of $T$ in four sets as shown in Figure 2: case 1 corresponds to the set $\{1 \to c\}$ of nodes connecting the root to the centroid, case 2 to the vertices of $(T, 1)_c \setminus \{c\}$, case 3 to the vertices of $(T, c)_1 \setminus \{1\}$ and finally case 4 to the vertices of $(T, 1)_i \setminus \{i\}$ for $i \in \{1 \to c\} \setminus \{1, c\}$. As we mentioned before, it is well known that for a non-centroid vertex $u$, its neighbor maximizing $|(T, u)_v|$ is such that $|(T, u)_v|$ contains any centroid. Note that for each vertex $u$ in cases 2, 3 and 4, for $v \sim u$ such that the subtree $(T, u)_v$ contains $c$, $(T, u)_v$ also contains vertex 1. As a consequence, $\psi_T(u) = |(T, u)_{\mathrm{pa}(u)}|$, where $\mathrm{pa}(u)$ is the “parent” of $u$. But by definition, $|(T, u)_{\mathrm{pa}(u)}| = n + 1 - \mathrm{de}(u) = \psi'_T(u)$, concluding the proof of the first part of the lemma.

Moon (2002) showed that the rank of the centroid $c$ is dominated by an exponential random variable of mean $K$, for a universal constant. The third statement follows from Theorem 3 of Bubeck, Devroye and Lugosi (2017). □
<figure><img src="image_3.png" /><figcaption>**Figure 2.** Sketch of a tree and its centroid. Circled in red are the vertices of the path {1 → c} (case 1). Blue vertices correspond to case 2, green to case 3 and purple vertices to case 4.</figcaption></figure>

In the following lemma, we bound the risk of $\hat{\sigma}_J$ by that of the descendant ordering $\hat{\sigma}'$. To compare the risks of the Jordan and descendant ordering, we introduce a simple coupling between the two of them, so that ties are broken at random in the same way in both orderings. In a tree $T$ of size $n$, first compute the Jordan ordering (where ties are broken uniformly at random). Then, to compute the descendant ordering, one must choose how to break ties. Let us fix an integer $k$. We denote by $v_1, \dots, v_j$ the vertices of $T$ having exactly $k$ descendants. From Lemma 2 we know that vertices in $\{v_1, \dots, v_j\} \cap [n]\setminus\{1 \to c\}$ have the same Jordan centrality. These ties have been broken uniformly at random in the Jordan ordering. For $j' = |\{v_1, \dots, v_j\} \cap [n]\setminus\{1 \to c\}|$, without loss of generality, we can assume that $\{v_1, \dots, v_j\} \cap [n]\setminus\{1 \to c\} = \{v_1, \dots, v_{j'}\}$ and that $\hat{\sigma}(v_1) < \dots < \hat{\sigma}(v_{j'})$. In the descendant ordering we break the ties of $\hat{\sigma}'(v_1), \dots, \hat{\sigma}'(v_j)$ uniformly at random conditioned on $\hat{\sigma}'(\sigma_1) < \dots < \hat{\sigma}'(\sigma_{j'})$. By doing so for every $k$, the ties of the descendant ordering are broken uniformly at random but in the same manner as in the Jordan ordering. This coupling allows us to compare their respective risks.

**Lemma 3.** Let $T \sim \text{URRT}$. For $\alpha > 0$

$$R_{\alpha}(\hat{\sigma}_J) \le R_{\alpha}(\hat{\sigma}') + K \sum_{i=1}^{n} \frac{1}{i^{\alpha}} + C \log^4(n),$$

where $C > 0$ is a constant (not depending on $\alpha$).

**Proof.** Recall that $\sigma = \text{Id}$, that is, we use the same integer to denote the label of a vertex and its arrival time. We first decompose the global risk $R_{\alpha}(\hat{\sigma}_J)$ into

$$R_{\alpha}(\hat{\sigma}_J) = \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \frac{|\hat{\sigma}_J(i) - i|}{i^{\alpha}}\right] + \mathbb{E}\left[\sum_{i \notin \{1 \to c\}} \frac{|\hat{\sigma}_J(i) - i|}{i^{\alpha}}\right].$$
Since by Lemma 2 and the carefully chosen coupling between Jordan and descendant ordering, vertices outside of the path {$1 \to c$} are put in the same order by the Jordan and the descendant ordering, then, for $i \notin \{1 \to c\}$, $|\hat{\sigma}_J(i) - \hat{\sigma}(i)| \le D + 1$, where $D$ is the distance between 1 and $c$. Thus, we can control the second term of the right-hand side as follows:

$$ 
\begin{aligned}
\mathbb{E}\left[\sum_{i \notin \{1 \to c\}} \frac{|\hat{\sigma}_J(i) - i|}{i^\alpha}\right] &= \mathbb{E}\left[\sum_{i \notin \{1 \to c\}} \frac{|\hat{\sigma}'(i) - i + \hat{\sigma}_J(i) - \hat{\sigma}'(i)|}{i^\alpha}\right] \\
&\le \mathbb{E}[D] \sum_{i=1}^n \frac{1}{i^\alpha} + \mathbb{E}\left[\sum_{i \notin \{1 \to c\}} \frac{|\hat{\sigma}'(i) - i|}{i^\alpha}\right].
\end{aligned}
$$

Since $D$ is at most the arrival time of the centroid, Lemma 2 implies that $\mathbb{E}[D] \le \mathbb{E}[c] \le K$. On the other hand,

$$ \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \frac{|\hat{\sigma}_J(i) - i|}{i^\alpha}\right] \le \mathbb{E}\left[\sum_{i \in \{1 \to c\}} i\right] + \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \hat{\sigma}_J(i)\right]. $$

Clearly,

$$ \mathbb{E}\left[\sum_{i \in \{1 \to c\}} i\right] \le \mathbb{E}[cD]. $$

Since $D \le c$ and since $c$ is dominated by an exponential random variable of mean $K$, by Lemma 2,

$$ \mathbb{E}[cD] \le \mathbb{E}[c^2] \le 2K^2. $$

In addition, since on the path {$1 \to c$}, $\hat{\sigma}_J$ is decreasing, we have

$$ \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \hat{\sigma}_J(i)\right] \le \mathbb{E}[D\hat{\sigma}_J(1)]. $$

Since $D$ and $\hat{\sigma}_J(1)$ are bounded by $n$, they have finite moments. Using Hölder's inequality, for any $\gamma > 0$,

$$ \mathbb{E}[D\hat{\sigma}_J(1)] \le \left(\mathbb{E}\left[D^{\frac{1+\gamma}{\gamma}}\right]\right)^{\frac{\gamma}{1+\gamma}} \left(\mathbb{E}[\hat{\sigma}_J(1)^{1+\gamma}]\right)^{\frac{1}{1+\gamma}}. \quad (9) $$

Since $D \le c$ which is dominated by an exponential random variable,

$$ \left(\mathbb{E}\left[D^{\frac{1+\gamma}{\gamma}}\right]\right)^{\frac{\gamma}{1+\gamma}} \le C \frac{1+\gamma}{\gamma}, \quad (10) $$

for some positive constant $C$. Next, using Lemma 2,

$$ \mathbb{P}\{\hat{\sigma}_J(1) \ge f(\epsilon)\} \le 5\epsilon, $$

where $f(\epsilon) = 2.5 \frac{\log(1/\epsilon)}{\epsilon}$. $f$ is a non-increasing function and therefore $f(5 \log^2(k)/k) \le k$ for all $k \ge 2$. Therefore,
$$ \mathbb{P}\{\hat{\sigma}_J(1) \geq k\} \leq 25 \frac{\log^2(k)}{k}, \quad \text{for all } k \geq 2, $$

so for any $\gamma > 0$,

$$ \mathbb{P}\{\hat{\sigma}_J(1)^{1+\gamma} \geq k\} = \mathbb{P}\{\hat{\sigma}_J(1) \geq k \frac{1}{1+\gamma}\} \leq 25 \frac{\frac{1}{(1+\gamma)^2} \log^2(k)}{k^{\frac{1}{1+\gamma}}}. $$

It follows that

$$ \begin{aligned} \mathbb{E}[\hat{\sigma}_J(1)^{1+\gamma}] &\leq 1 + 2^{1+\gamma} + \int_{k=2}^{n^{1+\gamma}} \mathbb{P}\{\hat{\sigma}_J(1)^{1+\gamma} \geq k\} dk \leq 1 + 2^{1+\gamma} + \int_{k=2}^{n^{1+\gamma}} \frac{25}{k^{\frac{1}{1+\gamma}}} \frac{\log^2(k)}{k^{\frac{1}{1+\gamma}}} dk \\ &\leq 1 + 2^{1+\gamma} + \frac{25}{(1+\gamma)^2} (1+\gamma)^2 \log^2(n) \frac{\gamma+1}{\gamma} (n^{1+\gamma})^{\frac{\gamma}{1+\gamma}} \\ &= 1 + 2^{1+\gamma} + 25 \frac{(1+\gamma) \log^2(n)}{\gamma} n^{\gamma}. \end{aligned} $$

Plugging the obtained inequality in (9) and recalling (10), we obtain

$$ \mathbb{E}[D\hat{\sigma}_J(1)] \leq C \frac{1+\gamma}{\gamma} \left( 1 + 2^{1+\gamma} + 25 \frac{1+\gamma}{\gamma} \log^2(n) n^{\gamma} \right). $$

Choosing $\gamma = 1/\log(n)$ we get

$$ \mathbb{E}[D\hat{\sigma}_J(1)] \leq C' \log^4(n). $$

This concludes the proof of the lemma.

<figure><img src="image_4.png" /></figure>

## 2.3. Performance of Jordan ordering in the URRT model

In this section, we prove upper bounds for the risk $R_\alpha(\hat{\sigma}_J)$. In particular, we prove that for $\alpha \in [1, 2)$, the risk $R_\alpha(\hat{\sigma}_J)$ has the same order as the optimal risk $R_\alpha^*$, defined in Section 2.1.

**Theorem 4.** Let $T \sim \text{URRT}$. Then there exist positive constants $C$, $K$ such that for $1 \leq \alpha < 2$

$$ R_{\alpha}(\hat{\sigma}_{J}) \leq K(\alpha)n^{2-\alpha} + K \sum_{i=1}^{n} \frac{1}{i^{\alpha}} + C \log^{4}(n), $$

where $K(\alpha) = \frac{2}{2-\alpha} + \frac{2e^2}{(2-\alpha)^2} + \frac{2}{(2-\alpha)^3}$. Moreover, for $\alpha \geq 2$

$$ R_{\alpha}(\hat{\sigma}_{J}) \leq C \log^{4}(n). $$

Before proving Theorem 4, we state a corollary that is a direct consequence of Theorems 1 and 4. This corollary notably implies that the Jordan ordering has a risk of optimal order for $\alpha \in [1, 2)$. Note that one cannot hope to match the established lower bounds for the optimal risk in a broader range of $\alpha$ for this method. Indeed, in a uniform random recursive tree of size $n$, the probability that
vertex 1 is a leaf is $1/n$. Since leaves are ordered last by $\hat{\sigma}_J$, and that there are roughly $n/2$ leaves, $\mathbb{P}\{\hat{\sigma}_J(1) \ge n/2\} \approx 1/n$. This implies that $\mathbb{E}[\hat{\sigma}_J(1)] \gtrsim \log(n)/2$, so $\hat{\sigma}_J$ has a risk of order at least $\log(n)$, while the lower bound is of constant order for $\alpha \ge 2$. We discuss in Appendix B the possibility of estimating the position of vertex 1 better, namely using the rumor centroid. We conjecture this alternative method has a risk of optimal order for any $\alpha \ge 1$.

**Corollary 5.** Let $T \sim \text{URRT}$. For $\alpha = 1$

$$R_{\alpha}(\hat{\sigma}_J) \le (1 + o(1)) 1170 R_1^*$$

and for $\alpha \in (1, 2)$,

$$R_{\alpha}(\hat{\sigma}_J) \le (1 + o(1)) \left( \frac{1}{2-\alpha} + \frac{3}{(2-\alpha)^2} + \frac{1}{(2-\alpha)^3} \right) 70 R_{\alpha}^*.$$

*Proof of Theorem 4.* By the triangle inequality,

$$R_{\alpha}(\hat{\sigma}') \le \sum_{i=1}^{n} \mathbb{E} \left[ \frac{\hat{\sigma}'(i)}{i^{\alpha}} \right] + \sum_{i=1}^{n} \frac{i}{i^{\alpha}}.$$

Using the triangle inequality here is not tight and might explain why we obtain such a big gap between the lower and upper bounds. However, to get a more precise control of $|\hat{\sigma}'(i) - i|$, one must not only upper bound $\hat{\sigma}'(i)$ but prove its concentration around $i$. We did not reach this goal in this paper. Establishing concentration of $\hat{\sigma}'(i)$ around $i$ seems to be the natural way to make the upper bound tighter, as well as having more information about the quality of the descendant ordering (and thus Jordan ordering). Let $i \in [n]$ be a vertex of $T$. We first note that

$$\mathbb{E}[\hat{\sigma}'(i)] \le \mathbb{E} \left[ \sum_{j=1}^{n} 1_{\text{de}(j) \ge \text{de}(i)} \right]. \qquad (11)$$

Moreover, for any $\tau_{i,j} \in \mathbb{R}$,

$$\mathbb{P}\{\text{de}(j) \ge \text{de}(i)\} \le \mathbb{P}\left\{\frac{\text{de}(j)}{n} \ge \tau_{i,j}\right\} + \mathbb{P}\left\{\frac{\text{de}(i)}{n} \le \tau_{i,j}\right\}.$$

Therefore, we may upper bound (11) by

$$\mathbb{E}[\hat{\sigma}'(i)] \le i + 1 + \sum_{j>i+1} \mathbb{P}\left\{\frac{\text{de}(j)}{n} \ge \tau_{i,j}\right\} + \mathbb{P}\left\{\frac{\text{de}(i)}{n} \le \tau_{i,j}\right\}. \qquad (12)$$

Let $j > i + 1$ be a vertex of $T$. Note that the distributions of $\text{de}(i)$ and $\text{de}(j)$ in a URRT model follow a Pólya urn model. In particular, for any vertex $k \in [n]$,

$$\mathbb{P}\{k \in (T, 1)_j\} = \frac{de_{k-1}(j) + 1}{k-1},$$

and each connection of a new vertex to a descendant of $j$ is independent of the previous ones, conditionally on $\text{de}(j)$. Let $N_n := n - j$ and let $\tilde{W}_N = \text{de}(j)$ be the number of descendants of $j$ at time $n$. We
thus have that $\tilde{W}_N = \text{de}(j)$ follows a Pólya urn distribution, where the Pólya urn process has balls of two colours, it is started when $j$ is added to $T$, and it is run for a maximum number of steps $N_n$. From Mahmoud (2008, Section 3.2), we have that

$$ \mathbb{E}[\text{de}(j) + 1] = \frac{n}{j}, $$

and also that

$$ \mathbb{P}\{\text{de}(j) = k\} = \frac{k!(j-1)(j)\cdots(n-k-2)}{j(j+1)\cdots(n-1)} \binom{n-j}{k}. \quad (13) $$

In Appendix C, we derive from these formulas the following upper-bounds.

**Lemma 6.** $i \ge 2$ and $j > i + 1$, by choosing $\tau_{i,j} = \frac{1}{j} \log \frac{i}{i}$,

$$ \mathbb{P}\left\{\frac{\text{de}(j)}{n} \ge \tau_{i,j}\right\} + \mathbb{P}\left\{\frac{\text{de}(i)}{n} \le \tau_{i,j}\right\} \le 2e^2 e^{-\log \frac{i}{i}} + \frac{i}{j} \log \frac{j}{i} \le \frac{i}{j} \left(2e^2 + \log \frac{j}{i}\right), $$

and that for $i = 1, j > i + 1$, choosing $\tau_{1,j} = \frac{1}{j} \log(j)$,

$$ \mathbb{P}\left\{\frac{\text{de}(j)}{n} \ge \tau_{1,j}\right\} + \mathbb{P}\left\{\frac{\text{de}(1)}{n} \le \tau_{1,j}\right\} \le \frac{1}{j} \left(2e^2 + \log(j)\right) + \frac{1}{n-1}. $$

Once plugged into the expression of $R_\alpha$, for $n \ge 60$, this leads to (details in Appendix C)

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i} \right] \le 18n. $$

For $1 < \alpha < 2$, a similar computation yields (details in Appendix C)

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}} \right] \le \left( \frac{2}{2-\alpha} + \frac{2e^2}{(2-\alpha)^2} + \frac{2}{(2-\alpha)^3} \right) n^{2-\alpha}. $$

Lemma 3 concludes the proof for $1 < \alpha < 2$. The proof of the case $\alpha \ge 2$ lies at the end of Appendix C.

## 3. Preferential attachment tree

In this section, we consider the preferential attachment model and investigate the performance of the Jordan ordering procedure. Since the arguments have a similar structure to the URRT model analyzed in Section 2, we omit some details of the proofs and report them to the Appendices. Similarly to the previous section, we first prove a minimax lower bound for the risk of any label-invariant estimator.

### 3.1. A lower bound

**Theorem 7.** In the PA model, we have, for $\alpha > 0$ and $n \ge 300$

$$ R_{\alpha}^{*} \ge \frac{n^{2-\alpha}}{70}. $$
The proof is deferred to Appendix D.

**Remark 2.** As in the case of the URRT model, we have

$$R_{\alpha}^{*} \geq \frac{1}{2},$$

which improves on the result of Theorem 7 for $\alpha > 2$.

### 3.2. Performance of the Jordan ordering in the PA model

Similarly to Section 2.3, we establish upper bounds for $R_{\alpha}(\hat{\sigma}_{J})$. In a subsequent corollary, we bound the risk $R_{\alpha}(\hat{\sigma}_{J})$ in terms of the optimal risk $R_{\alpha}^{*}$.

**Theorem 8.** Let $T \sim \text{PA}$. Then, there exist positive constants $C$, $K$, such that for $\alpha \in [1, 3/2)$

$$R_{\alpha}(\hat{\sigma}_{J}) \leq K(\alpha)n^{2-\alpha} + K \sum_{i=1}^{n} \frac{1}{i^{\alpha}} + C \log^{2}(n)\sqrt{n},$$

where $K(\alpha) = \frac{2}{2-\alpha} + \frac{8\sqrt{2} + \frac{10}{\sqrt{2}}}{(3/2-\alpha)(2-\alpha)} + \frac{20}{\sqrt{2}(2-\alpha)(3/2-\alpha)^2}$. For $\alpha \geq 3/2$,

$$R_{\alpha}(\hat{\sigma}_{J}) \leq cn^{3/2},$$

where c is a positive constant.

Corollary 9 is a direct consequence of Theorems 7 and 8. It states that the Jordan ordering has a risk of optimal order for $\alpha \in [1, 3/2)$. Let us remark that, here, the boundary value 3/2 does not appear for the same reason as in the URRT case. In the URRT, the optimality result is limited to $\alpha < 2$ because of the error originating from the estimation of vertex 1. Here, the limitation to $\alpha < 3/2$ has a different origin than in the URRT model. Indeed, the descendant ordering is only order optimal for $\alpha < 3/2$, meaning that even if the position of vertex 1 was known, ordering vertices by the number of their descendants would not result in a risk bound that matches the lower bound for $\alpha \geq 3/2$.

**Corollary 9.** Let $T \sim \text{PA}$. For $\alpha \in [1, 3/2)$

$$R_{\alpha}(\hat{\sigma}_{J}) \leq (1 + o(1)) 70 \left( \frac{2}{2-\alpha} + \frac{8\sqrt{2} + \frac{10}{\sqrt{2}}}{(3/2-\alpha)(2-\alpha)} + \frac{20}{\sqrt{2}(2-\alpha)(3/2-\alpha)^2} \right) R_{\alpha}^{*}.$$

The proof of Theorem 8 is reported to Appendix F.

In this appendix we discuss some issues concerning the choice of the parameter $\alpha$ in the definition of the risk and ordering according to degrees. Some elements of the proofs for the URRT model are also reported here. The final sections contain the proofs of all results in the PA model.
## Appendix A: A remark on the choice of the risk

The risk $R_\alpha$ defined in (2) leads to a meaningful performance measure in the URRT and PA models only for some values of $\alpha$. In particular, for $\alpha < 1$, it is easy to see that the risk of a random permutation is of the same order as the established lower bound, both in the URRT and PA models. More precisely, let $\Sigma$ be a permutation chosen uniformly at random. Simple computation for $\alpha < 1$ leads to

$$R_{\alpha}(\Sigma) \leq c_{\alpha} n^{2-\alpha},$$

for some positive constant $c_\alpha$. On the other hand, Theorems 1 and 7 imply that for $\alpha < 1$, $R_\alpha^* \geq c_\alpha' n^{2-\alpha}$. Therefore, with $\alpha < 1$, the random ordering has a risk of the same order as that of the optimal one. This is why we restrict our analysis of the risk to $\alpha \geq 1$. Our analysis of the Jordan ordering proves that this method has a risk of optimal order for $\alpha \in [1, 2)$ in the URRT case and $\alpha \in [1, 3/2)$ in the PA tree.

It is also possible to change the risk by replacing $1/\sigma(i)^\alpha$ by $f(\sigma(i))$, for some non-increasing function $f$. An example is $f(t) = I_{\{t \leq \tau_n\}}$, for some threshold $\tau_n$. Such a risk measures the quality of the ordering on the first $\tau_n$ vertices only. For many choices of $f$, our analysis can be directly adapted However, for rapidly decreasing functions (such as the step function above), the Jordan ordering is not optimal up to a constant factor. This suggests that one should investigate methods that are better at ordering the early vertices.

## Appendix B: A remark on rumor centrality

We conjecture that in the URRT model, there exists an ordering procedure whose risk is of the order of $n^{2-\alpha}$ for any $\alpha \geq 1$, matching that of the minimax lower bound. Indeed, in our analysis, the risk is decomposed in two parts. First, a part coming from the difference between the Jordan and the descendant ordering (i.e, the error made by estimating the position of vertex 1 by the Jordan centre), second the risk of the descendant ordering. A possible way to improve our bound on the risk is to estimate the position of vertex 1 more precisely. To do so, using the rumor centrality appears to be a promising option. Indeed, due to recent results from Crane and Xu (2021), in the URRT model, the rumor centrality orders vertices by their likelihood of being vertex 1. In particular, using the rumor centrality is optimal for minimizing the size of a conficence set containing the root, outperforming Jordan centrality (Bubeck, Devroye and Lugosi (2017)). However, one step in the analysis is missing. Copying the proof of Lemma 3, with the rumor center instead of the Jordan center, one needs to bound the moment of order $1 + \gamma$ of the arrival time of the rumor centre. Bounding it by a constant (for any value of $\gamma$) would be sufficient to prove that this new ordering procedure has a risk of optimal order for any $\alpha \geq 1$.

## Appendix C: Proof of Theorem 4

Here, we present the arguments to complete the proof of Theorem 4. We recall that we need to upper bound $\sum_{i=1}^n \mathbb{E}[\frac{|\hat{\sigma}'(i)-i|}{i^\alpha}]$, and that we reduced in (12) the problem to upper bounding $\mathbb{P}\{\frac{de(j)}{n} \geq \tau_{i,j}\} + \mathbb{P}\{\frac{de(i)}{n} \leq \tau_{i,j}\}$, which is done in Lemma 6.

**Proof of Lemma 6.** From (13), we have

$$\mathbb{P}\{de(j) = k\} = \frac{k!(j-1)(j)\cdots(n-k-2)}{j(j+1)\cdots(n-1)} \binom{n-j}{k}.$$
Re-arranging the factors,

$$
\begin{align*}
\mathbb{P}\{\mathrm{de}(j) = k\} &= k! \frac{(n-k-2)!}{(j-2)!} \frac{(j-1)!}{(n-1)!} \frac{(n-j)!}{k!(n-j-k)!} \\
&= (j-1) \frac{(n-k-2)!}{(n-j-k)!} \frac{(n-j)!}{(n-1)!}
\end{align*}
$$

Since $j \ge 3$,

$$
\begin{align*}
\mathbb{P}\{\mathrm{de}(j) = k\} &= (j-1) \frac{(n-j-k+1)\cdots(n-k-2)}{(n-j+1)\cdots(n-1)} \\
&= \frac{j-1}{n-1} \frac{n-j-k+1}{n-j+1} \cdots \frac{n-k-2}{n-2} \\
&\le \frac{j-1}{n-1} \left(1 - \frac{k}{n-2}\right)^{j-2}.
\end{align*}
$$

Therefore, for $n, j \ge 3$, we can upper bound the second term of (12) by

$$
\begin{align*}
\mathbb{P}\left\{\frac{\mathrm{de}(j)}{n} \ge \tau_{i,j}\right\} &\le \sum_{(\tau_{i,j}n) \le k \le n} \frac{j-1}{n-1} \left(1-\frac{k}{n}\right)^{j-2} \\
&\le \frac{(j-1)n}{n-1} \int_{\tau_{-\frac{1}{n}}}^{1} (1-t)^{j-2} dt = \frac{n}{n-1} \left(1-\tau_{i,j} + \frac{1}{n}\right)^{j-1} \le 2e^2 e^{-j\tau_{i,j}},
\end{align*}
$$

using $\log(1+x) \le x$. Moreover, for $i \ge 2$, we bound the third term of (12) by

$$
\begin{align*}
\mathbb{P}\left\{\frac{\mathrm{de}(i)}{n} \le \tau_{i,j}\right\} &\le \sum_{k \in [1, \tau_{i,j}n]} \frac{i-1}{n-1} \left(1 - \frac{k}{n-2}\right)^{i-2} \\
&\le \tau_{i,j} i \left(1 - \frac{1}{n-2}\right)^{i-2} \le \tau_{i,j} i.
\end{align*}
$$

Since for $i = 1$, $\mathbb{P}\{\mathrm{de}(1) = k\} = 1/(n-1)$,

$$
\mathbb{P}\left\{\frac{\mathrm{de}(1)}{n} \le \tau_{i,j}\right\} \le \sum_{k \in [1, \tau_{i,j}n]} \frac{1}{n-1} \le \tau_{i,j} + \frac{1}{n-1}.
$$

Therefore, for $i \ge 2$ and $j > i + 1$, by choosing $\tau_{i,j} = \frac{1}{j} \log \frac{j}{i}$, we obtain that

$$
\mathbb{P}\left\{\frac{\mathrm{de}(j)}{n} \ge \tau_{i,j}\right\} + \mathbb{P}\left\{\frac{\mathrm{de}(i)}{n} \le \tau_{i,j}\right\} \le 2e^2 e^{-\log \frac{i}{j}} + \frac{i}{j} \log \frac{j}{i} \le \frac{i}{j} \left(2e^2 + \log \frac{j}{i}\right),
$$

and for $i = 1, j > i + 1$, choosing $\tau_{1,j} = \frac{1}{j} \log(j)$ we obtain that

$$
\mathbb{P}\left\{\frac{\mathrm{de}(j)}{n} \ge \tau_{1,j}\right\} + \mathbb{P}\left\{\frac{\mathrm{de}(1)}{n} \le \tau_{1,j}\right\} \le \frac{1}{j}\left(2e^2 + \log(j)\right) + \frac{1}{n-1}.
$$

□
Plugging the upper-bounds of Lemma 6 in (12), for $\alpha = 1$, we get

$$ 
\begin{aligned}
\sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i} \right] &\le n + \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i)|}{i} \right] \\
&\le n + \sum_{i=2}^{n} \frac{1}{i} \left( i + 1 + \sum_{j=i+2}^{n} \frac{i}{j} \left( 2e^2 + \log \frac{j}{i} \right) \right) + 2 + \sum_{j=3}^{n} \left( \frac{1}{j} (2e^2 + \log(j)) + \frac{1}{n-1} \right) \\
&\le 2n + 3 + \log(n) + \sum_{j=3}^{n} \frac{1}{j} \sum_{i=1}^{j-2} \left( 2e^2 + \log \frac{j}{i} \right).
\end{aligned} 
\quad (14) $$

Since

$$ \sum_{i=1}^{j-2} \log \frac{j}{i} \le \log \left( \frac{j^j}{j!} \right), $$

and that the Stirling formula implies that $j! \ge (j/3)^j$,

$$ \sum_{i=1}^{j-2} \log \frac{j}{i} \le j \log(3). $$

Plugging this in (14) yields

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i} \right] \le 3 + \log(n) + (2 + 2e^2 + \log 3)n, $$

which in turn proves that for $n \ge 60$,

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i} \right] \le 18n. $$

For $1 < \alpha < 2$, a similar calculation yields

$$ 
\begin{aligned}
\sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i^\alpha} \right] &\le \frac{1}{2-\alpha} n^{2-\alpha} + \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i)|}{i^\alpha} \right] \\
&\le \frac{1}{2-\alpha} n^{2-\alpha} + 1 + \sum_{i=1}^{n} \frac{1}{i^\alpha} \left( i + 1 + \sum_{j=i+2}^{n} \frac{i}{j} \left( 2e^2 + \log \frac{j}{i} \right) \right) \\
&\le \frac{2}{2-\alpha} n^{2-\alpha} + 1 + \zeta(\alpha) + \sum_{j=3}^{n} \frac{1}{j} \sum_{i=1}^{j-2} \frac{2e^2}{i^{\alpha-1}} + \frac{1}{i^{\alpha-1}} \log \frac{j}{i} \\
&\le \frac{2}{2-\alpha} n^{2-\alpha} + 1 + \zeta(\alpha) + \frac{2e^2}{(2-\alpha)^2} n^{2-\alpha} + \sum_{j=3}^{n} \frac{1}{j} \sum_{i=1}^{j-2} \frac{1}{i^{\alpha-1}} \log \frac{j}{i}.
\end{aligned} 
$$
Recall that $\zeta$ denotes the Riemann zeta function. We may upper bound

$$ \sum_{i=1}^{j-2} \frac{1}{i^{\alpha-1}} \log \frac{j}{i} \le 2 \int_{1}^{j} \frac{1}{t^{\alpha-1}} \log \left( \frac{j}{t} \right) , $$

which in turn can be evaluated by integration by parts, leading to

$$ \sum_{i=1}^{j-2} \frac{1}{i^{\alpha-1}} \log \frac{j}{i} \le \frac{2}{(2-\alpha)^2} j^{2-\alpha} . $$

Finally

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}} \right] \le \left( \frac{2}{2-\alpha} + \frac{2e^2}{(2-\alpha)^2} + \frac{2}{(2-\alpha)^3} \right) n^{2-\alpha} . $$

For $\alpha \ge 2$, we similarly get

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}} \right] \le C, \qquad (15) $$

for some positive constant $C$.

# Appendix D: Proof of the minimax lower bound in the PA model

Here we prove Theorem 7

**Proof.** The proof follows the same argument as that of Theorem 1. It suffices to check that the event

$$ \Omega_j := \{ \tau(j) \text{ and } \tau(\lfloor n/4 \rfloor + j) \text{ are leaves, connected to vertices of rank in } \lfloor n/2 \rfloor \} $$

has a probability bounded away from 0. Proceeding as in the proof of Theorem 1, we get

$$ \begin{align*} \mathbb{P}\{\Omega_j\} &= \frac{2(\lfloor n/2 \rfloor - 1)}{2(j-2)} \prod_{k=j+1}^{\lfloor n/4 \rfloor + j-1} \frac{2k-3}{2(k-1)} \frac{2(\lfloor n/2 \rfloor - 1)}{2(\lfloor n/4 \rfloor + j-2)} \prod_{k=\lfloor n/4 \rfloor + j+1}^{n} \frac{2k-4}{2(k-1)} \\ &= \frac{(\lfloor n/2 \rfloor - 1)}{(j-2)} \frac{2j-1}{2(\lfloor n/4 \rfloor + j-2)} \frac{(\lfloor n/2 \rfloor - 1)}{(\lfloor n/4 \rfloor + j-2)} \frac{(\lfloor n/4 \rfloor + j-1)(\lfloor n/4 \rfloor + j)}{(n-1)(n-2)} \\ &= \frac{(\lfloor n/2 \rfloor - 1)^2}{(n-1)(n-2)} \frac{2j-1}{2j-4} \frac{(\lfloor n/4 \rfloor + j-1)(\lfloor n/4 \rfloor + j)}{(\lfloor n/4 \rfloor + j-2)^2} \\ &\ge \frac{1}{4} \left(1 - \frac{5}{n}\right)^5 . \end{align*} $$

□
Appendix E: Descendant ordering in the PA model

Here, we analyze the descendant ordering in the PA model. Recall the notation introduced in Section 2.2: the centrality measure $\psi'(u) = n + 1 - \mathrm{de}(u)$, and the corresponding ordering $\hat{\sigma}'$. In the next lemma we prove that $\psi'$ and $\psi$ coincide for most vertices and provide a control both on the number of vertices for which they differ and the estimated arrival time of vertex 1.

**Lemma 10.** Let $c$ be the rank of a Jordan's centroid, and let $\{1 \to c\}$ be the set of vertices on the path from the root to the centroid. Then

* $\forall v \in [n]\setminus\{1 \to c\}, \psi_T(v) = \psi'_T(v)$;

* there exists an universal constant $K$ such that $c$ is stochastically dominated by an exponential random variable with parameter $K$;

* for any $\epsilon > 0$, with probability at least $1 - \epsilon$

$$ \hat{\sigma}_J(1) \le \frac{C}{\epsilon^2} \exp\left(\sqrt{C \log\left(\frac{1}{\epsilon}\right)}\right). $$

**Proof.** The first part of the proof is identical to the proof of Lemma 2. First, we use Theorem 6 of Durant and Wagner (2019), which extend the result of Moon (2002) from uniform random recursive trees to preferential attachment trees. Using their result, we obtain that

$$ \mathbb{P}\{c \ge k\} \le \sum_{j=k}^{\infty} \frac{(-\log(2)/2)^j}{j!}, $$

so there exists an exponential random variable of parameter $K$ such that $c \le \mathcal{E}(K)$. Using Corollary 3.3.b of Banerjee and Bhamidi (2022), we have that the event

$$ \hat{\sigma}_J(1) \le \frac{C}{\epsilon^2} \exp\left(\sqrt{C \log\left(\frac{1}{\epsilon}\right)}\right), $$

holds with probability at least $1 - \epsilon$. This concludes the proof of the lemma. $\square$

The next lemma allows us to compare the risk of Jordan and descendant ordering.

**Lemma 11.** Let $T \sim \mathrm{PA}$. Then, there exist positive constants $C, K$, such that, for $\alpha > 0$

$$ R_{\alpha}(\hat{\sigma}_J) \le R_{\alpha}(\hat{\sigma}') + K \sum_{i=1}^{n} \frac{1}{i^{\alpha}} + C \log^2(n) \sqrt{n}. $$

**Proof.** The proof is similar to the one of Lemma 3, using the same coupling between the Jordan and descendant ordering. Recalling that $D$ is the distance between vertices 1 and $c$, we have

$$ \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \frac{|\hat{\sigma}_J(i) - i|}{i^{\alpha}}\right] \le \mathbb{E}\left[\sum_{i \in \{1 \to c\}} i\right] + \mathbb{E}\left[\sum_{i \in \{1 \to c\}} \hat{\sigma}_J(i)\right] $$
$$ \leq \frac{1}{2} \mathbb{E}[D^2] + \mathbb{E}[D\hat{\sigma}_J(1)]. $$

As in Lemma 3, we use the fact that $D \leq c$ and the domination of $c$ by an exponential random variable (see Lemma 10) to get that

$$ \frac{1}{2} \mathbb{E}[D^2] \leq K^2. $$

Then, it follows from Hölder's inequality that

$$ \mathbb{E}[D\hat{\sigma}_J(1)] \leq \left(\mathbb{E}\left[D^{\frac{1+\gamma}{\gamma}}\right]\right)^{\frac{\gamma}{1+\gamma}} \left(\mathbb{E}\left[\hat{\sigma}_J(1)^{1+\gamma}\right]\right)^{\frac{1}{1+\gamma}}. \quad (16) $$

Using once again the domination of $D$ by an exponential random variable,

$$ \left(\mathbb{E}\left[D^{\frac{1+\gamma}{\gamma}}\right]\right)^{\frac{\gamma}{1+\gamma}} \leq C \frac{1}{1+\gamma}\gamma, $$

for some positive constant $C$. Next, using Lemma 10,

$$ \mathbb{P}\{\hat{\sigma}_J(1) \geq f(\epsilon)\} \leq \epsilon, $$

where $f(\epsilon) = \frac{C}{\epsilon^2} \exp\left(\sqrt{C \log\left(\frac{1}{\epsilon}\right)}\right)$. The function $f$ is a non-increasing, therefore $f\left(\frac{C}{\sqrt{k}} \exp\left(\sqrt{C \log(k)}\right)\right) \leq k$. So

$$ \mathbb{P}\{\hat{\sigma}_J(1) \geq k\} \leq \frac{C}{\sqrt{k}} \exp\left(\sqrt{C \log(k)}\right). $$

Following the same steps as in Lemma 3, and choosing $\gamma = 1/\log(n)$, yields

$$ \mathbb{E}[D\hat{\sigma}_J(1)] \leq C \log^2(n) \sqrt{n}, $$

which concludes the proof of the lemma. $\square$

<figure><img src="image_5.png" /></figure>

# Appendix F: Performance of Jordan ordering in the PA model

In this section we prove Theorem 8.

**Proof.** Similarly to the URRT case, in the PA model, the number of descendants of a vertex is distributed as a Pólya urn. This well-known fact is easily seen since in the PA model, sampling a vertex with a probability proportional to its degree is the same as sampling an edge uniformly at random and picking one of its endpoints at random. In turn, it is the same as picking a half edge uniformly at random. Therefore, the resulting Pólya urn has slightly different initial conditions than in the URRT. Such Pólya urns are well understood. In particular, by Mahmoud (2008, Section 3.2), for a vertex $i \in [n]$, the distribution of $\text{de}(i)$ is given by

$$ \mathbb{P}\{\text{de}(i) = k\} = \frac{(13 \cdots (2k-1)) ((2i-3)(2i-1) \cdots (2n-2k-5))}{(2i-2)2i \cdots (2n-4)} \binom{n-i}{k}. $$
Re-arranging the terms in the above expression,

$$ \mathbb{P}\{\mathrm{de}(i) = k\} = \underbrace{\frac{1 \cdot 3 \cdots (2k-1)}{k!}}_{\stackrel{\mathrm{def}}{=} A} \cdot \underbrace{\frac{(2i-3)(2i-1)\cdots(2n-5)}{(2i-2)2i\cdots(2n-4)}}_{\stackrel{\mathrm{def}}{=} B} \cdot \underbrace{\frac{(n-i)!/(n-i-k)!}{(2n-2k-3)(2n-2k-1)\cdots(2n-5)}}_{\stackrel{\mathrm{def}}{=} C} \quad (17) $$

We bound each term on the right-hand side of (17). First, for $k \ge 1$,

$$ A = \frac{1}{k} \prod_{j=1}^{k-1} \frac{2j+1}{j} = \frac{2^{k-1}}{k} \prod_{j=1}^{k-1} \left(1 + \frac{1}{2j}\right). $$

Since

$$ \prod_{j=1}^{k-1} \left(1 + \frac{1}{2j}\right) = \exp\left(\sum_{j=1}^{k-1} \log\left(1 + \frac{1}{2j}\right)\right) \le \exp\left(\sum_{j=1}^{k-1} \frac{1}{2j}\right) \le \sqrt{k}, $$

then,

$$ A \le \frac{2^{k-1}}{\sqrt{k}}. $$

Second, we have

$$ \begin{aligned} B &= \prod_{j=i}^{n-1} \frac{2j-3}{2j-2} = \prod_{j=i}^{n-1} \left(1 - \frac{1}{2j-2}\right) \\ &= \exp\left(\sum_{j=i}^{n-1} \log\left(1 - \frac{1}{2j-2}\right)\right) \le \exp\left(-\sum_{j=i}^{n-1} \frac{1}{2j-2}\right) \le 2\sqrt{\frac{i}{n}}. \end{aligned} $$

Finally, we have that

$$ C = \prod_{j=n-k-2}^{n-3} \frac{j-i-3}{2j+1} = \frac{1}{2^{k-1}} \prod_{j=n-k-2}^{n-3} \left(1 - \frac{i+2.5}{j+0.5}\right) \le \frac{1}{2^{k-2}} \left(1 - \frac{k}{n}\right)^i. $$

Plugging these bounds into (17), we get, for any $k \ge 1$,

$$ \mathbb{P}\{\mathrm{de}(i) = k\} \le 4\sqrt{\frac{i}{kn}}\left(1 - \frac{k}{n}\right)^i. $$

Since $\mathbb{P}\{\mathrm{de}(i) = 0\} = (i-1)/(n-1)$, for any $\tau > 0$,

$$ \mathbb{P}\left\{\frac{\mathrm{de}(i)}{n} \le \tau\right\} \le \frac{i}{n} + \sum_{k=1}^{\lfloor n\tau \rfloor} 4\sqrt{\frac{i}{kn}} \le \frac{i}{n} + 4\sqrt{i} \int_{0}^{\tau} \frac{1}{\sqrt{t}} dt \le \frac{i}{n} + 8\sqrt{i\tau}. $$
Since $i/n \le 2\sqrt{i\tau}$ (because we choose $\tau \ge 1/(2n)$, see hereafter), we get

$$ \mathbb{P}\left\{\frac{\mathrm{de}(i)}{n} \le \tau\right\} \le 10\sqrt{i\tau}. \qquad (18) $$

Now, for $j \in [n]$, we have

$$ \begin{aligned} \mathbb{P}\left\{\frac{\mathrm{de}(j)}{n} \ge \tau\right\} &\le \sum_{k=[n\tau]}^{n} 4\sqrt{\frac{j}{kn}}\left(1-\frac{k}{n}\right)^j \le 4\sqrt{\frac{j}{\tau}}\sum_{k=[n\tau]}^{n} \frac{1}{n}\left(1-\frac{k}{n}\right)^j \\ &\le 4\sqrt{\frac{j}{\tau}}\int_{\frac{[n\tau]-1}{n}}^{1} (1-t)^j dt \le \frac{4}{\sqrt{j\tau}}\left(1-\frac{n\tau-1}{n}\right)^j. \end{aligned} \qquad (19) $$

We set $\tau = \frac{1+\log(j/i)}{2j}$. Plugging it in (18) leads to

$$ \mathbb{P}\left\{\frac{\mathrm{de}(i)}{n} \le \tau\right\} \le 10\sqrt{\frac{i}{2j}}\sqrt{1+\log(j/i)}, $$

and plugging it in (19) we get

$$ \begin{aligned} \mathbb{P}\left\{\frac{\mathrm{de}(j)}{n} \ge \tau\right\} &\le 4\sqrt{2}\exp\left(j\log\left(1-\frac{n\tau-1}{n}\right)\right) \\ &\le 4\sqrt{2}\exp\left(\frac{-\log(j/i)}{2}\right)\exp\left(-j\frac{\frac{n}{2j}-1}{n}\right) \\ &\le 8\sqrt{2}\sqrt{\frac{i}{j}}. \end{aligned} $$

Summing these two bounds, we get

$$ \mathbb{P}\{\mathrm{de}(i) \le \mathrm{de}(j)\} \le \left(8\sqrt{2} + \frac{10}{\sqrt{2}}\sqrt{1 + \log(j/i)}\right) \sqrt{\frac{i}{j}}. $$

Following similar calculations as in Section 2.3 and Appendix C,

$$ \begin{aligned} \sum_{i=1}^{n} \mathbb{E}\left[\frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}}\right] &\le \frac{1}{2-\alpha}n^{2-\alpha} + \sum_{i=1}^{n} \frac{1}{i^{\alpha}}\left(i + \sum_{j=i+1}^{n}\left(8\sqrt{2} + \frac{10}{\sqrt{2}} + \frac{10}{\sqrt{2}}\log(j/i)\right)\sqrt{\frac{i}{j}}\right) \\ &\le \frac{2}{2-\alpha}n^{2-\alpha} + \sum_{j=1}^{n}\left(\frac{1}{\sqrt{j}}\sum_{i=1}^{j-1}\left(8\sqrt{2} + \frac{10}{\sqrt{2}} + \frac{10}{\sqrt{2}}\log(j/i)\right)i^{1/2-\alpha}\right). \end{aligned} $$

For $\alpha \in [1, 3/2)$ we obtain

$$ \sum_{i=1}^{n} \mathbb{E}\left[\frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}}\right] \le \left(\frac{2}{2-\alpha} + \frac{8\sqrt{2} + \frac{10}{\sqrt{2}}}{(3/2-\alpha)(2-\alpha)} + \frac{20}{\sqrt{2}(2-\alpha)(3/2-\alpha)^2}\right)n^{2-\alpha}, $$
while for $\alpha \ge 3/2$

$$ \sum_{i=1}^{n} \mathbb{E} \left[ \frac{|\hat{\sigma}'(i) - i|}{i^{\alpha}} \right] \le C n^{3/2}, $$

for some positive constant C. This concludes the proof of Theorem 8. □

## Funding

Simon Briend acknowledges the support of Région Ile de France. Christophe Giraud acknowledges partial support by grant ANR-19-CHIA-0021-01 (BiSCottE, ANR) and by grant ANR-21-CE23-0035 (AS-CAI, ANR and DFG). Gábor Lugosi acknowledges the support of Ayudas Fundación BBVA a Proyectos de Investigación Científica 2021 and the Spanish Ministry of Economy and Competitiveness grant PID2022-138268NB-I00, financed by MCIN/AEI/10.13039/501100011033, FSE+MTM2015-67304-P, and FEDER, EU.).

## Supplementary Material

### Simulations

In the Supplementary Material, we first report a numerical illustration of our theoretical results on trees generated from the URRT and PA models. Then, we compare the performance of the Jordan ordering to other ordering procedures. For computational reasons, we display results for the descendant ordering procedure.

## References

* BANERJEE, S. and BHAMIDI, S. (2021). Persistence of hubs in growing random networks. Probab. Theory Related Fields 180 891–953. https://doi.org/10.1007/s00440-021-01066-0 MR4288334

* BANERJEE, S. and BHAMIDI, S. (2022). Root finding algorithms and persistence of Jordan centrality in growing random trees. Ann. Appl. Probab. 32 2180–2210. https://doi.org/10.1214/21-aap1731 MR4430011

* BRADLEY, R. A. and TERRY, M. E. (1952). Rank analysis of incomplete block designs. I. The method of paired comparisons. Biometrika 39 324–345. https://doi.org/10.2307/2334029 MR70925

* BRANDENBERGER, A. M., DEVROYE, L. and GOH, M. K. (2022). Root estimation in Galton-Watson trees. Random Structures Algorithms 61 520–542. https://doi.org/10.1002/rsa.21072 MR4474211

* BRIEND, S., CALVILLO, F. and LUGOSI, G. (2023). Archaeology of random recursive dags and Cooper-Frieze random networks. Combin. Probab. Comput. 32 859–873. https://doi.org/10.1017/s0963548323000184 MR4653727

* BRIEND, S., GIRAUD, C., LUGOSI, G. and SULEM, D. (2024). Supplementary Material for "Estimating the history of a random recursive tree".

* BUBECK, S., DEVROYE, L. and LUGOSI, G. (2017). Finding Adam in random growing trees. Random Structures Algorithms 50 158–172. https://doi.org/10.1002/rsa.20649 MR3607120

* BUBECK, S., ELDAN, R., MOSSEL, E. and RÁCZ, M. Z. (2017). From trees to seeds: on the inference of the seed from large trees in the uniform attachment model. Bernoulli 23 2887–2916. https://doi.org/10.3150/16-BEJ831 MR3648049

* CANTWELL, G. T., ST-ONGE, G. and YOUNG, J.-G. (2019). Recovering the past states of growing trees. arXiv preprint arXiv:1910.04788. https://doi.org/10.48550/arXiv.1910.04788
CONTAT, A., CURIEN, N., LACROIX, P., LASALLE, E. and RIVOIRARD, V. (2024). Eve, Adam and the preferential attachment tree. *Probab. Theory Related Fields* **190** 321–336. https://doi.org/10.1007/s00440-023-01253-1 MR4797370

CRANE, H. and XU, M. (2021). Inference on the history of a randomly growing tree. *J. R. Stat. Soc. Ser. B. Stat. Methodol.* **83** 639–668. https://doi.org/10.1111/rssb.12428 MR4319997

CRANE, H. and XU, M. (2023). Root and community inference on latent network growth processes using noisy attachment models. *J. R. Stat. Soc. Ser. B. Stat. Methodol.* https://doi.org/10.48550/arXiv.2107.00153

DEVROYE, L. and REDDAD, T. (2019). On the discovery of the seed in uniform attachment trees. *Internet Math.* 1–29. https://doi.org/10.24166/im.02.2019 MR3934290

DURANT, K. and WAGNER, S. (2019). On the centroid of increasing trees. *Discrete Math. Theor. Comput. Sci.* **21** 1–29. https://doi.org/10.23638/DMTCS-21-4-8 MR4001939

GILBERT, E. N. (1961). Random plane networks. *J. Soc. Indust. Appl. Math.* **9** 533–543. MR132566

GIRAUD, C., ISSARTEL, Y. and VERZELEN, N. (2023). Localization in 1D non-parametric latent space models from pairwise affinities. *Electron. J. Stat.* **17** 1587–1662. https://doi.org/10.1214/23-ejs2134 MR4612174

HAIGH, J. (1970). The recovery of the root of a tree. *J. Appl. Probability* **7** 79–88. https://doi.org/10.1017/s0021900200026954 MR253434

JANSSEN, J. and SMITH, A. (2022). Reconstruction of line-embeddings of graphons. *Electron. J. Stat.* **16** 331–407. https://doi.org/10.1214/21-ejs1940 MR4361745

JOG, V. and LOH, P.-L. (2017). Analysis of centrality in sublinear preferential attachment trees via the Crump-Mode-Jagers branching process. *IEEE Trans. Network Sci. Eng.* **4** 1–12. https://doi.org/10.1109/TNSE.2016.2622923 MR3625951

JOG, V. and LOH, P.-L. (2018). Persistence of centrality in random growing trees. *Random Structures Algorithms* **52** 136–157. https://doi.org/10.1002/rsa.20726 MR3731614

LUGOSI, G. and PEREIRA, A. S. (2019). Finding the seed of uniform attachment trees. *Electron. J. Probab.* **24** 1–15. https://doi.org/10.1214/19-EJP268 MR3925458

MAGNER, A. N., SREEDHARAN, J. K., GRAMA, A. Y. and SZPANKOWSKI, W. (2018). Times: Temporal information maximally extracted from structures. In *Proceedings of the 2018 World Wide Web Conference* 389–398. https://doi.org/10.1145/3178876.3186105

MAHMOUD, H. (2008). *Pólya urn models*. Chapman and Hall/CRC. https://doi.org/10.1201/9781420059847

MOON, J. W. (2002). On the centroid of recursive trees. *Australas. J. Combin.* **25** 211–219. MR1884048

NAVLAKHA, S. and KINGSFORD, C. (2011). Network archaeology: uncovering ancient networks from present-day interactions. *PLoS Comput. Biol.* **7** 1–16. https://doi.org/10.1371/journal.pcbi.1001119 MR2805381

RECANATI, A., BRÜLS, T. and D'ASPREMONT, A. (2017). A spectral algorithm for fast de novo layout of uncorrected long nanopore reads. *Bioinformatics* **33** 3188–3194. https://doi.org/10.1093/bioinformatics/btx370

RECANATI, A., KERDREUX, T. and D'ASPREMONT, A. (2018). Reconstructing latent orderings by spectral clustering. *arXiv preprint arXiv:1807.07122*. https://doi.org/10.48550/arXiv.1807.07122

ROBINSON, W. S. (1951). A method for chronologically ordering archaeological deposits. *American antiquity* **16** 293–301. https://doi.org/10.2307/276978

SHAH, D. and ZAMAN, T. (2011). Rumors in a network: who's the culprit? *IEEE Trans. Inform. Theory* **57** 5163–5181. https://doi.org/10.1109/TIT.2011.2158885 MR2849111

SHAH, D. and ZAMAN, T. (2016). Finding rumor sources on random trees. *Oper. Res.* **64** 736–755. https://doi.org/10.1287/opre.2015.1455 MR3515208

SREEDHARAN, J. K., MAGNER, A., GRAMA, A. Y. and SZPANKOWSKI, W. (2019). Inferring Temporal Information from a Snapshot of a Dynamic Network. *Scientific Reports* **9**, https://doi.org/10.1038/s41598-019-38912-0

YOUNG, J.-G., ST-ONGE, G., LAURENCE, E., MURPHY, C., HÉBERT-DUFRESNE, L. and DESROSIERS, P. (2019). Phase transition in the recoverability of network history. *Physical Review X* **9**, 041056. https://doi.org/10.1103/PhysRevX.9.041056