betaFeedback

WorksMathematics

Exact Asymptotics for the Harmonic Descent Chain and Extended Convergence Bounds for Recursive Statistics

Abstract

We give an exact asymptotic expansion of the occupation probabilities a(n,k)a(n,k) of the harmonic descent chain, introduced by D. Aldous, as n→∞n\rightarrow\infty with k∈o(n)k\in\mathrm{o}(\sqrt{n}). In addition, we extend the recent results of Brandenberger et al. by giving a bound on the rate of convergence of sequences defined recursively by xn=1Hn−1∑i=1n−1xin−ix_n = \frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{x_i}{n-i} for more general initial conditions. This result enables the application of an existing central limit theorem, also by Brandenberger et al., to statistics of the critical beta-splitting tree which satisfy our more general initial conditions.

Introduction

The critical beta-splitting tree is a particular case of a one-parameter family of random binary trees called beta-splitting models. The model was introduced in [2] as a more realistic model of real-world phylogenetic trees, and it has seen renewed interest in recent years [4, 5, 6, 3, 7]. Under a beta-splitting model, a random tree is generated by recursively partitioning {1,…,n}\{1,\ldots,n\} according to a splitting probability distribution q(n,i)q(n,i), 1≤i<n1 \le i < n, which gives the probability that a clade of size nn is split into clades of size ii and n−in-i. For the critical beta-splitting tree, this probability is

q(n,i):=n2Hn−11i(n−i),(1)q(n,i) := \frac{n}{2H_{n-1}}\frac{1}{i(n-i)}, \tag*{(1)}

where Hn−1H_{n-1} denotes the (n−1)(n-1)th harmonic number.

The harmonic descent chain, described in [4, 5, 6, 7], is a discrete-time Markov chain on the states {1,2,3,…}\{1,2,3,\ldots\} with transition probabilities

p(j,i)=1(j−i)Hj−1,1≤i<j, j≥2,p(j,i) = \frac{1}{(j-i)H_{j-1}}, \qquad1 \le i < j,\ j \ge2,

and p(1,1)=1p(1,1)=1. Started at state nn, this Markov chain describes the sequence of clade sizes in the critical beta-splitting tree with nn leaves along a path from the root to a uniformly random leaf. Of interest are the “occupation probabilities”, a(n,k)a(n,k), defined as the probability that the chain started at state nn is ever in state kk. These characterize the asymptotic fringe distribution of the tree (see [1] in general), that is, the n→∞n \to\infty weak limit of the tree relative to a uniformly random leaf. In particular, it has been shown [3, 6, 7, 13] that the limits lim⁡n→∞a(n,k)=:a(k)\lim_{n\to\infty} a(n,k) =: a(k) exist,

a(k)=Hk−1ζ(2)(k−1),k≥2,(2)a(k)=\frac{H_{k-1}}{\zeta(2)(k-1)},\qquad k\ge2, \tag*{(2)}

and a(1)=1a(1)=1. In turn, the “reverse harmonic descent chain” is a Markov chain with “upward” transition probabilities

q↑(i,j)=a(j)a(i)p(j,i).q^{\uparrow}(i,j)=\frac{a(j)}{a(i)}p(j,i).

Letting, at each upward step i→ji \to j, the sibling clade be distributed according to the critical beta-splitting distribution with j−ij-i leaves, the resulting infinite tree described by the upward chain is the extended fringe [1] relative to a typical leaf.

Many quantities of interest obey the recursion

xn=1Hn−1∑i=1n−1xin−i,n>M,(3)x_n=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{x_i}{n-i},\qquad n>M, \tag*{(3)}

with some set of initial conditions. For example, if Nn(k)N_n(k) is the number of kk-leaf subtrees of a critical beta-splitting tree with nn leaves and InI_n is the size of the split at the root, then the conditional distribution of Nn(k)N_n(k) given In=iI_n=i is the same as Ni(k)+Nn−i(k)+1(n=k)N_i(k)+N_{n-i}(k)+1(n=k). So, the law of total probability yields

E(Nn(k))n=1Hn−1∑i=1n−1E(Ni(k))/in−i\frac{\mathbb{E}(N_n(k))}{n}=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{\mathbb{E}(N_i(k))/i}{n-i}

for n>kn>k, that is, the quantity E(Nn(k))/n=a(n,k)/k\mathbb{E}(N_n(k))/n=a(n,k)/k obeys the recursion described.

Recently, Brandenberger et al. [8] analyzed such recursions and found bounds on the rate of convergence to the limit x:=lim⁡n→∞xnx:=\lim_{n\to\infty}x_n when xnx_n has the initial conditions x1=⋯=xk−1=0x_1=\cdots=x_{k-1}=0 and xk>0x_k>0. Because a(n,k)=kE(Nn(k))/na(n,k)=k\mathbb{E}(N_n(k))/n, this analysis yielded, in turn, a description of the asymptotic behavior of a(n,k)a(n,k); in particular, they showed [8 eqn. (1.6)]

