The Critical Beta-splitting Random Tree: Heights and Related Results

arXiv2302.05066MaRDI QIDQ6426010FDOQ6426010

Publication date: 10 February 2023

Abstract: In the critical beta-splitting model of a random

n

-leaf binary tree, leaf-sets are recursively split into subsets, and a set of

m

leaves is split into subsets containing

i

and

m - i

leaves with probabilities proportional to

1 / i (m - i)

. We study the continuous-time model in which the holding time before that split is exponential with rate

h_{m - 1}

, the harmonic number. We (sharply) evaluate the first two moments of the time-height

D_{n}

and of the edge-height

L_{n}

of a uniform random leaf (that is, the length of the path from the root to the leaf), and prove the corresponding CLTs. We find the limiting value of the correlation between the heights of two random leaves of the same tree realization, and analyze the expected number of splits necessary for a set of

t

leaves to partially or completely break away from each other. We give tail bounds for the time-height and the edge-height of the {em tree}, that is the maximal leaf heights. Our proofs are based on asymptotic analysis of the attendant (sum-type) recurrences. The essential idea is to replace such a recursive equality by a pair of recursive inequalities for which matching asymptotic solutions can be found, allowing one to bound, both ways, the elusive explicit solution of the recursive equality. {We show that the sequence of distributions for the size of the uniformly random subtree is tight, and--under monotonicity conjecture amply supported by numerics--the sequence converges to a proper distribution. However the expected size of the subtree is asymptotic to

f r a c 3 2 p i^{2} l o g^{2} n o i n f t y

.}

Mathematics Subject Classification ID

Trees (05C05) Taxonomy, cladistics, statistics in mathematical biology (92B10) Combinatorial probability (60C05)

This page was built for publication: The Critical Beta-splitting Random Tree: Heights and Related Results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426010)