The Phylogenetic Structure of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity: Covariance Matrix Sparsification of Critical Beta-splitting Trees Authors: Sean P. Svihla, Manuel E. Lladser Published: 2026 ABSTRACT Haar-like wavelets sparsify the phylogenetic covariance matrices of large, uniformly random k-regular trees with overwhelmingly high probability. This motivates the Haar-like distance, a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metric that implicitly ranks the splits of a reference phylogeny by their relevance in differentiating two microbial environments, offering an interpretation as to why the environments differ compositionally. Nevertheless, uniform binary trees exhibit statistical features distinct from those of the trees used by practitioners, leaving the extent of sparsification and the practical validity of the implied Haar-like distance speculative. To address this, our manuscript examines the sparsification of phylogenetic covariance matrices of large critical beta-splitting random trees, a model introduced to better reflect real-world phylogenies. By obtaining sharp asymptotic estimates of the first and second moments of the external path length in this ensemble, we demonstrate that the Haar-like basis also pseudo-diagonalizes the phylogenetic covariance matrix of most large trees in this more realistic framework. Additionally, we devise a test to assess the statistical significance of splits in the reference phylogeny identified by the Haar-like distance. We apply the test to a well-studied microbial mat to further substantiate the presumption that the identified splits represent genuine biological signals differentiating the top and bottom layers of the mat. Introduction In fields such as microbiology, phylogenetic trees arise as models of inter-species covariance (Fukuyama et al. 2012; Pavoine et al. 2004). This prior phylogenetic structure is incorporated into the definition of notable \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics, which quantify difference between environments in terms of species composition. For instance, UniFrac (Lozupone and Knight 2005; Lozupone et al. 2011) uses the notion of shared branch length between samples to capture the relative abundance of observed organisms; on the other hand, DPCoA (Pavoine et al. 2013) directly incorporates the induced covariance matrix of the phylogenetic tree. Phylogenetic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics, and especially UniFrac, have had great success in meaningfully ordinating microbial environments based only on their relative abundances of species (Lozupone et al. 2007; Pavoine et al. 2004); however, as newer and more sophisticated reference phylogenies grow larger in size, such metrics face two notable challenges: Phylogenetic covariance matrices are often fully or almost fully dense, so that for large datasets their manipulation is a computational challenge;Traditional phylogenetic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics do not provide any indication of why two microbial environments are different, limiting their usefulness as exploratory tools.Fortunately, phylogenetic covariance matrices bear a surprisingly rich structure due to redundancies induced by their hierarchies— in fact, they exactly comprise a set of highly structured matrices called ultrametric— and this structure may be exploited to make computations tenable (Gorman and Lladser 2023). Phylogenetic covariance matrices are often fully or almost fully dense, so that for large datasets their manipulation is a computational challenge; Phylogenetic covariance matrices are often fully or almost fully dense, so that for large datasets their manipulation is a computational challenge; Traditional phylogenetic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics do not provide any indication of why two microbial environments are different, limiting their usefulness as exploratory tools. Traditional phylogenetic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics do not provide any indication of why two microbial environments are different, limiting their usefulness as exploratory tools. Ultrametric matrices arise in probability theory and statistical physics, among other fields, and, under mild assumptions, arise as covariance matrices of phylogenetic trees. As shown in Nabben and Varga (1994), a square matrix C is ultrametric if and only if there exists a rooted binary tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T = (V, E)$$\end{document}T=(V,E) and function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell :E\rightarrow \mathbb {R}_{+}$$\end{document}ℓ:E→R+ such that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ C = \sum _{e\in E}\ell (e)\,\delta _e \delta ^T_e, $$\end{document}C=∑e∈Eℓ(e)δeδeT,where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta _e$$\end{document}δe is a binary column vector with entries indexed by the leaves of T, indicating those that descend from an edge e. This identity is equivalent to1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \forall i, j\in L, \quad C(i,j) = \sum _{e\in [i\wedge j, \circ ]}\ell (e), \end{aligned}$$\end{document}∀i,j∈L,C(i,j)=∑e∈[i∧j,∘]ℓ(e),where L is the leaf set of T and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[i\wedge j,\circ ]$$\end{document}[i∧j,∘] denotes the set of edges connecting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(i\wedge j)$$\end{document}(i∧j), the least common ancestor of leaves i and j, with the root of the tree, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\circ $$\end{document}∘. In the setting of rooted trees, a matrix with entries such as in (1) is called a phylogenetic covariance matrix. This formulation is sensible when edge lengths are interpreted as measures of common evolutionary history, in a genetic sense, in which case it aligns with one’s intuition that species that co-evolved for more of their evolutionary history should thrive or struggle similarly in similar environments. Notably, if edge lengths are taken to be measures of evolutionary time, then the formulation of phylogenetic covariance in (1) is equivalent to a model of neutral evolution wherein the average value of a trait in a population follows a Brownian motion (e.g., (Hansen and Martins 1996; Harmon 2019)). Under this model, trait variation between lineages evolves as independent Brownian motions from the time the lineages diverge, and accordingly the covariance in (1) is their shared path length to the root—a proxy for time before evolutionary divergence. Recent work has demonstrated that the phylogenetic covariance matrix associated with a large, uniformly-at-random binary tree (Gorman and Lladser 2023) or more generally k-regular tree (Svihla and Lladser 2024) tree is pseudo-diagonalized (i.e., significantly sparsified) with high probability after changing basis to the so-called Haar-like wavelets (Gavish et al. 2010) of the tree. In particular, the fraction of non-zero off-diagonal entries in the transformed matrix converges in probability to zero as the size of the tree approaches infinity. Such sparsification grants a significant storage reduction and enables computational manipulation of the covariance matrix by enabling sparse algorithms on the otherwise prohibitively large matrix. In Gorman and Lladser (2023) the Haar-like basis was used to pseudo-diagonalize the covariance matrix of the 97% Greengenes tree, a widespread reference phylogeny in earlier metagenomic studies (DeSantis et al. 2006; McDonald et al. 2012). In turn, this motivated the introduction of a new \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metric, the Haar-like distance (Gorman and Lladser 2023), which, unlike its predecessors, may highlight the mutations—and consequently the biological functions—that best explain differences in microbial relative abundance between two environments. More recently, using the same reference phylogeny, Gorman and Lladser (2024) showed that a kernel derived from Haar-like wavelets can be optimized against a random forest in order to learn a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metric, the adapted Haar-like distance, that preserves much of the random forest’s accuracy but renders its discrimination rules interpretable in terms of splits along the tree. This high sparsification of a phylogenetic covariance matrix results from the multiscale nature of the Haar-like wavelets and the matrix structure, and it requires that the tree be shaped appropriately (in a sense that will be specified below) to be effective. Not all families of trees are so well behaved (for example, the phylogenetic covariance matrices of binary caterpillar trees are not sparsified by the Haar-like wavelets). The results in Gorman and Lladser (2023); Svihla and Lladser (2024) depend on the characteristics of the uniform binary tree ensemble. As a consequence, inasmuch as the uniform ensemble falls short of modeling real-world phylogenies, such results may not generalize beyond the 97% Greengenes tree. In fact, Aldous (2001) observed that the median size of the smaller subtree after a split in trees with n leaves scales as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{O}\left( n^{1/2}\right) $$\end{document}On1/2 in real-world phylogenies, whereas under a uniform distribution it scales as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{O}\left( \log n\right) $$\end{document}Ologn. Because tree balance is related to subtree split size and plays a key role in sparsification under the Haar-like basis, this fact brings into question whether the wavelets will be as effective at sparsifying the covariance matrices of large trees used by practitioners. Our manuscript considers a more realistic random tree model, the critical beta-splitting random tree, introduced by Aldous (1996) as one better suited for real-world phylogenies (see also Aldous (2001)). After a detailed asymptotic analysis of the first and second moments of the external path length in a large random tree from this ensemble— complementing recent results in Aldous and Janson (2024a, 2024b) and extending some of Aldous and Pittel (2025); Aldous and Janson (2024c)— we show that the Haar-like basis pseudo-diagonalizes with overwhelmingly high probability the phylogenetic covariance matrix of large critical beta-splitting random trees. In particular, the effects of the Haar-like wavelets on the phylogenetic convariance matrix of the 97% Greengenes tree may not have been merely coincidental and could generalize to a much wider range of phylogenies, including new and more detailed ones being developed for metagenomic studies such as Greengenes2 (McDonald et al. 2024), SILVA (Quast et al. 2013; Yilmaz et al. 2014), and WoL (Zhu et al. 2019). Further, we build upon the analysis in Gorman and Lladser (2023) of the Guerrero Negro microbial mat samples in Kirk Harris et al. (2013) by devising a hypothesis test with which to assess the statistical significance of dominant components of the Haar-like distance. Importantly, the results further substantiate the claim that dominant components represent genuine biological signal that is not explainable by sampling variance or other random effects. In the remainder of the introduction, we briefly introduce some notation and terminology and provide an overview of concepts and properties relevant for presenting and proving our new results. Notation and Terminology Throughout the manuscript, we regard functions from L to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}$$\end{document}R interchangeably as vectors. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\!\!1_{A}(x)$$\end{document}1A(x) denotes the indicator function over set A. We use standard terminology for trees. We consider planted, ordered, and unlabelled trees. In particular, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=(V,E)$$\end{document}T=(V,E) is a rooted tree with vertex set V and edge (branch) set E. We denote its root by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\circ $$\end{document}∘. Because T is planted, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\circ $$\end{document}∘ has degree one, i.e., only one edge is connected to it. The sets of leaves and interior nodes of T are denoted by L and I, respectively, and the size of the tree is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T|:=|L|$$\end{document}|T|:=|L|, the number of leaves. By convention, we label the leaves of the tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i=1, 2, \ldots , |T|$$\end{document}i=1,2,…,|T| in the order they are encountered in its postorder traversal (i.e., their left-to-right order). See Figure 1 for an illustration. The depth of a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in V$$\end{document}v∈V, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{depth}\,}}\left( v\right) $$\end{document}depthv, is its edge-distance to the root. The external path length of T is the quantity2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} {{\,\textrm{EPL}\,}}\left( T\right) = \sum _{i\in L}{{\,\textrm{depth}\,}}\left( i\right) . \end{aligned}$$\end{document}EPLT=∑i∈Ldepthi.Each tree is equipped with an edge length function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell :E\rightarrow \mathbb {R}_{+}$$\end{document}ℓ:E→R+. We denote by C the phylogenetic covariance matrix of T, i.e., with entries as defined in (1). The Haar-like Wavelets We first define Haar-like wavelets associated with a planted binary tree. See Gavish et al. (2010) for details regarding the construction of the wavelets, and Gorman and Lladser (2023); Svihla and Lladser (2024) for their use in the context of phylogenetic trees.Fig. 1An illustration of a planted binary tree and associated Haar-like wavelets. Left: A balanced binary tree with leaves labelled 1, 2, 3, 4 and interior nodes labelled \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}α, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}γ. Note that the trees we consider need not be balanced. Right: The Haar-like wavelets associated with the tree on the left. Each wavelet is associated with a split in the tree and defined to be positive over the leaves of the left subtree and negative over those of the right. (Color Figure Online) An illustration of a planted binary tree and associated Haar-like wavelets. Left: A balanced binary tree with leaves labelled 1, 2, 3, 4 and interior nodes labelled \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}α, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}γ. Note that the trees we consider need not be balanced. Right: The Haar-like wavelets associated with the tree on the left. Each wavelet is associated with a split in the tree and defined to be positive over the leaves of the left subtree and negative over those of the right. (Color Figure Online) Definition 1.1 (Gorman and Lladser 2023) The Haar-like basis associated with the tree T is the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\{\phi _v\}}_{v\in I}$$\end{document}{ϕv}v∈I defined as follows:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \phi _\circ (i)&= \frac{1}{\sqrt{|L|}}, \quad \forall i\in L; \\ \phi _v(i)&= \sqrt{\frac{|L(v_{\scriptscriptstyle +})|}{|L(v_{\scriptscriptstyle -})|\cdot |L(v)|}}\cdot 1\!\!1_{L(v_{\scriptscriptstyle -})}(i) - \sqrt{\frac{|L(v_{\scriptscriptstyle -})|}{|L(v_{\scriptscriptstyle +})|\cdot |L(v)|}}\cdot 1\!\!1_{L(v_{\scriptscriptstyle +})}(i), \quad v\ne \circ ; \end{aligned}$$\end{document}ϕ∘(i)=1|L|,∀i∈L;ϕv(i)=|L(v+)||L(v-)|·|L(v)|·1L(v-)(i)-|L(v-)||L(v+)|·|L(v)|·1L(v+)(i),v≠∘;where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_-$$\end{document}v- and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_+$$\end{document}v+ denote the left and right children of v, respectively. The functions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _v$$\end{document}ϕv, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in I$$\end{document}v∈I, are mutually orthogonal with respect to the standard inner-product in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^{|L|}$$\end{document}R|L|, and form a basis for the linear space of functions from L to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}$$\end{document}R. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Phi $$\end{document}Φ denote the Haar-like basis matrix (i.e., the matrix with columns \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _v$$\end{document}ϕv for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in I$$\end{document}v∈I). It was shown in (Gorman and Lladser, 2023, Theorem 2.3) for binary trees and as a corollary to (Svihla and Lladser, 2024, Theorem 2) for k-regular trees that3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} (\Phi ^T C \Phi )(u,v) = \phi _u^T {{\,\textrm{diag}\,}}\left( \ell ^*(L, v)\right) \phi _v. \end{aligned}$$\end{document}(ΦTCΦ)(u,v)=ϕuTdiagℓ∗(L,v)ϕv.(The trace length of T is the function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell ^*:E\rightarrow \mathbb {R}_{+}$$\end{document}ℓ∗:E→R+ defined as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell ^*(e) = |L(e)|\cdot \ell (e)$$\end{document}ℓ∗(e)=|L(e)|·ℓ(e), where L(e) are the set of leaves that descend from an edge e.) As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\Phi ^T C\Phi )(u,v) = 0$$\end{document}(ΦTCΦ)(u,v)=0 whenever \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _u$$\end{document}ϕu and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _v$$\end{document}ϕv have disjoint supports. By counting such interactions, one obtains the following (Gorman and Lladser, 2023, Corollary 3.5):4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} {If {{\,\textrm{EPL}\,}}\left( T\right) \ll |T|^2, then \xi \!=\! 1 \!-\! \textrm{o}\left( 1\right) }; \end{aligned}$$\end{document}IfEPLT≪|T|2,thenξ=1-o1;where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi $$\end{document}ξ denotes the proportion of non-zero, off-diagonal entries, in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Phi ^T C\Phi $$\end{document}ΦTCΦ. In particular, (Gorman and Lladser, 2023, Theorem 3.4) gives the bound5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} (1 - \xi ) \le 2\frac{{{\,\textrm{EPL}\,}}\left( T_n\right) + 1}{n^2} - \frac{3}{n}. \end{aligned}$$\end{document}(1-ξ)≤2EPLTn+1n2-3n.If the condition in (4) is satisfied, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Phi ^T C\Phi $$\end{document}ΦTCΦ is pseudo-diagonal, i.e., nearly all of its off-diagonal entries are zero. This property is the key reason why wavelets may significantly reduce computations when working with tree phylogenetic covariance matrices. The Critical Beta-Splitting Random Tree The critical beta-splitting ensemble is a special case of a one-parameter family of random binary trees introduced by Aldous (1996), called beta-splitting models. These models generate a tree by a random, recursive binary partitioning of [n] according to a splitting probability distribution q(n, i), \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i=1,\ldots ,n-1$$\end{document}i=1,…,n-1, which determines the probability that [n] is split into clades of size i and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n-i)$$\end{document}(n-i), respectively. The critical beta-splitting tree model uses6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q(n,i):=\frac{n}{2h_{n-1}}\cdot \frac{1}{i(n-i)}, \quad 00$$\end{document}t>0, we aim to assess the statistical significance of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\,\Delta _v^2\,>\,t$$\end{document}λvΔv2>t following a permutation test principle (e.g., Evans and Matsen (2012)). Under the null hypothesis that the samples come from compositionally identical environments, the DNA reads are exchangeable across them. In particular, we mean that, given we have |a| samples from environment A and |b| from B, the vector of all samples \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{x}= (x_1, \dots , x_{|a|+|b|})$$\end{document}x=(x1,⋯,x|a|+|b|) is exchangebale, and the distribution of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(a,b) = (a(x_1, \dots , x_{|a|}), b(x_{|a|+1},\dots , x_{|a|+|b|}))$$\end{document}(a,b)=(a(x1,⋯,x|a|),b(x|a|+1,⋯,x|a|+|b|)) is invariant under permutations of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{x}$$\end{document}x. Consequently, we may estimate the cumulative distribution function (c.d.f.) of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2 by resampling a, drawing without replacement |a| of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|a|+|b|$$\end{document}|a|+|b| OTUs, and reassigning the unselected OTUs to b. After each resample, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2 is recomputed from the resampled vectors of OTU counts from each environment; these recomputed values are then used to estimate empirically the c.d.f. of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2. The p-value reported to assess the statistical significance of the Haar-component associated with v in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_h(a,b)$$\end{document}dh(a,b) is the empirical probability that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2>t$$\end{document}λvΔv2>t. We note that according to the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality (Dvoretzky et al. 1956; Massart 1990), estimating the c.d.f. within an infinity-norm error of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}ϵ, with probability \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1 - \delta )$$\end{document}(1-δ), requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N=\log (2/\delta )/(2\,\epsilon ^2)$$\end{document}N=log(2/δ)/(2ϵ2) resamples. In practice, we resample a by drawing the OTU counts from a multivariate hypergeometric distribution with parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(|a|; a+b)$$\end{document}(|a|;a+b) (Johnson 2005; Johnson et al. 1997), rather than by brute-force permutations. We provide fast hypergeometric and multivariate hypergeometric samplers on GitHub (see our Data Availability Statement in Section 4), which implements the algorithm described in Hörmann (1994) based on the rejection-inversion sampler for the tail of a log-concave distribution described in Hörmann and Derflinger (1996). This package is used to define an estimator for the c.d.f. of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2 under the null hypothesis. Further, it is implemented so that no significant additional computational expense is incurred by estimating the c.d.f.s of multiple Haar-components at once, nor by estimating one or more c.d.f.s at multiple points. While the dominant Haar-components help identify the most relevant splits in terms of the Haar-like distance, we are not limited to considering only these components. By filtering Haar-components with the permutation test, one is able to distinguish genuine environmental differences from random effects at finer scales, where it would be impossible to deduce from the Haar-component magnitudes alone. This can be accomplished by defining\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \tilde{\Delta }_v:= {\left\{ \begin{array}{ll} \Delta _v, & \text {if } \lambda _v\Delta _v^2 \text { is statistically significant};\\ 0, & \text {otherwise}. \end{array}\right. } $$\end{document}Δ~v:=Δv,ifλvΔv2is statistically significant;0,otherwise.Then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{\delta }:= \Phi \tilde{\Delta }_v$$\end{document}δ~:=ΦΔ~v, is the projection of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{\Delta }_v$$\end{document}Δ~v back to the standard basis, a proxy for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(a-b)$$\end{document}(a-b). Each of these Haar-components represents a dimension along which the observed environmental differences cannot be explained by chance; consequently, they constitute a (relatively) low-dimensional subspace in which to represent and study these environments. In practice, since there are many non-zero Haar-components, we assess the statistical significance after applying a Benjamini-Hochberg correction (Benjamini and Hochberg 1995). See Figure 5 for an example of this in practice. Proof-of-Concept: The Guerrero Negro Microbial Mat Fig. 6Plot of the twelve largest components of the Haar-like distance between top- and bottom-level 2013 samples from the Guerrero Negro microbial mat. Each point is marked according to whether the null hypothesis that these top and bottom samples are compositionally indistinguishable is rejected at the 5% significance level. We see that all but one of the top twelve dominant Haar-components pictured are statistically significant under our test. Each of these Haar-like components is readily interpretable in terms of splits in the reference phylogeny; our annotations include some potentially interesting interpretations of the dominant splits. (Color Figure Online) Table 1Statistical significance of the twelve most dominant Haar-components differentiating the shallowest and deepest samples in the 2013 Guerrero Negro study. We obtained p-values from the null empirical c.d.f. of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\,\Delta _v^2$$\end{document}λvΔv2 for each interior node v in the 97% Greengenes tree, using N resamples chosen according to the DKW inequality with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon = 0.0001$$\end{document}ϵ=0.0001 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta = 0.01$$\end{document}δ=0.01 (see Section 3.1). \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{v}$$\end{document}v \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\textbf {depth}}(v)}$$\end{document}depth(v) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{|L(v)|}$$\end{document}|L(v)| \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\lambda _v\Delta _v^2}$$\end{document}λvΔv2 p-Value 9931110952970.0488<4.53e-0860791817920.0048<4.53e-0867317348350.0047<4.53e-099930714500350.00466.762e-017116020144720.00451.322e-055923256000.0030<4.53e-085921272400.0029<4.53e-082799815207650.00203.985e-02711592148990.00143.234e-05679593214770.0013<4.53e-08682772720170.0011<4.53e-087116515218930.0010<4.53e-08Where the permutation algorithm failed to sample sufficiently far into the tail, returning zero, we report the discovery probability based on N. The reported p-values include a Bonferroni correction for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=12$$\end{document}m=12 hypotheses. For reference, the 97% Greengenes tree has a median leaf depth of 51 and a maximum leaf depth of 107. Components corresponding to deeper nodes capture finer-scale information. Remark: The Haar-component associated with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v=99311$$\end{document}v=99311 was misreported in Gorman and Lladser (2023) but is corrected here Plot of the twelve largest components of the Haar-like distance between top- and bottom-level 2013 samples from the Guerrero Negro microbial mat. Each point is marked according to whether the null hypothesis that these top and bottom samples are compositionally indistinguishable is rejected at the 5% significance level. We see that all but one of the top twelve dominant Haar-components pictured are statistically significant under our test. Each of these Haar-like components is readily interpretable in terms of splits in the reference phylogeny; our annotations include some potentially interesting interpretations of the dominant splits. (Color Figure Online) Table 1Statistical significance of the twelve most dominant Haar-components differentiating the shallowest and deepest samples in the 2013 Guerrero Negro study. We obtained p-values from the null empirical c.d.f. of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\,\Delta _v^2$$\end{document}λvΔv2 for each interior node v in the 97% Greengenes tree, using N resamples chosen according to the DKW inequality with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon = 0.0001$$\end{document}ϵ=0.0001 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta = 0.01$$\end{document}δ=0.01 (see Section 3.1). \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{v}$$\end{document}v \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\textbf {depth}}(v)}$$\end{document}depth(v) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{|L(v)|}$$\end{document}|L(v)| \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\lambda _v\Delta _v^2}$$\end{document}λvΔv2 p-Value 9931110952970.0488<4.53e-0860791817920.0048<4.53e-0867317348350.0047<4.53e-099930714500350.00466.762e-017116020144720.00451.322e-055923256000.0030<4.53e-085921272400.0029<4.53e-082799815207650.00203.985e-02711592148990.00143.234e-05679593214770.0013<4.53e-08682772720170.0011<4.53e-087116515218930.0010<4.53e-08Where the permutation algorithm failed to sample sufficiently far into the tail, returning zero, we report the discovery probability based on N. The reported p-values include a Bonferroni correction for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=12$$\end{document}m=12 hypotheses. For reference, the 97% Greengenes tree has a median leaf depth of 51 and a maximum leaf depth of 107. Components corresponding to deeper nodes capture finer-scale information. Remark: The Haar-component associated with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v=99311$$\end{document}v=99311 was misreported in Gorman and Lladser (2023) but is corrected here Statistical significance of the twelve most dominant Haar-components differentiating the shallowest and deepest samples in the 2013 Guerrero Negro study. We obtained p-values from the null empirical c.d.f. of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\,\Delta _v^2$$\end{document}λvΔv2 for each interior node v in the 97% Greengenes tree, using N resamples chosen according to the DKW inequality with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon = 0.0001$$\end{document}ϵ=0.0001 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta = 0.01$$\end{document}δ=0.01 (see Section 3.1). Where the permutation algorithm failed to sample sufficiently far into the tail, returning zero, we report the discovery probability based on N. The reported p-values include a Bonferroni correction for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=12$$\end{document}m=12 hypotheses. For reference, the 97% Greengenes tree has a median leaf depth of 51 and a maximum leaf depth of 107. Components corresponding to deeper nodes capture finer-scale information. Remark: The Haar-component associated with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v=99311$$\end{document}v=99311 was misreported in Gorman and Lladser (2023) but is corrected here Microbial mats are multi-layered biofilms of microbial communities, typically only a few centimeters thick at most, often fostering a rich biodiversity and exhibiting sharp variation in species composition across space and time (Dillon et al. 2009; Hörnlein et al. 2018). The Guerrero Negro microbial mat, located in Baja California Sur, Mexico, is one of the most well-studied mats (Ley et al. 2006; Lozupone and Knight 2007; Dillon et al. 2009; Maza-Márquez et al. 2024). In Kirk Harris et al. (2013), multiple samples from a single mat at Guerrero Negro were collected, sectioned into horizontal layers (at different depths reflecting the vertical stratification of the mat), and pooled within each layer. In this section, we assess the statistical significance of the twelve largest Haar-components differentiating the shallowest and deepest samples in this 2013 study. Since the samples in this study were collected concurrently, from the same pond, and nearby one another within a narrow radius, it is reasonable to assume that the OTU composition at each level is homogeneous. In particular, the pooled reads from each layer may be regarded as i.i.d. draws from a single probability distribution. This allows us to use the test in Section 3.1 to assess the statistical significance of the components of the Haar-like distance between samples from the top (0–1 mm) and bottom (34–49 mm) layers. We computed the Haar-like distance between the top and bottom samples using the OTU counts published to Qiita (study ID 1200), derived from closed-reference clustering of 454 reads against the 97% Greengenes tree (Kirk Harris et al. 2013; McDonald et al. 2012). Out of 4271 non-zero Haar-components, 956 had a raw p-value less than 0.05 and 159 remained statistically significant after applying a Bonferroni correction.Fig. 7Relative taxonomic composition breakdown between top and shallow samples from Guerrero Negro. Differences in relative abundance of OTUs between the deep layer (a) and the shallow layer (b) of the Guerrero Negro microbial mat beneath the splits of the six most dominant Haar-components. A positive x-value indicates prevalence in a over b, and a negative value indicates prevalence in b over a. Plots are ordered by descending value of the Haar-components from left to right and top to bottom. For each split v, the text box gives the lowest-level taxonomic rank shared by all OTUs in the respective subtree. Further, each OTU, i, beneath v is grouped into a class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_k$$\end{document}Ik by its taxonomic classification at the next lowest rank. The value reported is the aggregate change in relative abundance within each of these classes (i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{i\in I_k}{(a-b)}_i$$\end{document}∑i∈Ik(a-b)i). (Color Figure Online) Relative taxonomic composition breakdown between top and shallow samples from Guerrero Negro. Differences in relative abundance of OTUs between the deep layer (a) and the shallow layer (b) of the Guerrero Negro microbial mat beneath the splits of the six most dominant Haar-components. A positive x-value indicates prevalence in a over b, and a negative value indicates prevalence in b over a. Plots are ordered by descending value of the Haar-components from left to right and top to bottom. For each split v, the text box gives the lowest-level taxonomic rank shared by all OTUs in the respective subtree. Further, each OTU, i, beneath v is grouped into a class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_k$$\end{document}Ik by its taxonomic classification at the next lowest rank. The value reported is the aggregate change in relative abundance within each of these classes (i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{i\in I_k}{(a-b)}_i$$\end{document}∑i∈Ik(a-b)i). (Color Figure Online) In the case of this study, the Haar-like distance yields a wealth of subtle (yet nonetheless significant) relationships to explore between the top- and bottom-level environments. However, under the assumption that the largest Haar-components represent the most important splits (inasmuch as they contribute most to the magnitude of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_h(a,b)$$\end{document}dh(a,b)), we primarily concern ourselves with the several most dominant components. We will find support for this assumption when we observe that many of the compositional differences identified in Kirk Harris et al. (2013) are manifest in a small subset of dominant Haar-components. The twelve most dominant Haar-components are displayed in Figure 6, with nodes indexed in postorder traversal. Table 1 summarizes the findings of the permutation test. For all but one of the twelve dominant Haar-like components considered, the magnitude of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2 is statistically significant at the 5% level under the null hypothesis that the top- and bottom-level environments of the Guerrero Negro microbial mat are compositionally indistinguishable. The three most dominant Haar-components have also been deemed significant using a different criterion (Gorman and Lladser 2023). Figure 7 illustrates some of the dominant Haar-components in terms of the taxa found beneath their corresponding interior nodes. The most dominant component at node 99311 marks a split characterized by a prevalence of Cyanobacteria in the top layer relative to other bacterial phyla (such as Chloroflexi and Proteobacteria) in the bottom layer, as previously noted in Gorman and Lladser (2023). Nodes 6079, 5923, and 5921 mark splits exhibiting different responses to increasing mat depth within the phylum Cyanobacteria and, further, within the class Oscillatoriophycideae. Similarly, nodes 71159, 71160, and 71165 appear to capture the prevalence of the phylum Chloroflexi over the other bacterial phyla marked off from Cyanobacteria by node 99311. In turn, node 68277 marks a different response by the class Anaerolineae as compared with other members of Chloroflexi, with nodes 67317 and 67959 further delineating distinct responses within Anaerolineae. Finally, node 27998 marks a split within Proteobacteria revealing an increase in Alphaproteobacteria and a decrease in Betaproteobacteria and Gammaproteobacteria between the top and bottom environments. The dominant Haar-components suggest a gradient between the top and bottom layers marked by a shift from an oxic, high-light environment populated by oxygenic phototrophs to an anoxic, low-light environment populated by anoxygenic phototrophs (Kurth et al. 2021; Kawai et al. 2021). Such a spatial gradient has been widely observed and studied in microbial mats (Ley et al. 2006; Lozupone and Knight 2007; Dillon et al. 2009; Kirk Harris et al. 2013; McDonald et al. 2012; Hörnlein et al. 2018; Maza-Márquez et al. 2024). It is noteworthy, then, that the Haar-like distance implicitly identifies a low-dimensional space, the (Haar-like) coordinates of which are directly interpretable in terms of such a gradient. Unlike the other twelve most dominant Haar-components, node 99307, associated with the fourth dominant component, is not statistically significant at the 5% level of the permutation test. It was noted in Gorman and Lladser (2023) that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _v\Delta _v^2$$\end{document}λvΔv2 depends on the difference between the averages of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f=(a/|a|-b/|b|)$$\end{document}f=(a/|a|-b/|b|) on the leaves of the left- and right-subtrees of an interior node v. Upon inspection, however, one finds that the top and bottom layers are composed overwhelmingly of OTUs from the left-subtree, although their compositions within that subtree differ. The comparatively large magnitude of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _{99307}\Delta _{99307}^2$$\end{document}λ99307Δ993072 is therefore not due to a difference in OTU composition between environments across the split, but rather to a prevalence of OTUs from one subtree in both environments, contrasted with a shared lack of abundance in the other. In other words, the split does not correspond to a compositional difference between environments; rather, both are characterized by a prevalence of left-subtree OTUs. The permutation test is robust to such artifacts, and the Haar-component appears non-significant accordingly. Final Remarks Phylogenetically informed \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metrics such as UniFrac and DPCoA have found widespread use and success in metagenomics. DPCoA is defined in terms of a covariance matrix derived from a reference phylogeny and often leads to qualitatively similar conclusions to UniFrac. This manuscript is motivated by two shortcomings of such metrics: (i) the covariance matrix is often large and dense, making computational manipulation is expensive and potentially infeasible; and (ii) these metrics are not readily interpretable in terms of the phylogeny. Previous work has shown that the Haar-like basis and distance can address these concerns, ultimately due to the tendency of the Haar-like basis to significantly sparsify the phylogenetic covariance matrix of large phylogenetic trees chosen uniformly at random. However, because the significant sparsification relies heavily on the statistical properties of these random tree models, it was unclear whether it holds for large phylogenetic trees with features consistent with those used by practitioners. We have addressed this issue by deriving sparsification results similar to those but under the more realistic critical beta-splitting model of random binary trees. In particular, by obtaining sharp asymptotic estimates of the first and second moments of the external path length of the trees in this ensemble, we have shown that the Haar-like basis is highly effective at sparsifying all but a negligible fraction of large trees produced by this model. It remains an open problem to determine the rate at which \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) / n^2$$\end{document}EPLTn/n2 converges to 0 under the critical beta-splitting model. A notable limitation of the critical beta-splitting ensemble is its inability to model polytomies, which occur in many real-world phylogenies, especially in newer models. The feasibility of deriving analogous results for non-binary trees in principle is evidenced by Svihla and Lladser (2024), who treat the case of uniform random k-regular trees. However, formulating and deriving appropriate asymptotic results for a generalized critical beta-splitting model remains an open problem. Our preliminary analysis of large phylogenies with polytomies indicates—at least in the case of the Greengenes2 tree (McDonald et al. 2024)—that the binary portion of the tree (i.e., excluding polytomies) has a median minor split size structure similar to that of the critical beta-splitting model. Furthermore, the number of polytomies in the tree is small enough that, even assuming all entries corresponding to non-binary splits are non-zero, the degree of sparsification is virtually unchanged. These findings suggest that our method remains capable of pseudo-diagonalizing the phylogenetic covariance matrices associated with certain non-binary trees. In addition to enabling the sparsification of large, dense phylogenetic covariance matrices, the Haar-like basis motivates the definition of the Haar-like distance, a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β-diversity metric which importantly provides an implicit ranking of the splits in the reference phylogeny by order of their relevance in differentiating between two microbial environments. Still, it is not obvious that these dominant coordinates successfully parse genuine signal from noise. To address this uncertainty, we devised a permutation test based on the null hypothesis that a pair of environmental samples were drawn from two environments which are compositionally indistinguishable. The result of this test allows one to conclude when the magnitude of a particular Haar-like distance component is not plausibly explainable by random effects between samples from identical environments. In the proof-of-concept considered here, we found that all but one of the twelve most dominant Haar-like components were highly statistically significant, and that these components described many of the macro-level compositional-environmental differences identified in the original study. In particular, the dominant Haar-components suggested a gradient between the top and bottom layers of the Guerrero Negro microbial mat which is characterized by a shift from an oxic, high-light environment populated by oxygenic phototrophs to an anoxic, low-light environment populated by anoxygenic phototrophs—a spatial gradient which is well-known and widely observed in microbial mats like those at Guerrero Negro. While we have chosen a well-studied environment as proof-of-concept, this behavior supports the use of the Haar-like distance as an exploratory tool in understudied environments, where dominant Haar components may reveal unknown gradients. Our analysis shows that the technique of sparsifying dense phylogenetic covariance matrices by a change-of-basis to the Haar-like wavelets is well-justified under the critical beta-splitting model. The fact that we obtain similar sparsification-in-probability results under this more realistic model suggests that the previously observed sparsification on the 97% Greengenes tree was not coincidental, but rather reflects a general behavior of real-world phylogenetic covariance matrices with respect to the Haar-like basis. Furthermore, our demonstration of a permutation test on samples from the Guerrero Negro microbial mat substantiates the claim that dominant components capture genuine biological signals, while offering a method to study subtle—yet statistically significant—differences between environments. Proof of Theorem 2.1 In this section, we present the proof of Theorem 2.1, which is comprised mostly of Lemmas 5.4 and 5.5. Our arguments are overall inspired by those of (Aldous and Pittel, 2025, Theorem 2.6). In particular, recall that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_n$$\end{document}Ln denotes the edge-depth of a leaf selected uniformly at random in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_n$$\end{document}Tn and that first moment of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_n$$\end{document}Ln obeys the recursion (Aldous and Pittel, 2025, (44))12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( L_n\right) = 1 + \frac{1}{h_{n-1}}\sum _{i=1}^{n-1}\frac{\mathbb {E}\left( L_i\right) }{n-i}. \end{aligned}$$\end{document}ELn=1+1hn-1∑i=1n-1ELin-i.We make use of asymptotic formulas for the mean and variance of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_n$$\end{document}Ln (Aldous and Pittel, 2025, Theorem 1.2):13\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( L_n\right)&= \frac{1}{2\zeta _2}\log ^2(n) + \frac{\gamma \zeta _2+\zeta _3}{\zeta _2^2}\log (n) + \textrm{O}\left( 1\right) \end{aligned}$$\end{document}ELn=12ζ2log2(n)+γζ2+ζ3ζ22log(n)+O114\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} {{\,\textrm{Var}\,}}\left( L_n\right)&= \frac{2\zeta _3}{3\zeta _2^3}\log ^3(n) + \textrm{O}\left( \log ^2(n)\right) , \end{aligned}$$\end{document}VarLn=2ζ33ζ23log3(n)+Olog2(n),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\zeta _s$$\end{document}ζs, for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s>1$$\end{document}s>1, is the Riemann-zeta function and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}γ is Euler’s constant. The following refinement of (13) will be particularly useful in our analysis (Aldous and Janson, 2024c, Theorem 1.2):15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( L_n\right) = \frac{1}{2\zeta _2}\log ^2(n) + \frac{\gamma \zeta _2+\zeta _3}{\zeta _2^2}\log (n) + b_0 + \textrm{O}\left( \frac{\log (n)}{n}\right) , \end{aligned}$$\end{document}ELn=12ζ2log2(n)+γζ2+ζ3ζ22log(n)+b0+Olog(n)n,where\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ b_0 = \frac{\gamma ^2}{2\zeta _2} + \frac{\gamma \zeta _3}{\zeta _2^2} + \frac{\zeta _3^2}{\zeta _2^3} + \frac{1}{10}. $$\end{document}b0=γ22ζ2+γζ3ζ22+ζ32ζ23+110.Lastly, we borrow from (Aldous and Pittel, 2025, Proposition 2.5, (22) and (23)) the identities16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \int _{0}^{1}x^j\log ^k(x)\,dx&= {(-1)}^k\frac{k!}{{(j+1)}^{k+1}} \end{aligned}$$\end{document}∫01xjlogk(x)dx=(-1)kk!(j+1)k+117\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \int _{0}^{1}\frac{\log ^k(x)}{1-x}\,dx&= {(-1)}^k\,k!\,\zeta _{k+1} \end{aligned}$$\end{document}∫01logk(x)1-xdx=(-1)kk!ζk+1for integers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j\ge 0$$\end{document}j≥0 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 1$$\end{document}k≥1. In addition, we make use the following technical lemmas, the proofs of which can be found in Appendix A. Lemma 5.1 For all integers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 0$$\end{document}k≥0:18\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} \int _{0}^{1}\log ^k(x) \log (1-x)\,dx = {(-1)}^{k}\,k!\left( \sum _{j=1}^{k}(\zeta _{j+1}-1) - 1\right) . \end{aligned} \end{aligned}$$\end{document}∫01logk(x)log(1-x)dx=(-1)kk!∑j=1k(ζj+1-1)-1. Lemma 5.2 For all integers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 1$$\end{document}k≥1:19\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \int _{0}^{1}\frac{x\log ^k(x)}{1-x}\,dx = {(-1)}^k k! (\zeta _{k+1}-1) \end{aligned}$$\end{document}∫01xlogk(x)1-xdx=(-1)kk!(ζk+1-1) Lemma 5.3 Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c\in \mathbb {R}$$\end{document}c∈R. Then, uniformly for all integers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n>c$$\end{document}n>c and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\ge 1$$\end{document}m≥1:20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \frac{1}{(n-c)h_{n-1}} = \sum _{k=1}^{m}\frac{{(-\gamma )}^{k-1}}{n\log ^k(n)} + \textrm{O}\left( \frac{1}{n\log ^{m+1}(n)}\right) , \end{aligned}$$\end{document}1(n-c)hn-1=∑k=1m(-γ)k-1nlogk(n)+O1nlogm+1(n), Returning to the proof of Theorem 2.1, recall that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{n,i}$$\end{document}Ln,i denotes the edge-depth of the leaf with label i, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le i \le n$$\end{document}1≤i≤n. To complete the proof of the theorem, we require two additional results which we state and prove next. Lemma 5.4 derives a recursion for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( L_i\cdot L_j\right) $$\end{document}ELi·Lj, and Lemma 5.5 finds an approximate solution to the recursion that is accurate up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{O}\left( 1\right) $$\end{document}O1. Lemma 5.4 For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i\ne j$$\end{document}i≠j, the following recursion applies:21\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} \mathbb {E}\left( L_{n,i}\cdot L_{n,j}\right)&= \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\left( \frac{i-1}{n-i}\right) \mathbb {E}\left( L_{n,i}\cdot L_{n,j}\right) + \frac{1}{4\zeta _2^2}\log ^3(n) \\&\qquad + \Big (D_2 + \frac{1}{\zeta _2^2}\Big )\log ^2(n) + \Big (D_1 + \frac{2(\gamma \zeta _2+\zeta _3)}{\zeta _2^2}\Big )\log (n) \\&\qquad + D_0 + 2b_0 - 1 + \textrm{O}\left( \log ^{-1}(n)\right) . \end{aligned} \end{aligned}$$\end{document}ELn,i·Ln,j=1(n-1)hn-1∑i=1n-1i-1n-iELn,i·Ln,j+14ζ22log3(n)+(D2+1ζ22)log2(n)+(D1+2(γζ2+ζ3)ζ22)log(n)+D0+2b0-1+Olog-1(n).where\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} D_2&= \frac{3\gamma -4}{4\zeta _2^2} + \frac{\zeta _3}{\zeta _2^3}; \\ D_1&= \frac{-9}{10\zeta _2} + \frac{3\gamma ^2 - 8\gamma + 12}{4\zeta _2^2} + \frac{\zeta _3(2\gamma - 3)}{\zeta _2^3} + \frac{2\zeta _3^2}{\zeta _2^4}; \\ D_0&= \frac{18-9\gamma }{10\zeta _2} + \frac{4\zeta _3 + 5(\gamma ^3 - 4\gamma ^2 + 12\gamma - 24)}{20\zeta _2^2} \\&\qquad + \frac{\zeta _3(\gamma ^2 - 3\gamma + 6)}{\zeta _2^3} + \frac{2\zeta _3^2(\gamma - 2)}{\zeta _2^4} + \frac{2\zeta _3^3}{\zeta _2^5}. \end{aligned}$$\end{document}D2=3γ-44ζ22+ζ3ζ23;D1=-910ζ2+3γ2-8γ+124ζ22+ζ3(2γ-3)ζ23+2ζ32ζ24;D0=18-9γ10ζ2+4ζ3+5(γ3-4γ2+12γ-24)20ζ22+ζ3(γ2-3γ+6)ζ23+2ζ32(γ-2)ζ24+2ζ33ζ25. Proof Without loss of generality, assume that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i=1$$\end{document}i=1 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j=2$$\end{document}j=2, and define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Z_n:= L_{n,1}\cdot L_{n,2}$$\end{document}Zn:=Ln,1·Ln,2 for brevity. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_n$$\end{document}In be the (random) size of the left subtree of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_n$$\end{document}Tn after the first split, so that the right-subtree has size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n-I_n)$$\end{document}(n-In). Then, the conditional distribution of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Z_n$$\end{document}Zn given that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_n=i$$\end{document}In=i satisfies the distributional recursion\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ Z_n\,|\,[I_n=i] \,\overset{d}{=}\, {\left\{ \begin{array}{ll} (1 + L_{i,1})(1 + L_{i,2}) & {{\,\mathrm{w.p.\;\;}\,}}\frac{{(i)}_2}{{(n)}_2}; \\ (1 + L_{n-i,1})(1 + L_{n-i,2}) & {{\,\mathrm{w.p.\;\;}\,}}\frac{{(n-i)}_2}{{(n)}_2}; \\ (1 + L_{i,1})(1 + L_{n-i,2}) & {{\,\mathrm{w.p.\;\;}\,}}\frac{i(n-i)}{{(n)}_2}; \\ (1 + L_{i,2})(1 + L_{n-i,1}) & {{\,\mathrm{w.p.\;\;}\,}}\frac{i(n-i)}{{(n)}_2}. \\ \end{array}\right. } $$\end{document}Zn|[In=i]=d(1+Li,1)(1+Li,2)w.p.(i)2(n)2;(1+Ln-i,1)(1+Ln-i,2)w.p.(n-i)2(n)2;(1+Li,1)(1+Ln-i,2)w.p.i(n-i)(n)2;(1+Li,2)(1+Ln-i,1)w.p.i(n-i)(n)2.The first two cases correspond to the events in which both leaves fall on the left or right subtree, respectively; the final two cases correspond to these leaves falling into different subtrees, in which case their edge-depths are conditionally independent. So, the conditional expectation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Z_n$$\end{document}Zn given the split size is\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\mathbb {E}\left( Z_n|I_n=i\right) \\&= \big (1 + 2\,\mathbb {E}\left( L_i\right) + \mathbb {E}\left( Z_i\right) \big )\frac{{(i)}_2}{{(n)}_2} + \big (1 + 2\,\mathbb {E}\left( L_{n-i}\right) + \mathbb {E}\left( Z_{n-i}\right) \big ) \frac{{(n-i)}_2}{{(n)}_2} \\&\qquad + 2\big (1 + \mathbb {E}\left( L_i\right) + \mathbb {E}\left( L_{n-i}\right) + \mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) \big )\frac{i(n-i)}{{(n)}_2} \\&= 1 + \frac{2i}{n}\mathbb {E}\left( L_i\right) + \frac{2(n-i)}{n}\mathbb {E}\left( L_{n-i}\right) \\&\qquad + \frac{1}{{(n)}_2}\Big [{(i)}_2\,\mathbb {E}\left( Z_i\right) + {(n-i)}_2\,\mathbb {E}\left( Z_{n-i}\right) + 2i(n-i)\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) \Big ]. \end{aligned}$$\end{document}EZn|In=i=(1+2ELi+EZi)(i)2(n)2+(1+2ELn-i+EZn-i)(n-i)2(n)2+2(1+ELi+ELn-i+ELiELn-i)i(n-i)(n)2=1+2inELi+2(n-i)nELn-i+1(n)2[(i)2EZi+(n-i)2EZn-i+2i(n-i)ELiELn-i].The Law of Total Expectation implies that the expectation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Z_n$$\end{document}Zn, after some simplification, satisfies\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( Z_n\right)&= 1 + \frac{2}{h_{n-1}}\sum _{i=1}^{n-1}\frac{\mathbb {E}\left( L_i\right) }{n-i} + \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\left( \frac{i-1}{n-i}\right) \mathbb {E}\left( Z_i\right) \\&\qquad \qquad + \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) . \end{aligned}$$\end{document}EZn=1+2hn-1∑i=1n-1ELin-i+1(n-1)hn-1∑i=1n-1i-1n-iEZi+1(n-1)hn-1∑i=1n-1ELiELn-i.Due to (12), the first two terms on the right hand-side above simplify to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\mathbb {E}\left( L_n\right) - 1$$\end{document}2ELn-1. Thus, we may rewrite the last expression for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( Z_n\right) $$\end{document}EZn as22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} \mathbb {E}\left( Z_n\right)&= 2\mathbb {E}\left( L_n\right) - 1 + \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\left( \frac{i-1}{n-i}\right) \mathbb {E}\left( Z_i\right) \\&\qquad \qquad + \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) . \end{aligned} \end{aligned}$$\end{document}EZn=2ELn-1+1(n-1)hn-1∑i=1n-1i-1n-iEZi+1(n-1)hn-1∑i=1n-1ELiELn-i.Our task is now to derive asymptotic estimates for the first and last terms in the above recursion. In the remainder of the proof, we demonstrate how to handle the last term only, as the other can be handled similarly. To begin, substituting (15) into \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) $$\end{document}ELiELn-i, we obtain that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\sum _{i=1}^{n-1}\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) = \sum _{i=1}^{n-1}\left[ \frac{1}{2\zeta _2}\log ^2(i) + \frac{\gamma \,\zeta _2+\zeta _3}{\zeta _2^2}\log (i) + b_0 + \textrm{O}\left( \frac{\log (i)}{i}\right) \right] \\&\qquad \times \quad \left[ \frac{1}{2\zeta _2}\log ^2(n-i) + \frac{\gamma \,\zeta _2+\zeta _3}{\zeta _2^2}\log (n-i) + b_0 + \textrm{O}\left( \frac{\log (n-i)}{n-i}\right) \right] \end{aligned}$$\end{document}∑i=1n-1ELiELn-i=∑i=1n-112ζ2log2(i)+γζ2+ζ3ζ22log(i)+b0+Olog(i)i×12ζ2log2(n-i)+γζ2+ζ3ζ22log(n-i)+b0+Olog(n-i)n-iwhich becomes23\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned}&\sum _{i=1}^{n-1}\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right) =\frac{1}{4\zeta _2^2}\sum _{i=1}^{n-1}\log ^2(i)\log ^2(n-i) \\&+ \frac{\gamma \,\zeta _2+\zeta _3}{2\zeta _2^3}\sum _{i=1}^{n-1}\big [\log ^2(i)\log (n-i) + \log (i)\log ^2(n-i)\big ] \\&\qquad + {\left( \frac{\gamma \,\zeta _2+\zeta _3}{\zeta _2^2}\right) }^2\sum _{i=1}^{n-1}\log (i) \log (n-i) + \frac{b_0}{2\zeta _2}\sum _{i=1}^{n-1}[\log ^2(i) + \log ^2(n-i)] \\&\qquad \qquad + \frac{b_0(\gamma \,\zeta _2 + \zeta _3)}{\zeta _2^2}\sum _{i=1}^{n-1}\big [\log (i) + \log (n-i)\big ] + \textrm{O}\left( n\right) . \end{aligned} \end{aligned}$$\end{document}∑i=1n-1ELiELn-i=14ζ22∑i=1n-1log2(i)log2(n-i)+γζ2+ζ32ζ23∑i=1n-1[log2(i)log(n-i)+log(i)log2(n-i)]+γζ2+ζ3ζ222∑i=1n-1log(i)log(n-i)+b02ζ2∑i=1n-1[log2(i)+log2(n-i)]+b0(γζ2+ζ3)ζ22∑i=1n-1[log(i)+log(n-i)]+On.Next, one can obtain asymptotic formulas for each of the summations above by repeatedly applying the following argument, which we only demonstrate for the left-most sum in (23) using Riemann sum arguments. First note that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\sum _{i=1}^{n-1}\log ^2(i)\log ^2(n-i) \\&\qquad =\sum _{i=1}^{n-1}{\left( \log \left( \frac{i}{n}\right) + \log (n)\right) }^2{\left( \log \left( 1-\frac{i}{n}\right) + \log (n)\right) }^2 \\&\qquad = 2\log (n)\sum _{i=1}^{n-1}\log ^2\left( \frac{i}{n}\right) \log \left( 1-\frac{i}{n}\right) + \log ^2(n)\sum _{i=1}^{n-1}\log ^2\left( \frac{i}{n}\right) \\&\qquad \quad + 2\log (n) \sum _{i=1}^{n-1}\log \left( \frac{i}{n}\right) \log ^2\left( 1-\frac{i}{n}\right) + 4\log ^2(n)\sum _{i=1}^{n-1}\log \left( \frac{i}{n}\right) \log \left( 1-\frac{i}{n}\right) \\&\qquad \quad + 2\log ^3(n)\sum _{i=1}^{n-1}\log \left( \frac{i}{n}\right) + \log ^2(n)\sum _{i=1}^{n-1}\log ^2\left( 1-\frac{i}{n}\right) \\&\qquad \quad + 2\log ^3(n)\sum _{i=1}^{n}\log \left( 1-\frac{i}{n}\right) + n\log ^4(n) + \textrm{O}\left( n\right) . \end{aligned}$$\end{document}∑i=1n-1log2(i)log2(n-i)=∑i=1n-1login+log(n)2log1-in+log(n)2=2log(n)∑i=1n-1log2inlog1-in+log2(n)∑i=1n-1log2in+2log(n)∑i=1n-1loginlog21-in+4log2(n)∑i=1n-1loginlog1-in+2log3(n)∑i=1n-1login+log2(n)∑i=1n-1log21-in+2log3(n)∑i=1nlog1-in+nlog4(n)+On.From the identity in (16) and Lemma 5.1, it follows that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\sum _{i=1}^{n-1}\log ^2(i)\log ^2(n-i) \\&\qquad = 2n\log (n)\int _{0}^{1}\log ^2x\log (1-x)\,dx + n\log ^2(n)\int _{0}^{1}\log ^2 x\,dx \\&\qquad \quad + 2n\log (n)\int _{0}^{1}\log x\log ^2(1-x)\,dx + 4n\log ^2(n)\int _{0}^{1}\log x \log (1-x)\,dx \\&\qquad \quad + 2n\log ^3(n)\int _{0}^{1}\log x \,dx + n\log ^2(n) \int _{0}^{1}\log ^2(1-x)\,dx \\&\qquad \quad + 2n\log ^3(n) \int _{0}^{1}\log (1-x) \,dx + n\log ^4(n) + \textrm{O}\left( n\right) \\&\qquad = n\log ^4(n) - 4n\log ^3(n) + (12 - 4\zeta _2)n\log ^2(n) \\&\qquad \quad + 8(\zeta _2 + \zeta _3 - 3)n\log (n) + \textrm{O}\left( n\right) . \end{aligned}$$\end{document}∑i=1n-1log2(i)log2(n-i)=2nlog(n)∫01log2xlog(1-x)dx+nlog2(n)∫01log2xdx+2nlog(n)∫01logxlog2(1-x)dx+4nlog2(n)∫01logxlog(1-x)dx+2nlog3(n)∫01logxdx+nlog2(n)∫01log2(1-x)dx+2nlog3(n)∫01log(1-x)dx+nlog4(n)+On=nlog4(n)-4nlog3(n)+(12-4ζ2)nlog2(n)+8(ζ2+ζ3-3)nlog(n)+On.Using similar arguments for the other terms and Lemma 5.3, we obtain that24\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\mathbb {E}\left( L_i\right) \mathbb {E}\left( L_{n-i}\right)&= \frac{1}{4\zeta _2^2}\log ^3(n) + D_2\log ^2(n) \\&\qquad + D_1\log (n) + D_0 + \textrm{O}\left( \log ^{-1}(n)\right) \end{aligned} \end{aligned}$$\end{document}1(n-1)hn-1∑i=1n-1ELiELn-i=14ζ22log3(n)+D2log2(n)+D1log(n)+D0+Olog-1(n)for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_0$$\end{document}D0, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_1$$\end{document}D1, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_2$$\end{document}D2 as defined in the statement of the lemma. Finally, substituting (24) and (15) into (22), we obtain the implicit recursion for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( Z_n\right) $$\end{document}EZn in the lemma. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\square $$\end{document}□ Lemma 5.5 For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i\ne j$$\end{document}i≠j, the following recursion applies:25\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} \mathbb {E}\left( L_{n,i}\cdot L_{n,j}\right)&= \frac{1}{4\zeta _2^2}\log ^4(n) + \frac{\gamma \,\zeta _2 + \zeta _3}{\zeta _2^3}\log ^3(n) \\&\qquad + C_2\log ^2(n) + C_1\log (n) + \textrm{O}\left( 1\right) , \end{aligned} \end{aligned}$$\end{document}ELn,i·Ln,j=14ζ22log4(n)+γζ2+ζ3ζ23log3(n)+C2log2(n)+C1log(n)+O1,where\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_2&= -\frac{9}{10\zeta _2} + \frac{3\gamma ^2 + 4\zeta _3}{2\zeta _2^2} + \frac{3\gamma \zeta _3}{\zeta _2^3} + \frac{2\zeta _3^2}{\zeta _2^4}; \\ C_1&= 1 - \frac{9\gamma + 20\zeta _3}{5\zeta _2} + \frac{5\gamma ^3 + 20\zeta _3\gamma + 21\zeta _3 - 30\zeta _4}{5\zeta _2^2} \\&\qquad + \frac{3\zeta _3\gamma ^2 + 4\zeta _3^2}{\zeta _2^3} + \frac{4\zeta _3^2\gamma }{\zeta _2^4} + \frac{2\zeta _3^3}{\zeta _2^5}. \end{aligned}$$\end{document}C2=-910ζ2+3γ2+4ζ32ζ22+3γζ3ζ23+2ζ32ζ24;C1=1-9γ+20ζ35ζ2+5γ3+20ζ3γ+21ζ3-30ζ45ζ22+3ζ3γ2+4ζ32ζ23+4ζ32γζ24+2ζ33ζ25. Proof We start by noting the following useful identities:26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\frac{(i-1)\log ^4(i)}{n-i}&= \log ^4(n) - \log ^3(n) + \big [4(1-\zeta _2) + \gamma \big ]\log ^2(n) \nonumber \\&\qquad + \big [12(\zeta _3-1) + 4\gamma (\zeta _2 - 1) - \gamma ^2\big ]\log (n) \end{aligned}$$\end{document}1(n-1)hn-1∑i=1n-1(i-1)log4(i)n-i=log4(n)-log3(n)+[4(1-ζ2)+γ]log2(n)+[12(ζ3-1)+4γ(ζ2-1)-γ2]log(n)27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\qquad + 24(1-\zeta _4) + 12\gamma (1 - \zeta _3) + 4\gamma ^2(1 - \zeta _2) + \gamma ^3 \nonumber \\&\qquad + \textrm{O}\left( \log ^{-1}(n)\right) ; \nonumber \\ \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\frac{(i-1)\log ^3(i)}{n-i}&= \log ^3(n) - \log ^2(n) + \Big [3(1-\zeta _2) + \gamma \Big ]\log (n) \end{aligned}$$\end{document}+24(1-ζ4)+12γ(1-ζ3)+4γ2(1-ζ2)+γ3+Olog-1(n);1(n-1)hn-1∑i=1n-1(i-1)log3(i)n-i=log3(n)-log2(n)+[3(1-ζ2)+γ]log(n)28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&\qquad + 6(\zeta _3-1) + 3\gamma (\zeta _2 - 1) - \gamma ^2 + \textrm{O}\left( \log ^{-1}(n)\right) ; \nonumber \\ \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\frac{(i-1)\log ^2(i)}{n-i}&= \log ^2(n) - \log (n) + \gamma + 2(1-\zeta _2) + \textrm{O}\left( \log ^{-1}(n)\right) ;\end{aligned}$$\end{document}+6(ζ3-1)+3γ(ζ2-1)-γ2+Olog-1(n);1(n-1)hn-1∑i=1n-1(i-1)log2(i)n-i=log2(n)-log(n)+γ+2(1-ζ2)+Olog-1(n);29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\frac{(i-1)\log (i)}{n - i}&= \log (n) - 1 + \textrm{O}\left( \log ^{-1}(n)\right) . \end{aligned}$$\end{document}1(n-1)hn-1∑i=1n-1(i-1)log(i)n-i=log(n)-1+Olog-1(n).The first two identities follow from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{i=1}^{n-1} \frac{i-1}{n-i} = (n-1)(h_{n-1}-1)$$\end{document}∑i=1n-1i-1n-i=(n-1)(hn-1-1) and the application of Lemmas 5.2–5.3. The last two identities can be found in the proof of (Aldous and Pittel, 2025, Theorem 2.6). The key idea of the proof is to seek an approximate solution to the recursion in (21) of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E(n) = A\log ^4(n) + B\log ^3(n) + C\log ^2(n) + D\log (n)$$\end{document}E(n)=Alog4(n)+Blog3(n)+Clog2(n)+Dlog(n) for suitable constants A, B, C, and D, and then show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( L_{n,i} \cdot L_{n,j}\right) = E(n) + \textrm{O}\left( 1\right) $$\end{document}ELn,i·Ln,j=E(n)+O1, as in Aldous and Pittel (2025). By substituting E(n) for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}\left( Z_i\right) $$\end{document}EZi in (21), we find that a sum remains to be handled. In particular, the first term becomes\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\Big (\frac{i-1}{n-i}\Big )\Big (A\log ^4(i) + B\log ^3(i) + C\log ^2(i) + D\log (i)\Big ). $$\end{document}1(n-1)hn-1∑i=1n-1(i-1n-i)(Alog4(i)+Blog3(i)+Clog2(i)+Dlog(i)).Considering each power of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log (i)$$\end{document}log(i) in turn, we find that (26)-(29) provide an asymptotic estimate for this sum, which constrains the constants A, B, C, and D to satisfy:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}&A\log ^4(n) + B\log ^3(n) + C\log ^2(n) + D\log (n) \\&\qquad = A\log ^4(n) + \Big \{B - A + \frac{1}{4\zeta _2}\Big \}\log ^3(n) \\&\qquad \qquad + \Big \{C - B + \Big [4(1-\zeta _2)+\gamma \Big ]A + D_2 + \frac{1}{\zeta _2}\Big \}\log ^2(n) \\&\qquad \qquad + \Big \{D - C + \Big [3(1-\zeta _2)+\gamma \Big ]B + \Big [12(\zeta _3-1) + 4\gamma (\zeta _2) - 1 - \gamma ^2\Big ]A \\&\qquad \qquad + D_1 + \frac{2(\gamma \zeta _2 + \zeta _3)}{\zeta _2^2}\Big \}\log (n) \\&\qquad \qquad + \Big \{-D + \Big [2(1-\zeta _2) + \gamma \Big ]C + \Big [6(\zeta _3-1) + 3\gamma (\zeta _2-1) - \gamma ^2\Big ]B \\&\qquad \qquad + \Big [24(1-\zeta _4) + 12\gamma (1-\zeta _3)+4\gamma ^2(1-\zeta _2)+\gamma ^3\Big ]A + D_0 + 2b_0 - 1\Big \}. \end{aligned}$$\end{document}Alog4(n)+Blog3(n)+Clog2(n)+Dlog(n)=Alog4(n)+{B-A+14ζ2}log3(n)+{C-B+[4(1-ζ2)+γ]A+D2+1ζ2}log2(n)+{D-C+[3(1-ζ2)+γ]B+[12(ζ3-1)+4γ(ζ2)-1-γ2]A+D1+2(γζ2+ζ3)ζ22}log(n)+{-D+[2(1-ζ2)+γ]C+[6(ζ3-1)+3γ(ζ2-1)-γ2]B+[24(1-ζ4)+12γ(1-ζ3)+4γ2(1-ζ2)+γ3]A+D0+2b0-1}.Solving the linear system implied above, we find that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} A&= \frac{1}{4\zeta _2^2}; \qquad B = \frac{\gamma \,\zeta _2 + \zeta _3}{\zeta _2^3}; \qquad C = -\frac{9}{10\zeta _2} + \frac{3\gamma ^2 + 4\zeta _3}{2\zeta _2^2} + \frac{3\gamma \zeta _3}{\zeta _2^3} + \frac{2\zeta _3^2}{\zeta _2^4}; \\ D&= 1 - \frac{9\gamma + 20\zeta _3}{5\zeta _2} + \frac{5\gamma ^3 + 20\zeta _3\gamma + 21\zeta _3 - 30\zeta _4}{5\zeta _2^2} + \frac{3\zeta _3\gamma ^2 + 4\zeta _3^2}{\zeta _2^3} + \frac{4\zeta _3^2\gamma }{\zeta _2^4} + \frac{2\zeta _3^3}{\zeta _2^5}. \end{aligned}$$\end{document}A=14ζ22;B=γζ2+ζ3ζ23;C=-910ζ2+3γ2+4ζ32ζ22+3γζ3ζ23+2ζ32ζ24;D=1-9γ+20ζ35ζ2+5γ3+20ζ3γ+21ζ3-30ζ45ζ22+3ζ3γ2+4ζ32ζ23+4ζ32γζ24+2ζ33ζ25.The E(n) defined by the above coefficients satisfies the recursion in (21) up to a remainder of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{O}\left( \log ^{-1}(n)\right) $$\end{document}Olog-1(n). However, if we define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (n):= |\mathbb {E}\left( Z_n\right) - E(n)|$$\end{document}Δ(n):=|EZn-E(n)|, then\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \Delta (n) \le \frac{1}{(n-1)h_{n-1}}\sum _{i=1}^{n-1}\frac{(i-1)\Delta (i)}{n-i} + \textrm{O}\left( \log ^{-1}(n)\right) . $$\end{document}Δ(n)≤1(n-1)hn-1∑i=1n-1(i-1)Δ(i)n-i+Olog-1(n).The above inequality is equivalent to the one in (Aldous and Pittel, 2025, (32)) found in the proof of (Aldous and Pittel, 2025, Theorem 2.6). Repeating the arguments there, it finally follows that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (n) = \textrm{O}\left( 1\right) $$\end{document}Δ(n)=O1. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\square $$\end{document}□ We are now ready to prove the asymptotic formulas (8)-(10) in Theorem 2.1. The proof of (8) is a straightforward consequence of (13) from (Aldous and Pittel, 2025, Theorem 1.2) because, due to the exchangeability of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(L_{n,i})$$\end{document}(Ln,i):\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathbb {E}\left( {{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) \right) = \mathbb {E}\left( \sum _{i=1}^{n} L_{n,i}\right) = n\,\mathbb {E}\left( L_n\right) . $$\end{document}EEPLTn=E∑i=1nLn,i=nELn.On the other hand, again due to exchangeability,30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( {{{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) }^2\right)&=\mathbb {E}\left( {\left( \sum _{i=1}^{n} L_{n,i}\right) }^2\right) \nonumber \\&=\sum _{i=1}^{n}\mathbb {E}\left( {L_{n,i}}^2\right) +\sum _{i\ne j}\mathbb {E}\left( L_{n,i}\cdot L_{n,j}\right) \nonumber \\&=n\,\mathbb {E}\left( {L_n}^2\right) +n(n-1)\,\mathbb {E}\left( L_{n,1}\cdot L_{n,2}\right) . \end{aligned}$$\end{document}EEPLTn2=E∑i=1nLn,i2=∑i=1nELn,i2+∑i≠jELn,i·Ln,j=nELn2+n(n-1)ELn,1·Ln,2.We may estimate the first term in the last identity above using (13)–(14) as follows:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbb {E}\left( {L_n}^2\right)&={{\,\textrm{Var}\,}}\left( L_n\right) +{\mathbb {E}\left( L_n\right) }^2\\&=\frac{2\zeta _3}{3\zeta _2^3}\log ^{3}(n) + \textrm{O}\left( \log ^2(n)\right) + {\left[ \frac{1}{2\zeta _2}\log ^2(n) + \frac{\gamma \,\zeta _2+\zeta _3}{\zeta _2^2}\log (n) + \textrm{O}\left( 1\right) \right] }^2\\&=\frac{1}{4\zeta _2^2}\log ^{4}(n) + \frac{3\gamma \,\zeta _2+5\zeta _3}{3\zeta _2^3}\log ^{3}(n) + \textrm{O}\left( \log ^{2}(n)\right) . \end{aligned}$$\end{document}ELn2=VarLn+ELn2=2ζ33ζ23log3(n)+Olog2(n)+12ζ2log2(n)+γζ2+ζ3ζ22log(n)+O12=14ζ22log4(n)+3γζ2+5ζ33ζ23log3(n)+Olog2(n).By substituting the latter expression and the asymptotic formula in (25) into (30), equation (9) follows. Finally, the formula in (10) follows from\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {{\,\textrm{Var}\,}}\left( {{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) \right) = \mathbb {E}\left( {{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) ^2\right) - \mathbb {E}\left( {{\,\textrm{EPL}\,}}\left( \textrm{T}_n\right) \right) ^2, $$\end{document}VarEPLTn=EEPLTn2-EEPLTn2,after substituting in (8)-(9), which completes the proof of Theorem 2.1.