Correlated uniform attachment trees Johannes Bäumler, Miklós Z. Rácz, Nathan Ross, Anirudh Sridhar Abstract We introduce and study a new model of correlated uniform attachment (UA) trees, where correlation is sprinkled throughout the time evolution of the process. In this model, two UA trees are grown in parallel, and at each time step a new node is added to each tree, with an edge between it and a uniformly chosen existing vertex in the respective tree. The two choices of attachment are correlated: with probability α \alpha , the edges attach to nodes with the same time label in both trees, and with probability 1 − α 1-\alpha , the choices are made independently. We study fundamental detection and estimation questions for this model, given two unlabeled trees. In our main result, we construct a consistent estimator of the correlation parameter α \alpha , as the size of the trees goes to infinity. The construction of our statistic relies on two key ideas. First, we use Jordan centrality to identify subsets of vertices of each tree whose intersection has a sufficient number of common early vertices. The second idea is that, across multiple time scales, it is possible to approximately determine the labels of vertices that have attached to these early vertices, using the sizes of fringe subtrees. Our analysis includes novel quantitative bounds on the fraction of early vertices that remain central, which are of independent interest in the network archaeology literature. 1 Introduction and overview Networks arise naturally in a number of fields, such as protein-protein networks in biology, social networks in sociology, and power grids in engineering, just to name a few. Motivated by understanding such data, there has been an enormous effort over the last decades to define and study the properties of random networks for the purpose of inference. Modern introductions to this literature include the texts Barbour and Reinert 2026 , Newman 2018 , van der Hofstad 2017 ; van der Hofstad 2024 . Increasingly, important settings involve not only a single network but multiple networks which are correlated. Motivating applications include data privacy in social networks ( Narayanan and Shmatikov 2009 ) and inferring function in biological networks ( Singh et al. 2008 ) . Detecting correlation among the networks and estimating aspects of the correlated structure, such as latent matchings of the vertices across networks, are central questions. Inspired by these applications and questions, the past decade has seen an explosion of exciting work on correlated random graphs. Initially, these focused on the simplest such model, namely correlated Erdős–Rényi random graphs, introduced by Pedarsani and Grossglauser 2011 , which already exhibits interesting phenomena and presents significant technical challenges. By now, there is a fairly comprehensive understanding of the main questions for this model, including information-theoretic limits and algorithms for detection and estimation, due to the combined efforts of many works, including Cullina and Kiyavash 2016 ; Cullina and Kiyavash 2018 , Ding et al. 2021 , Ganassali and Massoulié 2020 , Ganassali et al. 2021 Ganassali et al. 2024a , Wu et al. 2022 ; Wu et al. 2023 , Mao et al. 2023a , Mao et al. 2023b ; Mao et al. 2024 , Ganassali et al. 2024b , Ding and Du 2023a ; Ding and Du 2023b , Ding et al. 2025a . An important research direction is to broaden the understanding of these questions by studying them on more realistic models of correlated random graphs, beyond Erdős–Rényi. While correlated stochastic block models have been explored substantially ( Lyzinski et al. 2015 , Onaran et al. 2016 , Lyzinski 2018 , Rácz and Sridhar 2021 , Gaudio et al. 2022 , Yang et al. 2023 , Yang and Chung 2023 , Chai and Rácz 2024 , Rácz and Zhang 2024 , Chen et al. 2026a ; Chen et al. 2026b ), models with other structure have received relatively little attention so far. The few examples include correlated randomly growing graphs ( Rácz and Sridhar 2022 ) , correlated random geometric graphs ( Wang et al. 2022 ) , correlated inhomogeneous random graphs ( Rácz and Sridhar 2023 ; Ding et al. 2025b ; Ameen and Hajek 2024 ) , and models with power-law degree distributions ( Korula and Lattanzi 2014 ; Yu et al. 2021 ) . In this paper, we contribute to this line of research by introducing and studying a novel model of correlated randomly growing graphs. The main feature of this model is that correlation is sprinkled throughout the time evolution of the process. This feature makes the model substantially different from the one studied by Rácz and Sridhar 2022 , which is a change-point model where two graphs initially grow together and subsequently grow independently. We focus our attention on correlated uniform attachment (UA) trees , which is arguably the simplest setting of such a model. We study fundamental detection and estimation questions in this new model of correlated UA trees. Our first result shows that correlated UA trees can be distinguished from independent ones with probability tending to one as the size of the trees goes to infinity; see Theorem 1.1 . Our main result goes a step further and shows that the level of correlation can be consistently estimated asymptotically; see Theorem 1.2 . In the spirit of other results in this area, our proofs rely on (rough) vertex matching, both for early-arriving vertices and for late-arriving vertices. Approximately matching early vertices is closely connected to a thread of recent work on network archaeology , which focuses on recovering parts of the past history (e.g., the root or early vertices) of a growing tree/graph given an unlabeled snapshot at a particular time. While the network archaeology literature has developed significantly over the past decade (see, e.g., Bubeck et al. 2015 , Curien et al. 2015 , Bubeck et al. 2017a , Bubeck et al. 2017b , Jog and Loh 2017 ; Jog and Loh 2018 , Lugosi and Pereira 2019 , Devroye and Reddad 2019 , Banerjee and Bhamidi 2022 , Briend et al. 2023 , Contat et al. 2024 , Briend et al. 2025 , Addario-Berry et al. 2024 ), the existing results are insufficient for our purposes (see Section 1.2 for details). Thus, as a key component in our proofs, we prove a novel result that is of independent interest in network archaeology: we quantify in UA trees the size of the intersection of the earliest vertices and the most central vertices (measured according to Jordan centrality); see Theorem 1.5 . 1.1 The model and results An unlabeled uniform attachment ( \mathrm{UA} ) tree sequence (T_{n})_{n\geq 0} is constructed sequentially by adding one vertex with an edge at each time step. Initially, T_{0} consists of a single node, and, given T_{n} , T_{n+1} is constructed by adding a single node with an edge connected to a node of T_{n} chosen uniformly at random. Distributionally we write T_{n}\sim\mathrm{UA}(n) . It is also natural to consider a labeled model, where the label of a vertex is the time of its arrival: the initial vertex has label 0 and the vertex added at step n is labeled n . We introduce and study a model of two correlated \mathrm{UA} tree sequences (T_{n}^{1},T_{n}^{2})_{n\geq 0} . The model has a single parameter \alpha\in[0,1] , which measures the amount of dependence between the two trees. The two trees are grown sequentially together, and marginally they are both UA trees, but the edge choices at each time step are correlated. Specifically, at each time step, with probability \alpha the edge choices are aligned , and with probability 1-\alpha they are independent , defined as follows: • Aligned choice: the two new nodes connect to a node in their respective trees with the same time label, chosen uniformly at random. That is, at time step n , choose i\in\{0,1,\ldots,n-1\} uniformly at random, and in both trees node n connects to node i . • Independent choice: the two new nodes make edge choices in their respective trees independently. That is, at time step n , choose i_{1},i_{2}\in\{0,1,\ldots,n-1\} independently and uniformly at random, in the first tree node n connects to node i_{1} and in the second tree node n connects to node i_{2} . Figure 1: An illustration of one step in the model. Before this step, the two trees with nodes \{0,1,\ldots,5\} are in black. Subsequently, a new node, labeled 6 , is added to both trees. The edge choices in the two trees are correlated, as follows. With probability \alpha , the two new nodes connect to a node in their respective trees with the same time label, chosen uniformly at random ( aligned choice , illustrated on the left). With probability 1-\alpha , the two new nodes make edge choices in their respective trees independently ( independent choice , illustrated on the right). The model is illustrated in Figure 1 . The time labels are an essential part of the definition of this model of correlated UA trees. Marginally, T_{n}^{1} and T_{n}^{2} are both uniform attachment trees, and they are correlated through the “aligned choice” steps in their time evolution, where the time labels play a central role. Nonetheless, since our focus is on inference problems given two such trees without knowledge of the time labels, in what follows we write \left(T_{n}^{1},T_{n}^{2}\right)\sim\alpha{\text{-}}\mathrm{CUA}\left(n\right) for a pair of unlabeled \mathrm{UA} trees constructed in this way. When \alpha=0 , the two trees are independent—we also write \mathrm{UA}(n)^{\otimes 2} for 0{\text{-}}\mathrm{CUA}(n) —and when \alpha=1 , we have T_{n}^{1}=T_{n}^{2} . Thus \alpha\in[0,1] quantifies the amount of dependence between the two trees. Given this model, a natural first question is whether it is possible to asymptotically distinguish between a pair of trees generated according to \alpha{\text{-}}\mathrm{CUA}(n) for \alpha>0 and an independent pair of \mathrm{UA}(n) trees. An inherent difficulty in this problem (and subsequent estimation problems) is that the data consists of an unlabeled pair of trees; while the “aligned choice” step aligns the choices of nodes in terms of labels , such a step may actually make the pair of unlabeled trees go further apart . 1 1 1 As an example, consider n=2 , let T_{2}^{1} and T_{2}^{2} both be paths on the node set \{0,1,2\} , with the central node in T_{2}^{1} having time label 0 and the central node in T_{2}^{2} having time label 1 . Now suppose that the next step is an “aligned choice” step, with node 3 attaching to node 0 in both trees. Then T_{3}^{1} is a star on four nodes and T_{3}^{2} is a path on four nodes, so the two trees are not isomorphic after the “aligned choice” step, despite being isomorphic before it. Despite this, we are able to distinguish correlated trees from independent ones. To state this result, recall that the total variation distance between two probability measures P and Q on a discrete set \mathcal{X} is defined by \mathrm{TV}(\textsf{P},\textsf{Q}):=\sup_{A\subseteq\mathcal{X}}|\textsf{P}(A)-\textsf{Q}(A)|. (1.1) Theorem 1.1 (Detecting correlation) . For every \alpha\in(0,1] we have that \lim_{n\to\infty}\mathrm{TV}\left(\alpha{\text{-}}\mathrm{CUA}\left(n\right),\mathrm{UA}(n)^{\otimes 2}\right)=1. (1.2) We initially attempted to prove Theorem 1.1 using various simple statistics, such as counting leaves in the two trees. However, while such approaches are able to show that the \mathrm{TV} distance in ( 1.2 ) is bounded away from 0 (see Appendix A for the details for counting leaves), these approaches cannot show that the limiting \mathrm{TV} distance is 1 . To show this, we devise a statistic that is inherently multiscale in nature. This statistic computes the (normalized) sum of the degrees of the K_{j} most central vertices (measured according to Jordan centrality) in both trees, across a range of different values \{K_{j}\}_{j=1}^{\ell} with K_{j}=2^{j}K ; see Section 1.3 for further discussion and Lemmas 3.3 and 3.4 for details. A key ingredient of our proof is a result that quantifies in UA trees the size of the intersection of the earliest vertices and the most central vertices. This is of independent interest in the network archaeology literature; see Section 1.2 and Theorem 1.5 below for details. We can go a step further and ask whether it is possible to asymptotically distinguish between two pairs of trees generated according to \alpha{\text{-}}\mathrm{CUA}(n) and \alpha^{\prime}{\text{-}}\mathrm{CUA}(n) for \alpha\not=\alpha^{\prime} . Our next result affirmatively answers this question by constructing a consistent estimator of \alpha . Theorem 1.2 (Consistent estimation of \alpha ) . There exists an estimator \widehat{\alpha}_{n}:=\widehat{\alpha}_{n}(T_{n}^{1},T_{n}^{2}) such that for every \alpha\in[0,1] , if (T_{n}^{1},T_{n}^{2})\sim\alpha{\text{-}}\mathrm{CUA}(n) , then \widehat{\alpha}_{n}\to\alpha in probability as n\to\infty . The construction of the estimator \widehat{\alpha}_{n} and the proof of Theorem 1.2 build on the statistics and proof of Theorem 1.1 , but are more involved. In particular, \widehat{\alpha}_{n} is also multiscale in nature and relies on estimating early vertices using the most central vertices. However, instead of computing degrees, the estimator \widehat{\alpha}_{n} takes a more fine-grained approach and computes, for central vertices, the number of neighbors whose fringe subtrees have sizes that fall in appropriate intervals. Effectively, the sizes of fringe subtrees allow us to approximately estimate the time labels of late-arriving vertices (at least in aggregate), and doing this across multiple time scales allows to estimate \alpha . We note that the estimator \widehat{\alpha}_{n} is computable in polynomial time in n . We refer to Section 1.3.2 for further details. The existence of this consistent estimator immediately implies the following corollary. Corollary 1.3 (Distinguishing different levels of correlation) . For every \alpha,\alpha^{\prime}\in[0,1] with \alpha\neq\alpha^{\prime} , we have that \lim_{n\to\infty}\mathrm{TV}\left(\alpha{\text{-}}\mathrm{CUA}\left(n\right),\alpha^{\prime}{\text{-}}\mathrm{CUA}(n)\right)=1. While Corollary 1.3 implies Theorem 1.1 , we state it separately because the proof of Theorem 1.1 is fundamentally different and simpler, and moreover it provides insights into the structure of UA trees in general, including the location of their most central vertices, which is a further contribution of the paper. We continue this introduction by discussing this latter contribution, followed by outlines of the proofs of Theorems 1.1 and 1.2 in Section 1.3 , then discussing open problems in Section 1.4 , and finally giving the plan of the rest of the paper in Section 1.5 . 1.2 Finding early vertices A key element of our proofs is identifying collections of vertices of each tree that are likely to contain early vertices and have many labels in common. Statistics related to such vertices can then give information about the correlation between the two trees. The problem of finding the root and early vertices of unlabeled randomly growing trees, including UA, has received significant attention in recent years, catalyzed by Bubeck et al. 2017a . In particular, closest to our paper are the works of Lugosi and Pereira 2019 and Devroye and Reddad 2019 , who study the problem of finding the seed , that is, the tree induced by the earliest vertices. However, for reasons discussed below, the results therein are insufficient for our purposes, so we derive a related result that is of independent interest in network archaeology. Specifically, we quantify in UA trees the size of the intersection of the earliest vertices and the most central vertices; see Theorem 1.5 below. Like many related works, we use the following notion of centrality to identify early vertices. Definition 1.4 (Centrality) . For a vertex v of a tree T , let \psi_{T}(v) denote the size of the maximal component after removing all edges connected to v , and call \psi_{T}(v) the centrality of vertex v . For a tree T , we refer to the K vertices of T with the smallest centrality (with ties broken uniformly at random) as the K most central vertices of T . (This notion of centrality is referred to as Jordan centrality in many network archaeology works, but that terminology is also used for a different notion of centrality—in terms of graph distances—in other areas.) The recent paper Josifov et al. 2026 discusses properties of the most central vertices (for this centrality measure and other common ones) in the context of root finding in UA trees, among others; see also Jog and Loh 2017 ; Jog and Loh 2018 , Banerjee and Bhamidi 2022 , and references therein. Here, we quantify the overlap of the most central vertices with the earliest vertices. Theorem 1.5 . Let T_{n}\sim\mathrm{UA}(n) and let A_{K}(n) be the set of the K most central vertices of T_{n} . Fix c>1 , \delta>0 , and set c^{\prime}:=c\left(1-e^{-1/c}\right)-\delta. Then there exists a constant C<\infty that depends only on c and \delta such that for every \varepsilon>0 , the following holds for all K\geq(C/\varepsilon)\log(1/\varepsilon) and all large enough n\geq n_{0}(K,\delta,c) : \mathbb{P}\left(\left|A_{\lceil cK\rceil}(n)\cap\{0,1,\ldots,K-1\}\right|\geq c^{\prime}\,K\right)\geq 1-\varepsilon. The theorem says that for large enough K , with probability close to one, the proportion of the first K vertices that are also among the cK most central is at least c(1-e^{-1/c})-\delta for any \delta>0 . This proportion is optimal with our proof, but it is an interesting question to study the behavior of |A_{K}(n)\cap\{0,\ldots,K-1\}|/K as K\to\infty . Figure 2 is a simulation illustrating the theorem for K=50 and c=2 , where the overlap between the 50 first arriving vertices and the 100 most-central vertices is 41. Further simulations suggest the mean overlap is around 40 with a standard deviation of a bit more than 2 , which aligns well with the threshold 2(1-e^{-1/2})\times 50=39.35 given by Theorem 1.5 . Figure 2: A simulation of a UA tree with 1000 vertices illustrating Theorem 1.5 with K=50 and c=2 . The 41 purple nodes are those within both the 50 first arrivals and the 100 most central nodes, orange are the 9 remaining of the 50 first arrivals, and green are the 59 remaining of the 100 most central. We use Theorem 1.5 to derive the following corollary that gives a lower bound on the overlap of the K -centrality sets of any two UA trees for large K ; this corollary is a key component of our subsequent proof for detecting correlation. Corollary 1.6 . Let (T_{n}^{1},T_{n}^{2})_{n\geq 0} be a sequence of pairs of UA trees with any joint distribution, and denote their vertex-labeled centrality sets by (A_{r}^{1}(n),A_{r}^{2}(n)) , r\in\N . Then there exists a constant C<\infty such that for all K and for all large enough n\geq n_{0}(K) , \displaystyle\mathbb{P}\left(\left|A_{K}^{1}(n)\cap A_{K}^{2}(n)\right|\geq 0.2K\right)\geq 1-\frac{C\log(K)}{K}. Let us now compare our results with those of Lugosi and Pereira 2019 and Devroye and Reddad 2019 , who study finding the seed in UA trees. There are two main differences between these works and ours. First, most of the results in Lugosi and Pereira 2019 and Devroye and Reddad 2019 focus on settings where the seed is either a known fixed graph (e.g., a path or a star), or certain properties of it are known (e.g., its number of leaves). Our interest is in the setting where the seed is itself a UA tree, so these results do not apply. The exception is ( Lugosi and Pereira 2019 , Theorem 1.5) , which shows that there exists a constant c>0 such that for large K , with probability close to one, the cK/\log K most central vertices are all among the K earliest vertices. However, for our purposes we would like to find \Omega(K) of the K earliest vertices (in fact, to obtain the linear overlap in K in Corollary 1.6 by a union bound, without any assumptions on the joint distribution of (T_{n}^{1},T_{n}^{2}) , we want to find at least (1/2+\varepsilon)K of the earliest K vertices), so the aforementioned result is insufficient for our application. This brings us to the second main difference between these works and ours, which is more conceptual. Lugosi and Pereira 2019 and Devroye and Reddad 2019 focus on seed-finding algorithms that output, with probability close to one, a set that either contains the seed (i.e., it must contain all seed nodes) or is contained in the seed (i.e., it cannot contain nodes outside of the seed). In contrast, our goal is more relaxed, allowing both types of errors: we are fine with outputting a set which does not contain all of the earliest vertices, and which contains vertices that are not early. The upside of this flexibility is that it allows us to find a large fraction of the K earliest vertices, as detailed in Theorem 1.5 . Focusing on the overlap between the earliest vertices and the most central vertices is natural in its own right, so Theorem 1.5 may find other applications. The proof of Theorem 1.5 follows the strategy (used in broad strokes in other works studying centrality in UA trees, e.g., Jog and Loh 2018 , Lugosi and Pereira 2019 ) of relating centrality to the sizes of so-called fringe subtrees of early and late vertices; see Definitions 2.2 and 2.3 , and Lemma 2.4 . For a \mathrm{UA} tree, fringe subtrees evolve as standard Pólya urns started with one ball of the counted color, which we can understand in detail; see Section 2.2 . 1.3 The statistics and proof ideas We now give a high level overview of the key ideas behind our proofs and statistics. Recall that the input to our statistics is a pair of unlabeled trees (T_{n}^{1},T_{n}^{2}) . Imagine, however, that we actually knew the identity of the initial vertex (labeled 0 ) in both trees. We now explain how this can help with distinguishing the distributions \alpha{\text{-}}\mathrm{CUA}(n) and \mathrm{UA}(n)^{\otimes 2} . Let D_{n}^{i}:=\deg_{T_{n}^{i}}(0) denote the degree of the initial vertex in T_{n}^{i} , for i\in\{1,2\} . A natural idea is to use the pair of degrees (D_{n}^{1},D_{n}^{2}) as a statistic to distinguish the distributions \alpha{\text{-}}\mathrm{CUA}(n) and \mathrm{UA}(n)^{\otimes 2} . Observe that we can write D_{n}^{i}=\sum_{j=1}^{n}X_{j}^{i} , where X_{j}^{i} is the indicator random variable that is 1 precisely when node j attaches to node 0 in the i -th tree. Since \mathbb{E}[X_{j}^{i}]=1/j , we have that \mathbb{E}[D_{n}^{i}]=\sum_{j=1}^{n}1/j\approx\log n , and in fact marginally D_{n}^{i} is approximately Poisson distributed with mean \log n . Under the independent model \mathrm{UA}(n)^{\otimes 2} , we have that D_{n}^{1} and D_{n}^{2} are independent. On the other hand, under \alpha{\text{-}}\mathrm{CUA}(n) , the indicators X_{j}^{1} and X_{j}^{2} are dependent. Specifically, we have that \mathbb{P}(X_{j}^{1}=X_{j}^{2}=1)=\alpha/j+(1-\alpha)/j^{2} , which implies that \Cov(D_{n}^{1},D_{n}^{2})\approx\alpha\log n . Now consider the normalized (centered and scaled) degrees Z_{n}^{i}:=(D_{n}^{i}-\log n)/\sqrt{\log n} for i\in\{1,2\} . By the preceding discussion, we have that the pair (Z_{n}^{1},Z_{n}^{2}) is approximately standard Gaussian under \mathrm{UA}(n)^{\otimes 2} , while under \alpha{\text{-}}\mathrm{CUA}(n) it is approximately Gaussian with mean (0,0) and covariance matrix \left(\begin{smallmatrix}1&\alpha\\ \alpha&1\end{smallmatrix}\right) . For every \alpha\in(0,1) , the total variation distance between these two Gaussian distributions is in (0,1) , so \alpha{\text{-}}\mathrm{CUA}(n) and \mathrm{UA}(n)^{\otimes 2} can be distinguished with positive probability. There are two main issues with this approach: (1) the identities of the initial vertices in the two trees are not known , and (2) this only distinguishes with positive probability, not with probability close to one. The solution to the first issue is to turn to network archaeology and estimate the earliest vertices in the two trees, while the solution to the second issue is to consider such statistics across multiple time scales. We dive into the details in Sections 1.3.1 and 1.3.2 below. Before proceeding further, we note that observable statistics can only be in terms of an unlabeled version of the tree T , but many times probabilities of statistics are more conveniently written in terms of the labeled version of the tree. To mitigate confusion around this point, we will write v\in T to denote a vertex in the unlabeled tree (e.g., when indexing a sum), and we will use \{0,\ldots,n\} to denote the vertices of labeled versions of the trees. Both statistics used in our proofs of Theorems 1.1 and 1.2 are based on centrality sets defined using Definition 1.4 , and we denote the K most central vertices of T_{n}^{i} by A_{K}^{i}(n) , 1\leq K\leq n+1 . 1.3.1 Distinguishing between independent and correlated models To construct our separating statistic to distinguish between independent and correlated pairs of UA trees, fix \ell\in\N and integers 01 and appropriately large K and n , \frac{|A_{\lceil cK\rceil}(n)\cap\{0,\ldots,K-1\}|}{K}\geq c(1-e^{-1/c})-\delta with probability close to one. Is the lower bound optimal? What else can be said about the ratio? A tantalizing conjecture is that it converges to c(1-e^{-1/c}) as K\to\infty . • (Other statistics) Our statistics for detection and estimation all involve a two step procedure of (1) fixing a set of vertices based on centrality and (2) computing local statistics related to those vertices, and then, importantly, doing this across multiple time scales. It is natural to ask if there are simpler statistics (e.g., ones that are not multi-scale in nature) that can detect correlation or consistently estimate the correlation parameter. Our first approach to the detection problem was to build a statistic from the joint empirical degree distributions. Marginally, these evolve according to a generalized Pólya urn, and, as shown by Janson 2005 , their centered and scaled limits are jointly Gaussian. The joint empirical degree distributions of correlated UA trees evolve according to a stochastic recursion, and applying central limit theorems in that setting (e.g., Fabian 1968 and Hernandez and Spall 2019 ) yields that the centered and scaled joint degree counts are asymptotically jointly Gaussian with a covariance depending on \alpha . While we were able to follow this program to show that \mathrm{TV}\left(\alpha{\text{-}}\mathrm{CUA}\left(n\right),\mathrm{UA}(n)^{\otimes 2}\right) is asymptotically bounded away from 0 (specifically, by counting leaves in the two trees), we were not able to show that it converges to 1 . See Appendix A for more details. Another approach to the detection problem is to consider the size of the largest common subtree of the two trees. However, even studying this statistic for two independent UA trees is interesting and challenging; see the forthcoming work by Bäumler et al. 2026+ . • (Properties of \alpha{\text{-}}\mathrm{CUA} ) The UA model (also called the random recursive tree) is a beautiful mathematical object with a long history and connections to other areas, such as extreme value theory, with many fine properties understood and studied to this day (e.g., Björklund et al. 2025 , Eslava 2022 , Eslava et al. 2023 , Janson 2005 ; Janson 2019 , Lodewijks 2024 , Meir and Moon 1978 , Pittel 1994 ). Deriving analogs of single-tree properties for the \alpha{\text{-}}\mathrm{CUA} model is an interesting avenue of future research. • (Other models of correlated networks) Studying the questions of this paper in different models with a similar flavor is also of interest. A concrete model is the weighted random recursive tree (see, e.g., Borovkov and Vatutin 2006 ). Here vertex i arrives with a (random or deterministic) weight w_{i} , and vertex n>i attaches to vertex i with probability w_{i}/\sum_{j=0}^{n-1}w_{j} . The case where the weights are all equal is the UA tree. There are several ways to introduce correlation into this model. First, the joint weights \{(w_{i}^{1},w_{i}^{2})\}_{i\geq 0} could be i.i.d. random but w_{i}^{1} and w_{i}^{2} could be correlated in some way, and the edge-choice mechanism then conditionally independent given the weights. Another option—analogous to the model studied in this paper—is to have fixed weights, but the edge choice mechanisms are aligned with probability \alpha\in[0,1] , and independent if not aligned. Another natural extension of correlated UA trees is to consider correlated UA graphs , where now each arriving vertex has m>1 edges connecting independently and uniformly to existing vertices; here m may be deterministic or random. We believe that our high-level approach to the detection problem should extend to this setting, with some modifications. While the notion of centrality we use to identify early vertices is tree-specific, we conjecture that replacing it with some other statistic that identifies early vertices and studying analogous subsequent local statistics such as degrees should yield similar results. For example, Briend et al. 2023 use “double cycles” instead of centrality to identify early vertices in the setting of UA graphs. On the other hand, the local statistic of our consistent estimator of \alpha is tree-specific, and it is not clear how to extend it to graphs. 1.5 Outline The outline of the rest of the paper is as follows. In Section 2 , we prove Theorem 1.5 and Corollary 1.6 . We then show in Section 3 that the separating statistic in ( 1.3 ) can distinguish an independent pair of trees from a correlated pair. Section 4 proves Theorem 1.2 by showing that the estimator in ( 1.5 ) converges in probability to \alpha . Some results about Pólya urns that are used to control fringe-subtree sizes are deferred to Section 5 . 2 Finding early vertices The goal of this section is to prove Corollary 1.6 via the following result, which both implies, and is a more detailed version of Theorem 1.5 from Section 1.2 . Theorem 2.1 . Let T_{n}\sim\mathrm{UA}(n) and recall that A_{K}:=A_{K}(n) denotes the set of the K most central vertices in T_{n} . There exists a universal constant C<\infty such that for every K\in\N , c>1 , and \delta\in(0,c-1) , the following holds for all large enough n\geq n_{0}(K,\delta,c) : \mathbb{P}\left(\bigl\lvert A_{\lceil cK\rceil}(n)\cap\bigl\{0,\ldots,K-1\bigr\}\bigr\rvert\geq\bigl(c(1-e^{-1/c})-\delta\bigr)K\right)\geq 1-C\left(\frac{c\log(cK)}{\delta^{2}K}+(0.7)^{\delta K/2}\right). As previously mentioned, the strategy to prove Theorem 2.1 is to relate centrality to certain subtree sizes. For this, we introduce a kind of inverse or negative centrality of a vertex v in a tree T on \lvert T\rvert vertices, which is simply \Psi_{T}(v):=\lvert T\rvert-\psi_{T}(v). In words, \Psi_{T}(v) is the number of vertices left in T when removing the largest component subtree formed by removing vertex v and all edges connecting to it. The reason for looking at this quantity over \psi_{T}(v) is that in a rooted tree T , if the largest subtree is the one containing the root, then \Psi_{T}(v) is exactly the size of the so-called fringe subtree , which we now define. Definition 2.2 (Fringe subtree size) . The fringe subtree of a vertex v of T having root 0 is the subtree of T induced by the collection of vertices whose path to the root 0 contains v (note that this set includes v ). We denote the number of vertices in the fringe subtree of T by F_{T}(v) . With this heuristic in mind, we introduce the following (deterministic) definition of trees where vertices having “large” fringe trees appear early on. Definition 2.3 . For K\in\N , \delta\in(0,1) , and c_{1}\geq 1 , we say a tree T on vertices \{0,\ldots,n\} is (K,\delta,c_{1}) -good if (i) \sum_{\delta K/2-11 implies \begin{split}\mathbb{P}\biggl(\bigl\lvert A_{\lceil cK\rceil}(n)\cap\bigl\{0,\ldots,K-1\bigr\}\bigr\rvert\geq\bigl((c-\delta)&(1-e^{-\frac{1}{c-\delta}})-\delta\bigr)K\biggr)\\ &\geq 1-C^{\star}\left(\frac{(c-\delta)\log((c-\delta)K)}{\delta^{2}K}+(0.7)^{\delta K}\right).\end{split} (2.1) Simple considerations imply that the function \phi(x):=x(1-e^{-1/x}) restricted to [0,\infty) is non-decreasing with derivative 0\leq\phi^{\prime}(x)\leq 1 , so that the mean value theorem implies (c-\delta)\bigl(1-e^{-\frac{1}{c-\delta}}\bigr)-c(1-e^{-1/c}))\geq-\delta, and so we have that \begin{split}\mathbb{P}\biggl(\bigl\lvert A_{\lceil cK\rceil}(n)\cap&\bigl\{0,\ldots,K-1\bigr\}\bigr\rvert\geq\bigl(c(1-e^{-1/c})-2\delta\bigr)K\biggr)\\ &\geq\mathbb{P}\biggl(\bigl\lvert A_{\lceil cK\rceil}(n)\cap\bigl\{0,\ldots,K-1\bigr\}\bigr\rvert\geq\bigl((c-\delta)(1-e^{-\frac{1}{c-\delta}})-\delta\bigr)K\biggr).\end{split} (2.2) The theorem follows by combining ( 2.1 ) and ( 2.2 ), changing \delta to \delta/2 , and using that x\log x is increasing for x\geq 1 . ∎ We finish the subsection by proving Corollary 1.6 . Proof of Corollary 1.6 . If \lvert A_{K}^{1}\cap A_{K}^{2}\rvert\leq 0.2K , then it must be the case that for at least one i\in\{1,2\} , \bigl\lvert A_{K}^{i}\cap\{0,\ldots,\lceil K/1.1\rceil\}\bigr\rvert\leq(0.58)K. This is because the minimum overlap of two subsets of sizes larger than A from a common superset of size B<2A is (2A-B) . Taking A=(0.58)K and B=\lceil K/1.1\rceil+1 , this gives the overlap of size at least (2\cdot 0.58-(1.1)^{-1})K-1\geq 0.25K for large enough K . But for fixed \widetilde{K}\in\N , Theorem 2.1 with c=1.1 , \delta=0.001 , and K=\widetilde{K}/c implies that \mathbb{P}\bigl(\lvert A_{\widetilde{K}}\cap\{0,\ldots,\lceil\widetilde{K}/1.1\rceil\}\rvert\leq(0.58)\widetilde{K}\bigr)\leq\widetilde{C}\frac{\log(\widetilde{K})}{\widetilde{K}}, and now switching \widetilde{K} to K and taking a union bound implies the result. ∎ In the remainder of this section, we prove Lemmas 2.4 and 2.5 . 2.1 Proof of Lemma 2.4 Proof of Lemma 2.4 . First note that A_{r} consists of the r vertices j with the largest values of \Psi_{T}(j) . Thus, we relate \Psi_{T}(k) to F_{T}(k) . A first key observation is that if F_{T}(k)<0.5(n+1) , then F_{T}(k)=\Psi_{T}(k) . Thus (i) from Definition 2.3 implies that \sum_{k=0}^{n}\mathbbm{1}_{\{F_{T}(k)\not=\Psi_{T}(k)\}}\leq\delta K/2. (2.3) Using this with (ii) , we have that \sum_{k=0}^{n}\mathbbm{1}_{\{\Psi_{T}(k)\geq n/(c_{1}K)\}}\leq\sum_{k=0}^{n}\mathbbm{1}_{\left\{F_{T}(k)\geq n/(c_{1}K)\right\}}+\delta K/2\leq\lceil(c_{1}+\delta)K\rceil. Thus there are at most \lceil(c_{1}+\delta)K\rceil vertices k with \Psi_{T}(k)\geq n/(c_{1}K) , which implies that any such vertex is in A_{\lceil(c_{1}+\delta)K\rceil} . Using this fact, ( 2.3 ), and (iii) , we find that \displaystyle\bigl\lvert A_{\lceil(c_{1}+\delta)K\rceil}\cap\bigl\{0,\ldots,K-1\bigr\}\bigr\rvert \displaystyle\geq\sum_{k=0}^{K-1}\mathbbm{1}_{\{\Psi_{T}(k)\geq n/(c_{1}K)\}}\geq\sum_{k=0}^{K-1}\mathbbm{1}_{\{F_{T}(k)\geq n/(c_{1}K)\}}-\delta K/2 \displaystyle\geq\bigl(c_{1}(1-e^{-1/c_{1}})-\delta\bigr)K.\qed 2.2 Proof of Lemma 2.5 To prove Lemma 2.5 , we need estimates of the moments of the random variables appearing in Definition 2.3 . We use properties of standard Pólya urns to derive the following. Lemma 2.6 . Let T_{n}\sim\mathrm{UA}(n) and fix constants 01 , and Ks by assumption) to find \displaystyle\sum_{k=0}^{n}\mathbb{P}(F_{T_{n}}(k)\geq n/(c_{1}K)) \displaystyle\leq\sum_{k=0}^{n}\bigl((1-(c_{1}K)^{-1}+n^{-1/4})^{k}+e^{-\sqrt{n}/2}\bigr) \displaystyle\leq\frac{1}{(c_{1}K)^{-1}-n^{-1/4}}+(n+1)e^{-\sqrt{n}/2} \displaystyle\leq\bigl(1+\tfrac{\delta}{4c_{1}}\bigr)c_{1}K, for n large enough. For ( 2.8 ), we use ( 2.5 ). Set \gamma small enough and n large enough (depending on \delta ) so that 1-\frac{(c_{1}K)^{-1}+2\gamma+2/n}{1-\gamma}\geq 1-\frac{1+\iota}{c_{1}K}, (2.10) where \iota is a parameter that can be chosen sufficiently small later. With this choice of \gamma and possibly enlarging n so that K<\gamma n , ( 2.5 ) with \beta=1/(c_{1}K) and ( 2.10 ) implies that \displaystyle\sum_{k=0}^{K-1}\mathbb{P}(F_{T_{n}}(k)\geq n/(c_{1}K)) \displaystyle\geq\sum_{k=0}^{K-1}\left(1-\frac{1+\iota}{c_{1}K}\right)^{k}=\frac{1-\left(1-\frac{1+\iota}{c_{1}K}\right)^{K}}{1-\left(1-\frac{1+\iota}{c_{1}K}\right)} \displaystyle\geq c_{1}K\left(\frac{1-e^{-\frac{(1+\iota)}{c_{1}}}}{1+\iota}\right)\geq(c_{1}(1-e^{-1/c_{1}})-\delta/4)K, which follows by shrinking \iota , and then choosing n large enough. Next we bound the variance ( 2.9 ), and to save space we denote I_{k}:=\mathbbm{1}_{\{F_{T_{n}}(k)\geq n/(c_{1}K)\}} . We compute \Var\biggl(\sum_{k=0}^{L}I_{k}\biggr)=\Var\biggl(\sum_{k=1}^{L}I_{k}\biggr)=\sum_{k=1}^{L}\Var(I_{k})+2\sum_{1\leq k\lceil(c_{1}+\delta)K\rceil-\delta K/2\biggr) \displaystyle\leq\frac{C\bigl(c_{1}K\log(c_{1}K)\bigr)}{\bigl(\lceil(c_{1}+\delta)K\rceil-\delta K/2-(1+\delta/(4c_{1}))c_{1}K\bigr)^{2}} \displaystyle\leq\frac{16C\bigl(c_{1}\log(c_{1}K)\bigr)}{\delta^{2}K}. Similarly, for (iii) , the bounds ( 2.8 ) and ( 2.9 ) on the mean and variance combined with Chebyshev’s inequality imply \displaystyle\mathbb{P}\biggl(\sum_{k=0}^{K-1}\mathbbm{1}_{\left\{F_{T}(k)\geq n/(c_{1}K)\right\}}<(c_{1}(1-e^{-1/c_{1}})-\delta/2)K\biggr) \displaystyle\leq\frac{16C\bigl(c_{1}\log(c_{1}K)\bigr)}{\delta^{2}K}.\qed 3 Distinguishing independent trees from correlated ones In this section, we show that the total variation distance between a pair of independent \mathrm{UA} trees and a pair of correlated ones tends to one, as the number of vertices tends to infinity. As previously described, if we knew the labels of A_{K}^{i}(n) for i=1,2 , and the overlap between them, then the mean and variance of the separating statistic could be computed. We first derive the appropriate results in this setting in Lemma 3.1 , and then use them in Section 3.2 to show how to distinguish. 3.1 Mean and variance of sums of degrees of sets Fix \ell\in\N and an increasing sequence 0m , we have \displaystyle\mathbb{E}\left[\left(S_{j}^{X}(n)-S_{j}^{Z}(n)\right)^{2}\right]\geq\left(2-0.01\alpha\right)K_{j}\log(n), (3.3) \displaystyle\mathbb{E}\left[\left(S_{j}^{X}(n)-S_{j}^{Y}(n)\right)^{2}\right]\leq\left(2-0.1\alpha\right)K_{j}\log(n), (3.4) \displaystyle\Cov\left(\left(S_{j}^{X}(n)-S_{j}^{Z}(n)\right)^{2},\left(S_{i}^{X}(n)-S_{i}^{Z}(n)\right)^{2}\right)\leq 10K_{j}^{2}\log(n)^{2},\text{ and } (3.5) \displaystyle\Cov\left(\left(S_{j}^{X}(n)-S_{j}^{Y}(n)\right)^{2},\left(S_{i}^{X}(n)-S_{i}^{Y}(n)\right)^{2}\right)\leq 10K_{j}^{2}\log(n)^{2}. (3.6) Furthermore, \displaystyle\mathbb{P}\biggl(\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}}{K_{j}\log(n)}\leq 2-0.02\alpha\biggr) \displaystyle\leq\frac{20\sum_{0\leq j\leq i\leq\ell}(K_{j}/K_{i})}{(\ell+1)^{2}(0.01\alpha)^{2}}, (3.7) \displaystyle\mathbb{P}\biggl(\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr)^{2}}{K_{j}\log(n)}\geq 2-0.09\alpha\biggr) \displaystyle\leq\frac{20\sum_{0\leq j\leq i\leq\ell}(K_{j}/K_{i})}{(\ell+1)^{2}(0.01\alpha)^{2}}, (3.8) and for any t>0 , \displaystyle\mathbb{P}\bigl(\bigl\lvert S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr\rvert\geq t\bigr) \displaystyle\leq\frac{4\log(n)}{t^{2}}K_{j}, (3.9) \displaystyle\mathbb{P}\bigl(\bigl\lvert S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr\rvert\geq t\bigr) \displaystyle\leq\frac{4\log(n)}{t^{2}}K_{j}. (3.10) The left hand side of the lower bound ( 3.3 ) does not depend on \alpha , and the right hand side could replace 0.01\alpha with any small enough constant, but we prefer to state things this way for easier comparison to the upper bound ( 3.4 ). Before proving the lemma, we record a useful result that follows easily by direct computation. Proposition 3.2 . If X,Y,\widetilde{X},\widetilde{Y} are square-integrable and mean-zero random variables such that (X,\widetilde{X}) is independent of (Y,\widetilde{Y}) , then \Cov\bigl(XY,\widetilde{X}\widetilde{Y}\bigr)=\Cov\bigl(X,\widetilde{X}\bigr)\Cov\bigl(Y,\widetilde{Y}\bigr). (3.11) If, in addition, Z is a square integrable random variable such that Y is independent of (X,Z) , then \Cov(X,YZ)=0. (3.12) Proof of Lemma 3.1 . We start with computing \mathbb{E}\Bigl[\left(S_{j}^{X}(n)-S_{j}^{Z}(n)\right)^{2}\Bigr] . Since the random variables (X_{a})_{a\geq N+1} are independent, we have \displaystyle\mathbb{E}\left[S_{j}^{X}(n)\right] \displaystyle=\sum_{a=N+1}^{n}\mathbb{P}\left(X_{a}\in M_{K_{j}}\right)=\sum_{a=N+1}^{n}\frac{K_{j}}{a}, \displaystyle\Var\left(S_{j}^{X}(n)\right) \displaystyle=\sum_{a=N+1}^{n}\Var\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}\right)=\sum_{a=N+1}^{n}\left(\frac{K_{j}}{a}-\left(\frac{K_{j}}{a}\right)^{2}\right)\approx K_{j}\log(n), where we have used from ( 3.1 ) that |M_{K_{j}}|=K_{j} . Since |M_{K_{j}}|=|\widetilde{M}_{K_{j}}| , we see that S_{j}^{X}(n),S_{j}^{Z}(n) , and S_{j}^{Y}(n) are identically distributed, and in particular, they all have the same mean and variance as above. Since S_{j}^{X}(n) and S_{j}^{Z}(n) are independent, we easily find that \displaystyle\mathbb{E}\Bigl[\left(S_{j}^{X}(n)-S_{j}^{Z}(n)\right)^{2}\Bigr] \displaystyle=2\Var\left(S_{j}^{X}(n)\right)=2\sum_{a=N+1}^{n}\left(\frac{K_{j}}{a}-\left(\frac{K_{j}}{a}\right)^{2}\right) (3.13) \displaystyle\geq 2\sum_{a=N+1}^{n}\frac{K_{j}}{a}-5K_{j}^{2}\geq\left(2-0.01\alpha\right)K_{j}\log(n), for n large enough, noting that we have introduced 0.01\alpha in line with the remark following the statement of Lemma 3.1 . This shows inequality ( 3.3 ). For ( 3.4 ), the sets M_{K_{j}} and \widetilde{M}_{K_{j}} satisfy |M_{K_{j}}|=|\widetilde{M}_{K_{j}}|=K_{j} and |M_{K_{j}}\cap\widetilde{M}_{K_{j}}|\geq 0.2K_{j} so that the symmetric difference of the sets M_{K_{j}}\Delta\widetilde{M}_{K_{j}}=\bigl(M_{K_{j}}\cup\widetilde{M}_{K_{j}}\bigr)\setminus\bigl(M_{K_{j}}\cap\widetilde{M}_{K_{j}}\bigr) satisfies |M_{K_{j}}\Delta\widetilde{M}_{K_{j}}|\leq 1.8K_{j} . Using this, we can upper bound the second moment of S_{j}^{X}(n)-S_{j}^{Y}(n) by \displaystyle\mathbb{E}\left[\left(S_{j}^{X}(n)-S_{j}^{Y}(n)\right)^{2}\right]=\Var\left(\sum_{a=N+1}^{n}\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{Y_{a}\in\widetilde{M}_{K_{j}}\}}\right)\right) \displaystyle=\sum_{a=N+1}^{n}\Var\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{Y_{a}\in\widetilde{M}_{K_{j}}\}}\right) \displaystyle=\alpha\sum_{a=N+1}^{n}\mathbb{E}\left[\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{X_{a}\in\widetilde{M}_{K_{j}}\}}\right)^{2}\right]+(1-\alpha)\sum_{a=N+1}^{n}\mathbb{E}\left[\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{Z_{a}\in\widetilde{M}_{K_{j}}\}}\right)^{2}\right] \displaystyle=\alpha\sum_{a=N+1}^{n}\mathbb{E}\left[\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\Delta\widetilde{M}_{K_{j}}\}}\right)^{2}\right]+(1-\alpha)\sum_{a=N+1}^{n}\Var\left(\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{Z_{a}\in\widetilde{M}_{K_{j}}\}}\right) \displaystyle=\alpha\sum_{a=N+1}^{n}\frac{\bigl\lvert M_{K_{j}}\Delta\widetilde{M}_{K_{j}}\bigr\rvert}{a}+2(1-\alpha)\sum_{a=N+1}^{n}\left(\frac{K_{j}}{a}-\frac{K_{j}^{2}}{a^{2}}\right) \displaystyle\leq\alpha 1.8\sum_{a=N+1}^{n}\frac{K_{j}}{a}+2(1-\alpha)\sum_{a=N+1}^{n}\frac{K_{j}}{a}=\left(2-0.2\alpha\right)\sum_{a=N+1}^{n}\frac{K_{j}}{a}\leq\left(2-0.1\alpha\right)K_{j}\log(n), for n large enough, which proves ( 3.4 ). Next, we estimate the covariances of \bigl(\bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr)^{2}\bigr)_{j\in\{0,\ldots,\ell\}} to prove inequality ( 3.6 ). The proof does not depend on the fact that \alpha>0 , and thus the exact same proof (with Y replaced by Z ) also shows inequality ( 3.5 ). First define the random variables R_{a}:=\mathbbm{1}_{\{X_{a}\in M_{K_{j}}\}}-\mathbbm{1}_{\{Y_{a}\in\widetilde{M}_{K_{j}}\}} , a\geq N+1 , which are independent and satisfy R_{a}\in\{-1,0,1\} , \mathbb{E}\left[R_{a}\right]=\mathbb{E}\left[R_{a}^{3}\right]=0,\text{ and }\mathbb{E}\left[R_{a}^{2}\right]=\mathbb{E}\left[R_{a}^{4}\right]\leq 2\mathbb{P}\left(X_{a}\in M_{K_{j}}\right)\leq\frac{2K_{j}}{a}. (3.14) We define their index- i counterpart random variables T_{a}:=\mathbbm{1}_{\{X_{a}\in M_{K_{i}}\}}-\mathbbm{1}_{\{Y_{a}\in\widetilde{M}_{K_{i}}\}} for a=N+1,\ldots,n , so that (S_{j}^{X}(n)-S_{j}^{Y}(n))=\sum_{a=N+1}^{n}R_{a},\ \text{ and }\ (S_{i}^{X}(n)-S_{i}^{Y}(n))=\sum_{c=N+1}^{n}T_{c}. Now, we calculate the covariance of \bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr)^{2} and \bigl(S_{i}^{X}(n)-S_{i}^{Y}(n)\bigr)^{2} for i,j\in\{0,\ldots,\ell\} with j\leq i . Noting that (R_{a},T_{a})_{a\geq N+1} are independent mean-zero bivariate random vectors, we find that \displaystyle\Cov\Bigl(\bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr)^{2},\bigl( \displaystyle S_{i}^{X}(n)-S_{i}^{Y}(n)\bigr)^{2}\Bigr) \displaystyle=\sum_{a,b=N+1}^{n}\sum_{\{c,d\}\cap\{a,b\}\not=\emptyset}\Cov(R_{a}R_{b},T_{c}T_{d}) \displaystyle=\sum_{a=N+1}^{n}\Cov(R_{a}^{2},T_{a}^{2})+2\sum_{\begin{subarray}{c}a,b\in\{N+1,\ldots,n\}:\\ a\neq b\end{subarray}}\Cov(R_{a}R_{b},T_{a}T_{b}), where the second equality follows because \Cov(R_{a}^{2},T_{a}T_{c})=0 for c\not=a , and \Cov(R_{a}R_{b},T_{a}T_{c})=0 for a\not=b and c\not\in\{a,b\} (again by independence and zero means). Using ( 3.11 ), we have that for a\not=b , \Cov(R_{a}R_{b},T_{a}T_{b})=\Cov(R_{a},T_{a})\Cov(R_{b},T_{b}) , and, using ( 3.14 ) and \lvert T_{a}\rvert\leq 1 , that \displaystyle\lvert\Cov(R_{a},T_{a})\rvert \displaystyle=\lvert\mathbb{E}[R_{a}T_{a}]\rvert\leq\mathbb{E}[\lvert R_{a}\rvert]\leq 2\frac{K_{j}}{a}, \displaystyle\lvert\Cov(R_{a}^{2},T_{a}^{2})\rvert \displaystyle\leq\mathbb{E}[R_{a}^{2}T_{a}^{2}]\leq\mathbb{E}[R_{a}^{2}]\leq 2\frac{K_{j}}{a}. Combining the previous two displays gives \displaystyle\Cov\Bigl( \displaystyle\bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr)^{2},\bigl(S_{i}^{X}(n)-S_{i}^{Y}(n)\bigr)^{2}\Bigr) \displaystyle\leq\sum_{a=N+1}^{n}\Cov(R_{a}^{2},T_{a}^{2})+2\sum_{\begin{subarray}{c}a,b\in\{N+1,\ldots,n\}:\\ a\neq b\end{subarray}}\Cov(R_{a},T_{a})\Cov(R_{b},T_{b}) \displaystyle\leq 2\sum_{a=N+1}^{n}\frac{K_{j}}{a}+8\sum_{\begin{subarray}{c}a,b\in\{N+1,\ldots,n\}:\\ a\neq b\end{subarray}}\frac{K_{j}^{2}}{ab} \displaystyle\leq 10K_{j}^{2}\log(n)^{2}, for large enough n . This establishes ( 3.6 ) for j\leq i . To prove ( 3.7 ), first note that inequality ( 3.3 ) implies that \mathbb{E}\left[\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}}{K_{j}\log(n)}\right]\geq 2-0.01\alpha for all large enough n\in\N . Chebyshev’s inequality shows that \mathbb{P}\biggl(\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}}{K_{j}\log(n)}\leq 2-0.02\alpha\biggr)\leq\frac{\Var\Bigl(\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}}{K_{j}\log(n)}\Bigr)}{(\ell+1)^{2}(0.01\alpha)^{2}}. (3.15) We further bound the variance using ( 3.5 ) to find \displaystyle\Var\Bigl(\sum_{j=0}^{\ell}\frac{\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}}{K_{j}\log(n)}\Bigr) \displaystyle\leq 2\sum_{0\leq j\leq i\leq\ell}\frac{\Cov\left(\left(S_{j}^{X}(n)-S_{j}^{Z}(n)\right)^{2},\left(S_{i}^{X}(n)-S_{i}^{Z}(n)\right)^{2}\right)}{K_{i}K_{j}\log(n)^{2}} \displaystyle\leq 20\sum_{0\leq j\leq i\leq\ell}(K_{j}/K_{i}), which, combined with ( 3.15 ), gives ( 3.7 ). The proof of ( 3.8 ) follows in a nearly identical manner to ( 3.7 ), substituting ( 3.4 ) for ( 3.3 ), and ( 3.6 ) for ( 3.5 ). To prove ( 3.9 ), we use Markov’s inequality and the squared moment expression ( 3.13 ) to find that for n large enough, \displaystyle\mathbb{P}\bigl(\bigl\lvert S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr\rvert\geq t\bigr)=\mathbb{P}\bigl(\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}\geq t^{2}\bigr)\leq\frac{\mathbb{E}\Bigl[\bigl(S_{j}^{X}(n)-S_{j}^{Z}(n)\bigr)^{2}\Bigr]}{t^{2}}\leq\frac{4\log(n)}{t^{2}}K_{j}. The proof of ( 3.10 ) follows in a nearly identical manner, but using ( 3.4 ) in place of ( 3.13 ). ∎ 3.2 Using the moment bounds to distinguish The next two lemmas immediately imply that it is possible to asymptotically distinguish the independent \mathrm{UA} model from a correlated one. Lemma 3.3 . If \bigl(T_{n}^{1},T_{n}^{2}\bigr)_{n\in\N} is distributed according to the measure 0\text{-CUA} , then for all \varepsilon>0 there exist m,K,\ell\in\N such that for all n\geq m \displaystyle\mathbb{P}\left(\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{1}{2^{j}K\log(n)}\left(\sum_{x\in A_{2^{j}K}^{1}(n)}\deg_{T_{n}^{1}}(x)-\sum_{x\in A_{2^{j}K}^{2}(n)}\deg_{T_{n}^{2}}(x)\right)^{2}>2-0.05\alpha\right)>1-\varepsilon. Lemma 3.4 . If \bigl(T_{n}^{1},T_{n}^{2}\bigr)_{n\in\N} is distributed according to the measure \alpha{\text{-}}\mathrm{CUA} , then for all \varepsilon>0 there exist m,K,\ell\in\N such that for all n\geq m \displaystyle\mathbb{P}\left(\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{1}{2^{j}K\log(n)}\left(\sum_{x\in A_{2^{j}K}^{1}(n)}\deg_{T_{n}^{1}}(x)-\sum_{x\in A_{2^{j}K}^{2}(n)}\deg_{T_{n}^{2}}(x)\right)^{2}<2-0.05\alpha\right)>1-\varepsilon. The statistics in the lemmas are closely related to those considered in Lemma 3.1 with M_{K_{j}}=A_{K_{j}}^{1} and \widetilde{M}_{K_{j}}^{2} , but there are two key differences. The first is that the sets A_{K_{j}}^{i} are not fixed, and the second is that Lemma 3.1 only considers the contribution to degrees past some threshold step N . The following two lemmas are a key tool for controlling these differences between the two setting, in order to apply Lemma 3.1 . Lemma 3.5 . From two sequences (X_{j}^{i})_{j\geq 1} , i=1,2 with X_{j}^{i}\in\{0,1,\ldots,j-1\} , generate a paired tree sequence (T_{k}^{1},T_{k}^{2})_{k\geq 1} , where the edges of T_{k}^{i} are \{\{j,X_{j}^{i}\}\}_{j=0}^{k} . Fix a sequence of time steps 0C\log(n), for some fixed C>0 . Then \displaystyle\frac{1}{(\ell+1)\log(n)}\sum_{j=0}^{\ell}\frac{1}{K_{j}} \displaystyle\biggl(\sum_{x\in A_{K_{j}}^{1}(n)}\deg_{T_{n}^{1}}(x)-\sum_{x\in A_{K_{j}}^{2}(n)}\deg_{T_{n}^{2}}(x)\biggr)^{2} (3.16) \displaystyle>C-\frac{1}{(\ell+1)\log(n)}\sum_{j=0}^{\ell}\frac{2(m+1)\log(n)^{2/3}+(m+1)^{2}}{K_{j}}. Lemma 3.6 . Under the setup of Lemma 3.5 , assume that (a) and (b) hold, and, in addition, that the following holds. (c’) After time step m , the weighted sum of squares of the differences in the number of nodes connecting to A_{K_{j}}^{i}(m) in each of the two trees satisfies the bound \frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{1}{K_{j}}\biggl(\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{1}\in A_{K_{j}}^{1}(m)\right\}}-\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{2}\in A_{K_{j}}^{2}(m)\right\}}\biggr)^{2}0 . Then \displaystyle\frac{1}{(\ell+1)\log(n)}\sum_{j=0}^{\ell}\frac{1}{K_{j}} \displaystyle\biggl(\sum_{x\in A_{K_{j}}^{1}(n)}\deg_{T_{n}^{1}}(x)-\sum_{x\in A_{K_{j}}^{2}(n)}\deg_{T_{n}^{2}}(x)\biggr)^{2} \displaystyleC\log(n)-\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{2(m+1)\log(n)^{2/3}+(m+1)^{2}}{K_{j}}, where the first equality is because of ( 3.17 ), the second equality is because of (a) , the second to last inequality is because of ( 3.18 ) and the elementary inequality (x+y)^{2}\geq x^{2}-2|xy|-y^{2} , and the last inequality follows from (b) and (c) . Dividing both sides by \log(n) proves the result. ∎ To prove Lemma 3.3 (respectively Lemma 3.4 ) we show that with good probability for \mathrm{UA} trees, (a) , (b) , and (c) (respectively (c’) ) hold for appropriate parameters. The last two items are handled by Lemma 3.1 , while for (a) , we use the following result, which is due to Jog and Loh ( Jog and Loh 2018 , Theorem 2) . Theorem 3.7 (Theorem 2 in Jog and Loh 2018 ) . For all \varepsilon>0,K\in\N there exists m\in\N such that for a uniform-attachment tree (T_{n})_{n\in\N} one has \displaystyle\mathbb{P}\left(A_{K}(T_{m})=A_{K}(T_{n})\text{ for all }n\geq m\right)>1-\varepsilon. We can now prove the first of the main results of this section. Proof of Lemma 3.4 . Let \ell be large enough so that \frac{40}{(\ell+1)(0.01\alpha)^{2}}\leq\frac{\varepsilon}{5}. (3.19) For K\in\N , set K_{j}:=K2^{j} , j=0,\ldots,\ell , and let N\in\N and K both be large enough so that for all n\geq N \sum_{j=0}^{\ell}\mathbb{P}\left(\left|A_{K_{j}}^{1}(n)\cap A_{K_{j}}^{2}(n)\right|<0.2\cdot K_{j}\right)\leq\frac{\varepsilon}{5}. (3.20) The existence of such K,N\in\N follows from Corollary 1.6 , since \lim_{K\to\infty}\sum_{j=0}^{\ell}\frac{\log(2^{j}K)}{2^{j}K}=0. Given those values of \ell,K , let m\geq N be large enough so that \sum_{i=1}^{2}\sum_{j=0}^{\ell}\mathbb{P}\left(A_{K_{j}}^{i}(M)\neq A_{K_{j}}^{i}(m)\text{ for some }M\geq m\right)<\frac{\varepsilon}{5}. (3.21) The existence of such an integer m\in\N follows from Theorem 3.7 . Finally, take n\geq m large enough so that \sum_{j=0}^{\ell}\frac{4\cdot 2^{j}K}{\log(n)^{1/3}}<\frac{\varepsilon}{5}, (3.22) and \frac{2(m+1)+(m+1)^{2}}{\log(n)^{1/3}}<0.01\alpha. (3.23) In view of applying Lemma 3.6 , define the events \displaystyle{\mathcal{A}} \displaystyle=\bigcap_{i=1}^{2}\bigcap_{j=0}^{\ell}\left\{A_{K_{j}}^{i}(M)=A_{K_{j}}^{i}(m)\text{ for all }M\geq m\right\}, \displaystyle{\mathcal{B}} \displaystyle=\biggl\{\max_{j\in\{0,\ldots,\ell\}}\biggl\lvert\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{1}\in A_{K_{j}}^{1}(m)\right\}}-\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{2}\in A_{K_{j}}^{2}(m)\right\}}\biggr\rvert\leq\log(n)^{2/3}\biggr\}, \displaystyle{\mathcal{C}} \displaystyle=\left\{\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{1}{K_{j}\log(n)}\left(\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{1}\in A_{K_{j}}^{1}(m)\right\}}-\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{2}\in A_{K_{j}}^{2}(m)\right\}}\right)^{2}<2-0.08\alpha\right\}, where we recall that X_{k}^{i}\sim\mathrm{Uniform}\{0,\ldots,k-1\} represents the vertex that vertex k attaches to in T_{k}^{i} . If the events {\mathcal{A}},{\mathcal{B}},{\mathcal{C}} hold, then Lemma 3.6 with K_{j}=K2^{j} and C=2-0.08\alpha implies \displaystyle\frac{1}{(\ell+1)\log(n)}\sum_{j=0}^{\ell} \displaystyle\frac{1}{K_{j}}\left(\sum_{x\in A_{K_{j}}^{1}(n)}\deg(x)-\sum_{x\in A_{K_{j}}^{2}(n)}\deg(x)\right)^{2} \displaystyle\leq 2-0.08\alpha+\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{2(m+1)\log(n)^{2/3}+(m+1)^{2}}{2^{j}K\log(n)} \displaystyle\leq 2-0.08\alpha+\frac{2(m+1)+(m+1)^{2}}{\log(n)^{1/3}}<2-0.05\alpha, where the last inequality is because of ( 3.23 ). Thus, in order to show Lemma 3.4 , it suffices to show that \mathbb{P}({\mathcal{A}}\cap{\mathcal{B}}\cap{\mathcal{C}})>1-\varepsilon , which is equivalent to saying that \mathbb{P}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\cup{\mathcal{C}}^{c})<\varepsilon . Introducing the event \displaystyle{\mathcal{D}} \displaystyle=\bigcap_{j=0}^{\ell}\left\{\left|A_{K_{j}}^{1}(m)\cap A_{K_{j}}^{2}(m)\right|\geq 0.2\cdot K_{j}\right\}, a union bound implies \mathbb{P}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\cup{\mathcal{C}}^{c})\leq\mathbb{P}({\mathcal{A}}^{c})+\mathbb{P}({\mathcal{B}}^{c}|{\mathcal{D}})+\mathbb{P}({\mathcal{C}}^{c}|{\mathcal{D}})+\mathbb{P}({\mathcal{D}}^{c}), and we show that each of the four summands is bounded by \frac{\varepsilon}{5} , which shows the result. The inequality \mathbb{P}({\mathcal{A}}^{c})\leq\frac{\varepsilon}{5} directly follows from a union bound and ( 3.21 ). The inequality \mathbb{P}({\mathcal{D}}^{c})\leq\frac{\varepsilon}{5} directly follows from a union bound and ( 3.20 ), noting that m\geq N . For the third summand \mathbb{P}({\mathcal{C}}^{c}|{\mathcal{D}}) , because (X_{k}^{1},X_{k}^{2})_{k>m} are independent of A_{K_{j}}^{i}(m) , i=1,2 , (as functions only of the edge indicators (X_{k}^{1},X_{k}^{2})_{k=1}^{m} ), we have that given {\mathcal{D}} , the random variables \Bigl(\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{1}\in A_{K_{j}}^{1}(m)\right\}}-\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{2}\in A_{K_{j}}^{2}(m)\right\}}\Bigr),\ \ j=0,\ldots,\ell (3.24) have the same joint distributions as the random variables \bigl(S_{j}^{X}(n)-S_{j}^{Y}(n)\bigr) defined at ( 3.2 ) with M_{K_{j}}=A_{K_{j}}^{1}(m) , \widetilde{M}_{K_{j}}=A_{K_{j}}^{2}(m) , and N=m , and satisfy ( 3.1 ). Thus, ( 3.7 ) of Lemma 3.1 implies \mathbb{P}({\mathcal{C}}^{c}|{\mathcal{D}})\leq\frac{20\sum_{0\leq j\leq i\leq\ell}2^{j-i}}{(\ell+1)^{2}(0.01\alpha)^{2}}\leq\frac{40}{(\ell+1)(0.01\alpha)^{2}}\leq\frac{\varepsilon}{5}, where we have used K_{j}=K2^{j} in the first inequality, an easy direct calculation in the second, and ( 3.19 ) in the third. Using again that conditional on {\mathcal{D}} , we may apply Lemma 3.1 to ( 3.24 ), a union bound and ( 3.9 ) with t=\log(n)^{2/3} imply \mathbb{P}({\mathcal{B}}^{c}|{\mathcal{D}})\leq\frac{4}{\log(n)^{1/3}}\sum_{j=0}^{\ell}K2^{j}\leq\frac{\varepsilon}{5}, where we have used ( 3.22 ) and that n\geq m in the second inequality. ∎ Proof of Lemma 3.3 . The proof follows nearly the same way as the previous one, but we replace the event {\mathcal{C}} with {\mathcal{C}}^{\prime}=\left\{\frac{1}{\ell+1}\sum_{j=0}^{\ell}\frac{1}{K_{j}\log(n)}\left(\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{1}\in A_{K_{j}}^{1}(m)\right\}}-\sum_{k=m+1}^{n}\mathbbm{1}_{\left\{X_{k}^{2}\in A_{K_{j}}^{2}(m)\right\}}\right)^{2}>2-0.02\alpha\right\}, and we use ( 3.3 ), ( 3.5 ), ( 3.7 ), and ( 3.9 ) where we previously used ( 3.4 ), ( 3.6 ), ( 3.8 ), and ( 3.10 ) (respectively). ∎ 4 Estimating the correlation parameter \alpha In this section, we prove Corollary 1.3 . Recall from ( 1.4 ), that for a vertex v\in T_{n}^{i} and j\leq\ell\in\N , we define \displaystyle\widehat{U}_{\ell,j}^{T_{n}^{i}}(u)=\sum_{v\in T_{n}^{i}}\mathbbm{1}\left\{v\sim_{i}u,\left|K_{v}\left(T_{n}^{i}\setminus\{u\}\right)\right|\in\left(\frac{n}{e^{j}},\frac{n}{e^{\ell}}\right]\right\}, where for a tree T_{n}^{i} and two distinct vertices u,v in the tree, we write \left|K_{v}\left(T_{n}^{i}\setminus\{u\}\right)\right| for the size of the tree that contains v when removing u . The theorem directly follows from the following lemma. Lemma 4.1 . For all \varepsilon>0 there exist m,k,K\in\N such that for all n\geq m , whenever \left(T_{n}^{1},T_{n}^{2}\right) is distributed according to \alpha{\text{-}}\mathrm{CUA} , then \displaystyle\mathbb{P}\left(\left|\min_{u_{1}\in A_{K}^{1}(n),u_{2}\in A_{K}^{2}(n)}\frac{1}{k^{3}}\sum_{j=1}^{k}\left(\widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})-\widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2})\right)^{2}-2(1-\alpha)\right|\leq\varepsilon\right)>1-\varepsilon. As mentioned previously, we study the \widehat{U}^{T_{n}^{i}} variables through the easier to understand quantities \begin{split}U_{\ell,j}^{T_{n}^{i}}(u)&:=\sum_{v=M+1}^{n}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)\in\left(\frac{n}{e^{j}},\frac{n}{e^{\ell}}\right]\right\}.\end{split} (4.1) We will eventually show that the first order behavior of our estimator is the same when replacing the \widehat{U}^{T_{n}^{i}} variables in it with the U^{T_{n}^{i}} . The next lemma is the key to our proof, and shows that to first order, U_{\ell,j}^{T_{n}^{i}}(u) behaves as the simpler \begin{split}D_{\ell,j}^{T_{n}^{i}}(u):=\sum_{v=e^{\ell}}^{e^{j}-1}\mathbbm{1}\left\{v\sim_{i}u\right\},\end{split} (4.2) which is a sum of independent Bernoulli-distributed random variables. Lemma 4.2 . Let \ell,j,M,n,u be such that u0 and for k large enough, \mathbb{E}\left[X_{k}(u_{1},u_{2})\right]\in\left(2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)-\frac{\varepsilon}{10},2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)+\frac{\varepsilon}{10}\right) (4.3) and \Var\left(X_{k}(u_{1},u_{2})\right)\leq\frac{\bar{C}}{k} (4.4) for some \bar{C}<\infty . Proof. Recalling that U_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u)=D_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u)+Z_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u) for any u , and, for the sake of brevity, writing \displaystyle\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})} \displaystyle\coloneqq U_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})-U_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2}), \displaystyle\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})} \displaystyle\coloneqq D_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})-D_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2}), \displaystyle\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})} \displaystyle\coloneqq Z_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})-Z_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2}), we have that \displaystyle\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right] \displaystyle=\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}+\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right] \displaystyle\begin{split}&=\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]+\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]\\ &\qquad\qquad+\frac{2}{k^{2}}\mathbb{E}\left[\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\,\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right].\end{split} (4.5) For the first term in this sum, for all k large enough and all j\in[k] , we have that \begin{split}\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]&=\frac{1}{k^{2}}\mathbb{E}\left[\left(\sum_{v=e^{jk^{2}}}^{e^{(j+1)k^{2}}-1}\left(\mathbbm{1}_{\left\{v\sim_{1}u_{1}\right\}}-\mathbbm{1}_{\left\{v\sim_{2}u_{2}\right\}}\right)\right)^{2}\right]\\ &=\frac{1}{k^{2}}\sum_{v=e^{jk^{2}}}^{e^{(j+1)k^{2}}-1}\left(\frac{2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)}{v}-\frac{2(1-\alpha)}{v^{2}}\right)\\ &\in\left(2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)\pm\frac{\varepsilon}{20}\right),\end{split} (4.6) where the second equality follows by a direct calculation, using that the mean zero random variables \left(\mathbbm{1}_{\left\{v\sim_{1}u_{1}\right\}}-\mathbbm{1}_{\left\{v\sim_{2}u_{2}\right\}}\right) are independent across v . Also note that the above calculation directly implies that for k large enough, we have \displaystyle\mathbb{E}\left[\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]\leq 3k^{2} (4.7) For the second summand in ( 4.5 ), Lemma 4.2 combined with the Cauchy-Schwarz inequality implies that for k large enough, we have \begin{split}\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]\leq\frac{2}{k^{2}}\mathbb{E}\left[Z_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})^{2}+Z_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2})^{2}\right]\leq\frac{4\sqrt{C_{\star}}}{k^{2}}\leq\frac{\varepsilon}{100}.\end{split} (4.8) For the third term in ( 4.5 ), we use the Cauchy-Schwarz inequality, Lemma 4.2 combined with the Cauchy-Schwarz inequality, and ( 4.7 ), to find that for k large enough \begin{split}\left|\frac{2}{k^{2}}\mathbb{E}\left[\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\,\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right]\right|&\leq\frac{2}{k^{2}}\mathbb{E}\left[\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]^{1/2}\mathbb{E}\left[\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]^{1/2}\\ &\leq\frac{2}{k^{2}}\left(3k^{2}\right)^{1/2}\left(4\sqrt{C^{\star}}\right)^{1/2}\leq\frac{\varepsilon}{100}.\end{split} (4.9) Inserting ( 4.6 ), ( 4.8 ), and ( 4.9 ) into ( 4.5 ), we find \displaystyle\mathbb{E}\left[\frac{1}{k^{2}}\left(\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right]\in\left(2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)-\frac{\varepsilon}{10},2\left(1-\alpha\mathbbm{1}_{u_{1}=u_{2}}\right)+\frac{\varepsilon}{10}\right), which gives the desired result ( 4.3 ) for the mean of X_{k}(u_{1},u_{2}) . To bound the variance of X_{k}(u_{1},u_{2}) , we need to bound covariance terms. We have \displaystyle\Cov\biggl(\Bigl( \displaystyle\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\Bigr)^{2},\Bigl(\Delta U_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\Bigr)^{2}\biggr) \displaystyle=\Cov\left(\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+\Cov\left(\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+2\Cov\left(\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right) \displaystyle\hskip 14.22636pt+2\Cov\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})},\left(\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+2\Cov\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})},\left(\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+4\Cov\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})},\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right) \displaystyle\hskip 14.22636pt+\Cov\left(\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+\Cov\left(\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\hskip 14.22636pt+2\Cov\left(\left(\Delta Z_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\Delta D_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\Delta Z_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right). We now bound each of the 9 terms in the above sum separately. The first term is 0 for j\neq j^{\prime} , as the relevant random variables are independent. For j=j^{\prime} , \begin{split}\Var\left(\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{4}\right)&\leq\mathbb{E}\left[\left(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{4}\right]\\ &=\mathbb{E}\left[\left(\sum_{v=e^{jk^{2}}}^{e^{(j+1)k^{2}}-1}\mathbbm{1}\left\{v\sim_{1}u_{1}\right\}-\mathbbm{1}\left\{v\sim_{2}u_{2}\right\}\right)^{4}\right]\\ &\leq 3\left(\sum_{v=e^{jk^{2}}}^{e^{(j+1)k^{2}}-1}\frac{2}{v}\right)^{2}+\left(\sum_{v=e^{jk^{2}}}^{e^{(j+1)k^{2}}-1}\frac{2}{v}\right)\\ &\leq 36k^{4},\end{split} (4.10) where the second inequality follows by direct calculation, using that for centered independent random variables (Y_{\gamma})_{\gamma} with Y_{\gamma}\in\{-1,0,1\} , we have \displaystyle\mathbb{E}\biggl[\Bigl(\sum_{\gamma}Y_{\gamma}\Bigr)^{4}\biggr]=3\sum_{\begin{subarray}{c}\gamma,\gamma^{\prime}:\\ \gamma\neq\gamma^{\prime}\end{subarray}}\mathbb{E}\left[Y_{\gamma}^{2}Y_{\gamma^{\prime}}^{2}\right]+\sum_{\gamma}\mathbb{E}[Y_{\gamma}^{4}]\leq 3\left(\sum_{\gamma}\mathbb{E}\left[Y_{\gamma}^{2}\right]\right)^{2}+\sum_{\gamma}\mathbb{E}[Y_{\gamma}^{4}], and that \mathbb{E}\bigl[(\mathbbm{1}\left\{v\sim_{1}u_{1}\right\}-\mathbbm{1}\left\{v\sim_{2}u_{2}\right\})^{2}\bigr]\leq 2/v , read from ( 4.6 ). The remaining 8 terms are bounded using that \Cov(X,Y)\leq\sqrt{\Var(X)\Var(Y)}\leq\sqrt{\mathbb{E}\left[X^{2}\right]\mathbb{E}\left[Y^{2}\right]}, and, from ( 4.10 ), that \mathbb{E}\Bigl[\bigl(\Delta D_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\bigr)^{4}\Bigr]\leq 36k^{4} , and finally, from Lemma 4.2 , that for some universal constant C_{\star}>0 , we have \displaystyle\mathbb{E}\left[\left(\Delta Z_{ik^{2},(i+1)k^{2}}^{(u_{1},u_{2})}\right)^{4}\right]\leq C_{\star}. This implies that the remaining eight terms are upper bounded of order k^{3} , and so we have that \displaystyle\Cov\left(\left(\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta U_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right)\leq 36k^{4}\mathbbm{1}_{\{j=j^{\prime}\}}+\widetilde{C}k^{3} for some constant \widetilde{C}<\infty . Thus we find that \displaystyle\Var\left(X_{k}(u_{1},u_{2})\right) \displaystyle=\frac{1}{k^{6}}\sum_{j=1}^{k}\sum_{j^{\prime}=1}^{k}\Cov\left(\left(\Delta U_{jk^{2},(j+1)k^{2}}^{(u_{1},u_{2})}\right)^{2},\left(\Delta U_{j^{\prime}k^{2},(j^{\prime}+1)k^{2}}^{(u_{1},u_{2})}\right)^{2}\right) \displaystyle\leq\frac{1}{k^{6}}\sum_{j=1}^{k}\sum_{j^{\prime}=1}^{k}\left(36k^{4}\mathbbm{1}_{\{j=j^{\prime}\}}+\widetilde{C}k^{3}\right)\leq\frac{36k^{5}+\widetilde{C}k^{5}}{k^{6}}\leq\frac{\bar{C}}{k}, as desired. ∎ We can now prove our main result by linking the behavior of X_{k}(u_{1},u_{2}) to that of our observable statistic, and then applying Proposition 4.3 . Proof of Lemma 4.1 . Fix \varepsilon>0 . We first define “good” events, under which the event considered in the lemma holds deterministically, and then lower bound the probability of these good events. For the latter, let K\in\N be such that \displaystyle\mathbb{P}\left(A_{K}^{1}(n)\cap A_{K}^{2}(n)\not=\emptyset\right)>1-\frac{\varepsilon}{10} (4.11) for all n\geq N(K) large enough. The existence of such K is guaranteed by Corollary 1.6 . Given this K , let M\in\N be such that M\geq N(K) and for all n\geq M , we have \mathbb{P}\left(A_{K}^{1}(M)=A_{K}^{1}(\ell)\text{ for all }\ell\geq M\right)>1-\frac{\varepsilon}{10}. (4.12) The existence of such an M follows from ( Jog and Loh 2018 , Theorem 2) , stated as Theorem 3.7 above. Given K and M , take k large enough, and n\geq e^{k^{2}(k+1)} also large enough so that \displaystyle(M+1)^{2}\frac{100\Var\left(X(u_{1},u_{2})\right)}{\varepsilon^{2}}\leq\frac{\varepsilon}{5}, (4.13) which can be done by Proposition 4.3 . Finally, since M is fixed and F_{T_{n}^{1}}(M)/n\to F\sim\mathrm{Beta}(1,M) almost surely, we can enlarge k and n\geq e^{k^{2}(k+1)} if necessary to make 2(M+1)^{2}\mathbb{P}(F\leq e^{-k})\leq\frac{\varepsilon}{10}, and then choose n large enough so that 2(M+1)^{2}\biggl\lvert\mathbb{P}(F\leq e^{-k})-\mathbb{P}\Bigl(F_{T_{n}^{1}}(M)\leq\frac{n}{e^{k}}\Bigr)\biggr\rvert\leq\frac{\varepsilon}{10} which implies \displaystyle 2(M+1)^{2}\mathbb{P}\left(F_{T_{n}^{1}}(M)\leq\frac{n}{e^{k}}\right)\leq\frac{\varepsilon}{5}. Given K,M,k , and n , define the good events \displaystyle{\mathcal{A}}=\left\{A_{K}^{1}\left(n\right)\cap A_{K}^{2}\left(n\right)\not=\emptyset\right\}, \displaystyle{\mathcal{B}}=\left\{A_{K}^{i}(n)=A_{K}^{i}(M),i=1,2\right\}, \displaystyle{\mathcal{C}}=\bigcap_{u_{1}\in A_{K}^{1}(M)}\bigcap_{u_{2}\in A_{K}^{2}(M)}\left\{\left|X(u_{1},u_{2})-\mathbb{E}\left[X(u_{1},u_{2})\right]\right|\leq\frac{\varepsilon}{10}\right\}, \displaystyle{\mathcal{D}}=\bigcap_{i=1}^{2}\bigcap_{v=0}^{M}\bigcap_{\begin{subarray}{c}u=0\\ u\neq v\end{subarray}}^{M}\left\{\left|K_{v}\left(T_{n}^{i}\setminus\{u\}\right)\right|>\frac{n}{e^{k}}\right\}. With this setup, we make the following Claim: If the four events {\mathcal{A}},{\mathcal{B}},{\mathcal{C}} , and {\mathcal{D}} hold, then \displaystyle\min_{u_{1}\in A_{K}^{1}(n),u_{2}A_{K}^{2}(n)}\frac{1}{k^{3}}\sum_{j=1}^{k}\left(\widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{1}}(u_{1})-\widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{2}}(u_{2})\right)^{2}\in(2(1-\alpha)-\varepsilon,2(1-\alpha)+\varepsilon). To see why the claim is true, if the event {\mathcal{B}} holds, then the minimum over u_{1}\in A_{K}^{1}(n),u_{2}\in A_{K}^{2}(n) goes only over a subset of \{0,\ldots,M\} . Further, if the event {\mathcal{D}} holds, then \displaystyle\widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{i}}(u_{i})=U_{jk^{2},(j+1)k^{2}}^{T_{n}^{i}}(u_{i}). (4.14) This is because all vertices v\in\{0,\ldots,M\} with v\neq u_{i} satisfy \left|K_{v}\left(T_{n}^{i}\setminus\{u_{i}\}\right)\right|>\frac{n}{e^{jk^{2}}} , and thus do not contribute to the sum in \widehat{U}_{jk^{2},(j+1)k^{2}}^{T_{n}^{i}}(u_{i}) . For other vertices u_{i}\leq M\frac{\varepsilon}{10}\right) \displaystyle\leq\sum_{u_{1}\in\{0,\ldots,M\}}\sum_{u_{2}\in\{0,\ldots,M\}}\frac{100\Var(X(u_{1},u_{2}))}{\varepsilon^{2}}<\frac{\varepsilon}{5}. For each pair u,v\in\{0,\ldots,M\} with u\neq v , the size of K_{v}\left(T_{n}^{i}\setminus\{u\}\right) stochastically dominates F_{T_{n}^{i}}(M) , so that a union bound implies \displaystyle\mathbb{P}\left({\mathcal{D}}^{c}\right)\leq\sum_{i=1}^{2}\sum_{v=0}^{M}\sum_{\begin{subarray}{c}u=0\\ u\neq v\end{subarray}}^{M}\mathbb{P}\left(\left|K_{v}\left(T_{n}^{i}\setminus\{u\}\right)\right|\leq\frac{n}{e^{k}}\right)\leq 2(M+1)^{2}\mathbb{P}\left(F_{T_{n}^{i}}(M)\leq\frac{n}{e^{k}}\right)<\frac{\varepsilon}{5}, which finishes the proof. ∎ 4.1 Proof of Lemma 4.2 We first define some intermediate random variables, which can be used to decompose Z_{\ell,j}^{T_{n}^{i}}(u) . \displaystyle O_{\ell,j}^{T_{n}^{i}}(u) \displaystyle:=\sum_{v=e^{\ell}}^{e^{j}-1}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right\}, \displaystyle I_{\ell,j}^{1,T_{n}^{i}}(u) \displaystyle:=\sum_{v=M+1}^{e^{\ell}-1}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)\leq\frac{n}{e^{\ell}}\right\}, \displaystyle I_{\ell,j}^{2,T_{n}^{i}}(u) \displaystyle:=\sum_{v=e^{j}}^{n}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)>\frac{n}{e^{j}}\right\}, \displaystyle\widetilde{O}_{\ell,j}^{T_{n}^{i}}(u) \displaystyle:=\sum_{v=e^{\ell}}^{e^{j}-1}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\right\} \displaystyle\widetilde{I}_{\ell,j}^{1,T_{n}^{i}}(u) \displaystyle:=\sum_{v=M+1}^{e^{\ell}-1}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right\}, \displaystyle\widetilde{I}_{\ell,j}^{2,T_{n}^{i}}(u) \displaystyle:=\sum_{v=e^{j}}^{n}\mathbbm{1}\left\{v\sim_{i}u,F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\right\}. By basic set operations, and separating summands according to the label of vertices v\in[M+1,n] , (i.e., O,\widetilde{O} are terms with v\in[e^{\ell},e^{j}) , I^{1},\widetilde{I}^{1} have v\in[M+1,e^{\ell}) and I^{2},\widetilde{I}^{2} have v\in[e^{j},n] ), we easily find that \begin{split}Z_{\ell,j}^{T_{n}^{i}}(u)&=-\left(O_{\ell,j}^{T_{n}^{i}}(u)+\widetilde{O}_{\ell,j}^{T_{n}^{i}}(u)\right)+\left(I_{\ell,j}^{1,T_{n}^{i}}(u)-\widetilde{I}_{\ell,j}^{1,T_{n}^{i}}(u)\right)+\left(I_{\ell,j}^{2,T_{n}^{i}}(u)-\widetilde{I}_{\ell,j}^{2,T_{n}^{i}}(u)\right).\end{split} (4.15) Since for general x_{1},\ldots,x_{6}\in\R , we have (x_{1}+\cdots+x_{6})^{4}\leq 6^{4}\max_{i=1,\ldots,6}x_{i}^{4}\leq 6^{4}\sum_{i=1}^{6}x_{i}^{4}, it is sufficient to show that the fourth moment of each of the six random variables in the decomposition ( 4.15 ) of Z_{\ell,j}^{T_{n}^{i}}(u) is uniformly bounded. To accomplish this, we need the following result for sums of Bernoulli random variables. Proposition 4.4 . Let X_{1},\ldots,X_{n} be Bernoulli random variables and let X=\sum_{i=1}^{n}X_{i} . Suppose that for any subset of indices S\subseteq\{1,\ldots,n\} with \lvert S\rvert\leq 4 , there is a constant \widetilde{C} such that \mathbb{P}\left(X_{i}=1\text{ for all }i\in S\right)\leq\widetilde{C}\prod_{i\in S}\mathbb{P}(X_{i}=1). (4.16) Then there is a constant \widehat{C} depending only on \widetilde{C} such that \displaystyle\mathbb{E}\left[X^{4}\right]\leq\widehat{C}\bigl(\mathbb{E}[X]+\mathbb{E}[X]^{4}\bigr). Proof. Expanding the fourth power of X and using that X_{i}^{k}=X_{i}\in\{0,1\} for any k>0 , there is a universal (combinatorial) constant c_{4} such that \displaystyle\mathbb{E}\left[X^{4}\right] \displaystyle=\sum_{i_{1},i_{2},i_{3},i_{4}=1}^{n}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}X_{i_{3}}X_{i_{4}}\right] \displaystyle\leq c_{4}\biggl(\sum_{i_{1}=1}^{n}\mathbb{E}\left[X_{i_{1}}\right]+\sum_{\begin{subarray}{c}i_{1},i_{2}\in\{1,\ldots,n\}:\\ i_{1}\neq i_{2}\end{subarray}}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}\right] \displaystyle\qquad\qquad+\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3}\in\{1,\ldots,n\}:\\ |\{i_{1},i_{2},i_{3}\}|=3\end{subarray}}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}X_{i_{3}}\right]+\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\in\{1,\ldots,n\}:\\ |\{i_{1},i_{2},i_{3},i_{4}\}|=4\end{subarray}}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}X_{i_{3}}X_{i_{4}}\right]\biggr) \displaystyle\leq c_{4}\,\widetilde{C}\biggl(\sum_{i_{1}=1}^{n}\mathbb{E}\left[X_{i_{1}}\right]+\sum_{i_{1},i_{2}=1}^{n}\mathbb{E}\left[X_{i_{1}}\right]\mathbb{E}\left[X_{i_{2}}\right] \displaystyle\qquad\qquad+\sum_{i_{1},i_{2},i_{3}=1}^{n}\mathbb{E}\left[X_{i_{1}}\right]\mathbb{E}\left[X_{i_{2}}\right]\mathbb{E}\left[X_{i_{3}}\right]+\sum_{i_{1},i_{2},i_{3},i_{4}=1}^{n}\mathbb{E}\left[X_{i_{1}}\right]\mathbb{E}\left[X_{i_{2}}\right]\mathbb{E}\left[X_{i_{3}}\right]\mathbb{E}\left[X_{i_{4}}\right]\biggr) \displaystyle=c_{4}\,\widetilde{C}\biggl(\sum_{j=1}^{4}\mathbb{E}[X]^{j}\biggr), where the second inequality uses the hypothesis ( 4.16 ). The result follows by taking \widehat{C}=4c_{4}\,\widetilde{C} . ∎ To apply the proposition, we need to verify ( 4.16 ) for the Bernoulli sums in our setting, and have good bounds on their means. For the latter we use the following result. Lemma 4.5 . Let T_{n}\sim\mathrm{UA}(n) , let u\in\{0,\ldots,n\} and let r\in\left[1,n\right] . Then \sum_{v=r}^{n}\mathbb{P}\left(v\sim u,F_{T_{n}}(v)>\frac{n}{r}\right)\leq 2, (4.17) and \sum_{v=u+1}^{r-1}\mathbb{P}\left(v\sim u,F_{T_{n}}(v)\leq\frac{n}{r}\right)\leq 1. (4.18) Proof. We start with a proof of ( 4.17 ). Noting that (F_{T_{n}}(v)-1) is distributed as the number of times a red ball is chosen in a standard Pólya urn started with 1 red and v blue balls after taking n-v steps, exchangeability implies \mathbb{E}\left[F_{T_{n}}(v)\right]=1+\frac{n-v}{v+1}=\frac{n+1}{v+1}. Since the events \{v\sim u\} and \left\{F_{T_{n}}(v)>\frac{n}{r}\right\} are independent, an application of Markov’s inequality implies that \displaystyle\sum_{v=r}^{n}\mathbb{P}\left(v\sim u,F_{T_{n}}(v)>\frac{n}{r}\right) \displaystyle=\sum_{v=r}^{n}\mathbb{P}\left(v\sim u\right)\mathbb{P}\left(F_{T_{n}}(v)>\frac{n}{r}\right)\leq\sum_{v=r}^{n}\frac{1}{v}\frac{\mathbb{E}[F_{T_{n}}(v)]}{n/r} \displaystyle\leq 2\sum_{v=r}^{n}\frac{r}{v(v+1)}=2r\left(\frac{1}{r}-\frac{1}{n+1}\right)\leq 2. For ( 4.18 ), noting again the Pólya urn represpentation of F_{T_{n}}(v)-1 , a direct calculation gives \displaystyle\mathbb{P}\left(F_{T_{n}}(v)-1=k\right) \displaystyle=\binom{n-v}{k}\frac{\Gamma(1+k)\Gamma(n-k)}{\Gamma\left(1+n\right)}\frac{\Gamma\left(1+v\right)}{\Gamma(1)\Gamma(v)} \displaystyle=\frac{(n-v)!k!(n-k-1)!v!}{k!(n-v-k)!n!(v-1)!} \displaystyle=\frac{(n-v)!v}{n!}\frac{(n-1-k)!}{(n-v-k)!}. By considering consecutive ratios, the last expression is maximal when k=0 . In particular, we have that for all v\in\{1,\ldots,n\} and \{x\in 1,\ldots,n\} , \displaystyle\mathbb{P}\left(F_{T_{n}}(v)=x\right)\leq\mathbb{P}\left(F_{T_{n}}(v)-1=0\right)=\frac{(n-v)!v}{n!}\frac{(n-1)!}{(n-v)!}=\frac{v}{n}. Summing over all possible values x\leq n/r yields \displaystyle\mathbb{P}\left(F_{T_{n}}(v)\leq\frac{n}{r}\right)=\sum_{x=1}^{\frac{n}{r}}\mathbb{P}\left(F_{T_{n}}(v)=x\right)\leq\sum_{x=1}^{\frac{n}{r}}\frac{v}{n}\leq\frac{v}{r}. Using again that the events \left\{v\sim u\right\} and \left\{F_{T_{n}}(v)\leq\frac{n}{r}\right\} are independent for v\geq u+1 , we find that \displaystyle\sum_{v=u+1}^{r-1}\mathbb{P}\left(v\sim u,F_{T_{n}}(v)\leq\frac{n}{r}\right)=\sum_{v=u+1}^{r-1}\mathbb{P}\left(v\sim u\right)\mathbb{P}\left(F_{T_{n}}(v)\leq\frac{n}{r}\right)\leq\sum_{v=u+1}^{r-1}\frac{1}{v}\frac{v}{r}\leq 1.\qed We can now prove the main result of this subsection. Proof of Lemma 4.2 . As previously mentioned, it is enough to show that fourth moment of each of the six random variables in the decomposition ( 4.15 ) of Z_{\ell,j}^{T_{n}^{i}}(u) is uniformly bounded. We only show that \mathbb{E}\bigl[O_{\ell,j}^{T_{n}^{i}}(u)^{4}\bigr] and \mathbb{E}\bigl[\widetilde{O}_{\ell,j}^{T_{n}^{i}}(u)^{4}\bigr] are uniformly bounded; the terms \mathbb{E}\bigl[I_{\ell,j}^{1,T_{n}^{i}}(u)^{4}\bigr] and \mathbb{E}\bigl[\widetilde{I}_{\ell,j}^{1,T_{n}^{i}}(u)^{4}\bigr] can be treated like the term \mathbb{E}\bigl[O_{\ell,j}^{T_{n}^{i}}(u)^{4}\bigr] , whereas the terms \mathbb{E}\bigl[I_{\ell,j}^{2,T_{n}^{i}}(u)^{4}\bigr] and \mathbb{E}\bigl[\widetilde{I}_{\ell,j}^{2,T_{n}^{i}}(u)^{4}\bigr] can be treated like the term \mathbb{E}\bigl[\widetilde{O}_{\ell,j}^{T_{n}^{i}}(u)^{4}\bigr] . We start with the term \mathbb{E}\bigl[\widetilde{O}_{\ell,j}^{T_{n}^{i}}(u)^{4}\bigr] , and apply Proposition 4.4 . To verify ( 4.16 ), let S\subset\left\{\lceil e^{\ell}\rceil,\ldots,\lfloor e^{j}-1\rfloor\right\} be a collection of vertices corresponding to the summands from \widetilde{O}_{\ell,j}^{T_{n}^{i}}(u) . A key fact we will use that given v\sim_{i}u for all v\in S , the process \bigl((F_{T_{m}^{i}}(v))_{v\in S}\bigr)_{m\geq\lfloor e^{j}-1\rfloor} of sizes of the Fringe subtrees of vertices in S starting from time \lfloor e^{j}-1\rfloor evolve like a multi-color Pólya urn with random initialization. In particular, they are conditionally negatively related. Thus we have that \displaystyle\mathbb{P}\left(\bigcap_{v\in S}\left\{F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}},v\sim_{i}u\right\}\right) \displaystyle=\mathbb{P}\left(\bigcap_{v\in S}\left\{F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\right\}\Big|\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\mathbb{P}\left(\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right) \displaystyle\leq\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\Big|\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\right)\mathbb{P}\left(\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right) \displaystyle=\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\Big|\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right) \displaystyle\leq\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\Big|v\sim_{i}u\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right) \displaystyle=\prod_{v\in S}\mathbb{P}\left(v\sim_{i}u,F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\right), where the first inequality follows from the conditional negative relation already discussed, and the second inequality is because \{v^{\prime}\sim_{i}u\} is either independent of the event \{F_{T_{n}^{i}}(v)>y\} (if v^{\prime}\frac{n}{e^{\ell}}\right)\leq\sum_{v=e^{\ell}}^{n}\mathbb{P}\left(v\sim_{i}u,F_{T_{n}^{i}}(v)>\frac{n}{e^{\ell}}\right)\leq 2, and now finally applying Proposition 4.4 yields the result for this case. Next, we bound \mathbb{E}\bigl[O_{j,\ell}^{T_{n}^{i}}(u)^{4}\bigr] in an analogous way. Let S\subset\left\{\lceil e^{\ell}\rceil,\ldots,\lfloor e^{j}-1\rfloor\right\} be a collection of vertices, corresponding to the summands from O_{j,\ell}^{T_{n}^{i}}(u) , such that |S|\leq 4 . Then \begin{split}&\mathbb{P}\left(\bigcap_{v\in S}\left\{F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}},v\sim_{i}u\right\}\right)\\ &\qquad=\mathbb{P}\left(\bigcap_{v\in S}\left\{F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right\}\Big|\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\mathbb{P}\left(\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\\ &\qquad\leq\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\right)\mathbb{P}\left(\bigcap_{v^{\prime}\in S}\left\{v^{\prime}\sim_{i}u\right\}\right)\\ &\qquad=\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|\bigcap_{v^{\prime}\in S\setminus\{v\}}\left\{v^{\prime}\sim_{i}u\right\}\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right),\end{split} (4.19) where the inequality is due to conditional negative relation, and the second equality follows by direct calculation and independence, noting that u\leq v^{\prime}\in S . To go further, the key observation is that the distribution of F_{T_{n}^{i}}(v) conditional on the event \cap_{v^{\prime}\in S\setminus\{v\}}\left\{v^{\prime}\sim_{i}u\right\} is stochastically larger than the conditional distribution of F_{T_{n}^{i}}(v) given that v^{\prime} does not join the fringe subtree of v when it arrives, which we write as \cap_{v^{\prime}\in S\setminus\{v\}}\{v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\} , where {\mathcal{F}}_{T_{m}}^{i}(v) is the fringe subtree of v at time m , and which we say is empty if mv result in a particular blue ball, whereas the latter conditioning corresponds to the same set of draws being any blue ball. It is intuitively clear that conditioning on choosing any blue ball at some set of times has a stronger bias to smaller values of red balls than conditioning on choosing a particular blue ball, and this yields the stochastic monotonicity. A formal proof using the correspondence to Pólya urns is given in Lemma 5.1 below. Now, because the size of the fringe subtree of v evolves like the number of red balls in a Pólya urn started with 1 red ball and v\geq 1 blue ball(s), exchangeability implies the chance vertex v^{\prime} joins the fringe subtree is 1/(1+v)\leq 1/2 . Combining this fact with the positive association of the events \{v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\} for v^{\prime}\in S\setminus\{v\} , we have that \mathbb{P}\left(\bigcap_{v^{\prime}\in S\setminus\{v\}}\{v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\}\right)\geq\prod_{v^{\prime}\in S\setminus\{v\}}\mathbb{P}\left(v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\right)\geq 2^{-\lvert S\setminus\{v\}\rvert}\geq 2^{-3}, (4.20) where in the last inequality we use that \lvert S\rvert\leq 4 . Using the stochastic monotonicity and the inequality ( 4.20 ), we can bound the terms appearing in the last line of ( 4.19 ) by \displaystyle\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|\bigcap_{v^{\prime}\in S\setminus\{v\}}\left\{v^{\prime}\sim_{i}u\right\}\right) \displaystyle\leq\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|\bigcap_{v^{\prime}\in S\setminus\{v\}}\{v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\}\right) \displaystyle\leq\frac{\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right)}{\mathbb{P}\left(\bigcap_{v^{\prime}\in S\setminus\{v\}}\{v^{\prime}\not\in{\mathcal{F}}_{T_{v^{\prime}}^{i}}(v)\}\right)} \displaystyle\leq 8\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right). Inserting this into ( 4.19 ) and using again that |S|\leq 4 , we get that \displaystyle\mathbb{P}\left(\bigcap_{v\in S}\left\{F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}},v\sim_{i}u\right\}\right) \displaystyle\leq\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|\bigcap_{v^{\prime}\in S\setminus\{v\}}\left\{v^{\prime}\sim_{i}u\right\}\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right) \displaystyle\leq\left(\prod_{v\in S}8\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right) \displaystyle=8^{|S|}\left(\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\Big|v\sim_{i}u\right)\right)\prod_{v^{\prime}\in S}\mathbb{P}\left(v^{\prime}\sim_{i}u\right) \displaystyle\leq 8^{4}\prod_{v\in S}\mathbb{P}\left(F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}},v\sim_{i}u\right), verifying ( 4.16 ) with \widetilde{C}=8^{4} . The first moment is bounded by ( 4.18 ) from Lemma 4.5 , which gives \mathbb{E}\left[O_{\ell,j}^{T_{n}^{i}}(u)\right]=\sum_{v=e^{\ell}}^{e^{j}-1}\mathbb{P}\left(v\sim_{i}u,F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right)\leq\sum_{v=u+1}^{e^{j}-1}\mathbb{P}\left(v\sim_{i}u,F_{T_{n}^{i}}(v)\leq\frac{n}{e^{j}}\right)\leq 1. The result now follows from Proposition 4.4 . ∎ 5 Pólya urn lemmas Here we record some results about standard Pólya urns used above. Lemma 5.1 . Let (R_{m})_{m\geq 0} be the sequence of counts of the number of red balls in a standard Pólya urn started with r\in\N red balls and b\in\N blue balls. Assume also that one of the blue balls is in the urn initially is ‘distinguished’ with the label \mathfrak{d} . Let {\mathcal{B}}_{\ell} denote the event that a blue ball is chosen at step \ell , and {\mathcal{D}}_{\ell} denote the event that the the ball marked \mathfrak{d} is chosen at step \ell . Then for any sequence of draws 00, where {\mathcal{N}}(\mu,\sigma^{2}) denotes a Gaussian random variable with mean \mu and variance \sigma^{2} . We provide an overview of the analysis here, and leave the details to the interested reader. Define the sets \displaystyle{\mathcal{S}}_{11}(n) \displaystyle:=\left\{0\leq v\leq n:\deg_{T_{n}^{1}}(v)=\deg_{T_{n}^{2}}(v)=1\right\}, \displaystyle{\mathcal{S}}_{1\times}(n) \displaystyle:=\left\{0\leq v\leq n:\deg_{T_{n}^{1}}(v)=1,\deg_{T_{n}^{2}}(v)\geq 2\right\}, \displaystyle{\mathcal{S}}_{\times 1}(n) \displaystyle:=\left\{0\leq v\leq n:\deg_{T_{n}^{1}}(v)\geq 2,\deg_{T_{n}^{2}}(v)=1\right\}, \displaystyle{\mathcal{S}}_{\times\times}(n) \displaystyle:=\left\{0\leq v\leq n:\deg_{T_{n}^{1}}(v)\geq 2,\deg_{T_{n}^{2}}(v)\geq 2\right\}. Note that these sets partition the set \{0,1,\ldots,n\} , while also capturing similarities in leaves with the same node label across T_{n}^{1} and T_{n}^{2} . In particular, the difference between the number of leaves in the two trees is precisely captured by |{\mathcal{S}}_{1\times}(n)|-|{\mathcal{S}}_{\times 1}(n)|=(n+1)(L_{1}(n)-L_{2}(n)) . Deriving stochastic recursions. The first step of the analysis is to characterize the evolution of the set sizes |{\mathcal{S}}_{11}(n)|,|{\mathcal{S}}_{1\times}(n)| and |{\mathcal{S}}_{\times 1}(n)|,|{\mathcal{S}}_{\times\times}(n)| , which depend on the sequence of aligned and independent choice steps in the joint construction of the two trees. As an example, consider the evolution of |{\mathcal{S}}_{11}(n)| . We first note that when vertex n+1 is added, it is clearly a leaf in both trees; thus n+1\in{\mathcal{S}}_{11}(n+1) . Depending on the type of choice (aligned or independent) and the specific connections made by vertex n+1 , some vertices in {\mathcal{S}}_{11}(n) may not be present in {\mathcal{S}}_{11}(n+1) . We outline the possibilities below: • Aligned choice. If n+1 attaches to vertex u in both trees and u\in{\mathcal{S}}_{11}(n) , then u\notin{\mathcal{S}}_{11}(n+1) . Otherwise, all vertices in {\mathcal{S}}_{11}(n) are also present in {\mathcal{S}}_{11}(n+1) . Hence |{\mathcal{S}}_{11}(n+1)|-|{\mathcal{S}}_{11}(n)|=1-\mathbf{1}(u\in{\mathcal{S}}_{11}(n)). • Independent choice. Suppose that n+1 attaches to u^{1} in T_{n}^{1} and u^{2} in T_{n}^{2} . If u^{1}\in{\mathcal{S}}_{11}(n) , then u^{1}\notin{\mathcal{S}}_{11}(n+1) . The same logic holds for u^{2} . Consequently, |{\mathcal{S}}_{11}(n+1)|-|{\mathcal{S}}_{11}(n)|=1-\mathbf{1}(u^{1}\in{\mathcal{S}}_{11}(n))-\mathbf{1}(u^{2}\in{\mathcal{S}}_{11}(n))+\mathbf{1}(u^{1}=u^{2}\text{ and }u^{1}\in{\mathcal{S}}_{11}(n)), where the addition of the third indicator is due to double-counting by the first two indicators when u^{1}=u^{2} . Putting everything together, we obtain the recursion \displaystyle\mathbb{E}\left[|{\mathcal{S}}_{11}(n+1)||{\mathcal{F}}_{n}\right] \displaystyle=|{\mathcal{S}}_{11}(n)|+1-\frac{\alpha|{\mathcal{S}}_{11}(n)|}{n+1}-(1-\alpha)\left(\frac{2|{\mathcal{S}}_{11}(n)|}{n+1}-\frac{|{\mathcal{S}}_{11}(n)|}{(n+1)^{2}}\right) \displaystyle=|{\mathcal{S}}_{11}(n)|+1-(2-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{n+1}+(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{(n+1)^{2}}. The normalized set size evolves as \mathbb{E}\left[\left.\frac{|{\mathcal{S}}_{11}(n+1)|}{n+2}\right|{\mathcal{F}}_{n}\right]=\frac{|{\mathcal{S}}_{11}(n)|}{n+1}+\frac{1}{n+2}\left(1-(3-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{n+1}+(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{(n+1)^{2}}\right), (A.1) and similar arguments give the following recursions for |{\mathcal{S}}_{1\times}(n)| and |{\mathcal{S}}_{\times 1}(n)| , \begin{split}\mathbb{E}\biggl[&\left.\frac{|{\mathcal{S}}_{1\times}(n+1)|}{n+2}\right|{\mathcal{F}}_{n}\biggr]\\ &=\frac{|{\mathcal{S}}_{1\times}(n)|}{n+1}+\frac{1}{n+2}\left(-\frac{2|{\mathcal{S}}_{1\times}(n)|}{n+1}+(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{n+1}-(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{(n+1)^{2}}\right),\end{split} (A.2) \begin{split}\mathbb{E}\biggl[&\left.\frac{|{\mathcal{S}}_{\times 1}(n+1)|}{n+2}\right|{\mathcal{F}}_{n}\biggr]\\ &=\frac{|{\mathcal{S}}_{\times 1}(n)|}{n+1}+\frac{1}{n+2}\left(-\frac{2|{\mathcal{S}}_{\times 1}(n)|}{n+1}+(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{n+1}-(1-\alpha)\frac{|{\mathcal{S}}_{11}(n)|}{(n+1)^{2}}\right).\end{split} (A.3) Asymptotic normality. Well-established results on stochastic approximation such as Fabian 1968 and Hernandez and Spall 2019 allow us to characterize the limiting distribution of the iterates |{\mathcal{S}}_{11}(n)|/n,|{\mathcal{S}}_{1\times}(n)|/n , and |{\mathcal{S}}_{\times 1}(n)|/n . By applying known results to the coupled stochastic recursion ( A.1 ), ( A.2 ), and ( A.3 ), we obtain that \sqrt{n}\begin{pmatrix}\frac{|{\mathcal{S}}_{1\times}(n)|}{n}-\frac{1-\alpha}{2(3-\alpha)}\\ \frac{|{\mathcal{S}}_{\times 1}(n)|}{n}-\frac{1-\alpha}{2(3-\alpha)}\\ \frac{|{\mathcal{S}}_{11}(n)|}{n}-\frac{1}{3-\alpha}\end{pmatrix}\stackrel{{\scriptstyle d}}{{\to}}{\mathcal{N}}\left(0,Q\right), (A.4) where Q is a 3\times 3 matrix with entries given by \displaystyle Q_{33} \displaystyle=\frac{4-3\alpha}{(3-\alpha)^{2}(5-2\alpha)} \displaystyle Q_{23}=Q_{32} \displaystyle=\frac{(1-\alpha)(4\alpha-17)}{2(3-\alpha)^{2}(5-2\alpha)(4-\alpha)} \displaystyle Q_{22} \displaystyle=-\frac{(1-\alpha)(2\alpha^{3}-23\alpha^{2}+105\alpha-192)}{12(4-\alpha)(3-\alpha)^{2}(5-2\alpha)} \displaystyle Q_{13}=Q_{31} \displaystyle=\frac{(1-\alpha)(4\alpha-17)}{2(3-\alpha)^{2}(5-2\alpha)(4-\alpha)} \displaystyle Q_{12}=Q_{21} \displaystyle=\frac{(1-\alpha)(2\alpha^{4}-15\alpha^{3}+25\alpha^{2}+12\alpha+12)}{12(4-\alpha)(3-\alpha)^{2}(5-2\alpha)} \displaystyle Q_{11} \displaystyle=-\frac{(1-\alpha)(2\alpha^{3}-23\alpha^{2}+105\alpha-192)}{12(4-\alpha)(3-\alpha)^{2}(5-2\alpha)}. The form of the matrix Q is computed based on the stochastic approximation results of Hernandez and Spall 2019 . At a high level, the calculation first involves computing the covariance matrix of the martingale differences corresponding to the stochastic recursion of interest, and applying a certain recursive, entry-wise transformation to compute Q . We make a few remarks about the asymptotic normality result ( A.4 ) and its relation to known results. • When \alpha=1 , the two jointly generated trees are identical, and the number of leaves in each tree is captured by {\mathcal{S}}_{11}(n) . The display in ( A.4 ) shows that |{\mathcal{S}}_{11}|/n concentrates around 1/2 in this case, with asymptotically normal fluctuations of variance Q_{33}=1/12 . This recovers known distributional results on the number of leaves in a single UA tree; see Janson 2005 . • For any \alpha\in[0,1] , the fraction of leaves in T_{n}^{1} is equal to L_{1}(n)=(|{\mathcal{S}}_{11}(n)|+|{\mathcal{S}}_{1\times}(n)|)/n . According to ( A.4 ), this concentrates around 1/2 with asymptotically normal fluctuations of variance Q_{33}+Q_{11}+2Q_{13}=1/12 . Hence the marginal characterization of leaves in a single UA tree aligns with the results of Janson 2005 . Distributional differences in the fraction of leaves. The convergence in ( A.4 ) implies that \sqrt{n}(L_{1}(n)-L_{2}(n))\stackrel{{\scriptstyle d}}{{\to}}{\mathcal{N}}\left(0,\frac{(1-\alpha)(3+\alpha)}{6(3-\alpha)}\right). (A.5) Thus, we can use the difference between the fraction of leaves in the two trees as a differentiating statistic. Specifically, if (T_{n}^{1},T_{n}^{2})\sim\mathrm{UA}(n)^{\otimes 2} , then \sqrt{n}(L_{1}(n)-L_{2}(n))\stackrel{{\scriptstyle d}}{{\to}}{\mathcal{N}}\left(0,1/6\right) , while if (T_{n}^{1},T_{n}^{2})\sim\alpha{\text{-}}\mathrm{CUA}(n) , then \sqrt{n}(L_{1}(n)-L_{2}(n))\stackrel{{\scriptstyle d}}{{\to}}{\mathcal{N}}\left(0,\sigma_{\alpha}^{2}\right) , where recall that \sigma_{\alpha}^{2}:=\frac{(1-\alpha)(3+\alpha)}{6(3-\alpha)} . This proves Theorem A.1 by noting that \sigma_{\alpha}^{2}\neq 1/6 for \alpha>0 . Since \sigma_{\alpha}\to 0 as \alpha\to 1 , it is straightforward to see that \mathrm{TV}\left(\mathrm{UA}(n)^{\otimes 2},\alpha{\text{-}}\mathrm{CUA}(n)\right)\to 1 as \alpha\to 1 and n\to\infty . For example, if X_{\alpha}=\sigma_{\alpha}Z and Y=\sqrt{1/6}Z with Z\sim{\mathcal{N}}(0,1) , then as \alpha\to 0 , we have \mathbb{P}(\lvert X_{\alpha}\rvert>\sqrt{\sigma_{\alpha}})=\mathbb{P}(\lvert Z\rvert>1/\sqrt{\sigma_{\alpha}})\to 0 and \mathbb{P}(\lvert Y\rvert>\sqrt{\sigma_{\alpha}})=\mathbb{P}(\lvert Z\rvert>\sqrt{6\sigma_{\alpha}})\to 1 . Beyond leaves. A natural question is whether comparing the fraction of higher degree vertices across the two trees can allow us to distinguish \mathrm{UA}(n)^{\otimes 2} and \alpha{\text{-}}\mathrm{CUA}(n) with power close to 1. While we expect that asymptotic normality can be established for joint degree counts in a similar sense as ( A.4 ), the corresponding more general covariance matrix Q does not seem to admit a tractable representation for analysis. Even if there is no closed form for Q , understanding its qualitative properties would shed insight into the joint structure of correlated UA trees and may also lead to better algorithms for identifying and estimating correlated regions in the two trees.