a(n,k)−a(k)=n−γ∗+o(1)(4)a(n,k)-a(k)=n^{-\gamma_*+o(1)} \tag*{(4)}

for some 1.5<γ∗<21.5<\gamma_*<2. Moreover, they showed a central limit theorem based on the contraction method (e.g., see [16, 17] for this method in general) for statistics of the critical beta-splitting tree:

Proposition 1.1 (Proposition 1.3 of [8]). Let (Xn′)n≥1(X'_n)_{n\ge1} and (Xn′′)n≥1(X''_n)_{n\ge1} be independent copies of the random sequence (Xn)n≥1(X_n)_{n\ge1}, independent also of (In,bn)n≥2(I_n,b_n)_{n\ge2}, and suppose that

Xn=dXIn′+Xn−In′′+bn,n≥2.(5)X_n \mathrel{\overset{d}{=}} X'_{I_n}+X''_{n-I_n}+b_n,\qquad n\ge2. \tag*{(5)}

Suppose further that there exist constants μ,σ,ϵ,C>0\mu,\sigma,\epsilon,C>0 such that ∣E(Xn)−μn∣≤Cn1/2−ϵ|\mathbb{E}(X_n)-\mu n|\le Cn^{1/2-\epsilon} and ∣Var⁡(Xn)−σ2n∣≤Cn1−ϵ|\operatorname{Var}(X_n)-\sigma^2n|\le Cn^{1-\epsilon} and E(∣bn∣3)≤n3/2−ϵ\mathbb{E}(|b_n|^3)\le n^{3/2-\epsilon}. Then

Xn−E(Xn)Var⁡(Xn)⟶dN(0,1).(6)\frac{X_n-\mathbb{E}(X_n)}{\sqrt{\operatorname{Var}(X_n)}}\mathrel{\overset{d}{\longrightarrow}}\mathcal{N}(0,1). \tag*{(6)}

See [14] as well for another example of the contraction method applied specifically to the critical beta-splitting tree. Of interest to us in particular, Brandenberger et al. [8] demonstrated that their analysis of xnx_n can be used to determine that (Xn)n≥1(X_n)_{n\geq1} satisfies the conditions of the CLT when (E(Xn)/n)n≥1(\mathbb{E}(X_n)/n)_{n\geq1} obeys this recursion and initial conditions.

Our first main result is to present an exact asymptotic expansion of a(n,k)a(n,k) in terms of a(k)a(k), as n→∞n \to\infty with k∈o(n)k \in o(\sqrt{n}). Our result refines the asymptotic estimate shown in [8] and confirms the exact value of γ∗\gamma_*, given numerically in [8], as γ∗=∣s1∣+1=1.567…\gamma_* = |s_1| + 1 = 1.567\ldots where s1s_1 denotes the largest negative root of ψ(s)−ψ(1)\psi(s)-\psi(1). Our second result gives convergence bounds for a sequence xnx_n obeying the recursion (1.3) with a more general set of initial conditions than in Theorem 1.1 of [8], in particular, xk≥0x_k \geq0 for all 1≤k≤M1 \leq k \leq M and xk>0x_k > 0 for at least one kk. For appropriate random variables, this result enables Proposition 1.1 to be applied when (E(Xn)/n)n≥1(\mathbb{E}(X_n)/n)_{n\geq1} obeys our more general initial conditions, and as a demonstration we give a CLT for a random variable of interest which falls outside the scope of Theorem 1.1 of [8].

Notation and Terminology

1A(x)1_A(x) denotes the indicator function over the event AA. We may often write, for example, 1(x≤N)1(x \leq N) for 1{y≤N}(x)1_{\{y\leq N\}}(x).

We use standard terminology for trees and consider ordered, unlabelled binary trees. For a tree TT, let ∣T∣|T| denote the number of vertices in TT, and let [T][T] denote the number of leaves of TT. For a vertex v∈Tv \in T, let T(v)T(v) denote the subtree of TT rooted at vv, and let p(v)p(v) denote the parent vertex of vv.

Unless otherwise stated, TnT_n is a random critical beta-splitting tree with nn leaves.

Write ψ(s)\psi(s) for the digamma function, Hn=∑i=1ni−1H_n = \sum_{i=1}^{n} i^{-1} for the nnth harmonic number, and ζ(s)\zeta(s) for the Riemann zeta function.

We denote that f(n)f(n) and g(n)g(n) are asymptotically equivalent by f(n)∼g(n)f(n) \sim g(n).

Main Results

Asymptotics for the Harmonic Descent Chain

Our first result is an exact asymptotic expansion of the occupation probabilities, a(n,k)a(n,k). It was shown in Brandenberger et al. [8], eqn. (1.6) that for xnx_n obeying the recursion (1.3) with initial conditions xn=0x_n = 0 for n<kn < k and xk>0x_k > 0, that x:=lim⁡n→∞xnx := \lim_{n\to\infty} x_n exists and

xn−x=n−γ∗+o(1)x_n - x = n^{-\gamma_*+o(1)}

for some 1.5<γ∗<21.5 < \gamma_* < 2. They reported that γ∗=1.567353…\gamma_* = 1.567353\ldots numerically. Because a(n,k)=kE(Nn(k))/na(n,k) = k\mathbb{E}(N_n(k))/n and E(Nn(k))/n\mathbb{E}(N_n(k))/n follows this behavior of xnx_n, the result gives an asymptotic estimate for a(n,k)−a(k)a(n,k)-a(k).

References

  1. [1]David Aldous, Asymptotic fringe distributions for general families of random trees, The Annals of Applied Probability 1 (1991), no. 2, 228–266.DOI
  2. [2]———, Probability distributions on cladograms, The IMA Volumes in Mathematics and its Applications, vol. 76, pp. 1–18. Springer New York, New York, NY, 1996 (en).DOI
  3. [3]David Aldous and Svante Janson, The critical beta-splitting random tree IV: Mellin analysis of leaf height, Electronic Journal of Probability 30 (2025), no. none, 1–39 (en).arxiv.org/abs/2412.12319
  4. [4]David Aldous and Boris Pittel, The critical beta-splitting random tree I: Heights and related results, The Annals of Applied Probability 35 (2025), no. 1, 158–195 (en).
  5. [5]David J. Aldous and Svante Janson, The critical beta-splitting random tree II: Overview and open problems, July 2024, arXiv:2303.02529.arxiv.org/abs/2303.02529
  6. [6]———, The critical beta-splitting random tree III: The exchangeable partition representation and the fringe tree, December 2024, arXiv:2412.09655.arxiv.org/abs/2412.09655
  7. [7]David J. Aldous, Svante Janson, and Xiaodan Li, The harmonic descent chain, May 2024, arXiv:2405.05102.arxiv.org/abs/2405.05102
  8. [8]Anna Brandenberger, Byron Chin, and Elchanan Mossel, Asymptotics for the harmonic descent chain and applications to critical beta-splitting trees, September 2026, arXiv:2505.24821.arxiv.org/abs/2505.24821
  9. [9]Louis H. Y. Chen, Larry Goldstein, and Qi-Man Shao, Normal approximation by Stein’s method, Probability and Its Applications, Springer-Verlag Berlin Heidelberg, Berlin, Heidelberg, 2011 (eng).DOI
  10. [10]A. Erdélyi and F. G. Tricomi, The asymptotic expansion of a ratio of gamma functions., Pacific Journal of Mathematics 1 (1951), no. 1, 133–142 (en).DOI
  11. [11]Philippe Flajolet and Robert Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice’s integrals, Theoretical Computer Science 144 (1995), no. 1, 101–124.DOI
  12. [12]Larry Goldstein and Gesine Reinert, Stein’s method and the zero bias transformation with application to simple random sampling, The Annals of Applied Probability 7 (1997), no. 4, 935–952 (en).
  13. [13]Alexander Iksanov, The harmonic descent chain and regenerative composition structures, Electronic Communications in Probability 30 (2025), no. none, 1–3 (en).DOI
  14. [14]Brett Kolesnik, Critical beta-splitting, via contraction, Electronic Communications in Probability 30 (2025), no. none, 1–14 (en).DOI
  15. [15]M. Ram Murty, Irrationality of zeros of the digamma function, pp. 237–243, Springer International Publishing, Cham, 2023 (en).DOI
  16. [16]Mireille Régnier, A limiting distribution for Quicksort, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 23 (1989), no. 3, 335–343 (eng).DOI
  17. [17]Uwe Rösler, A limit theorem for "Quicksort", RAIRO - Theoretical Informatics and Applications 25 (1991), no. 1, 85–100 (en).
  18. [18]Moshe Shaked and J. George Shanthikumar, Stochastic orders, Springer series in statistics, Springer, New York, 2007.
  19. [19]Edmund T. Whittaker and G. N. Watson, A course of modern analysis: an introduction to the general theory of infinite processes and of analytic functions, with an account of the principal transcendental functions, fourth edition, reprinted ed., Cambridge mathematical library, Cambridge University Press, Cambridge New York, 1927 (eng).

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

Claude Sonnet 5.5 (bare)

View statement
Looking for related papers…
Contents