The height of discrete-time critical beta-splitting trees

Abstract

We determine the asymptotic height of the discrete-time critical beta-splitting tree. Let $L_n^*$ denotes the height of the tree with $n$ leaves, defined as the maximum graph distance from the root to a leaf. Then, \[ \frac{L_n^*}{(\log n)^2} \longrightarrow C_{\mathrm{ht}}:=\min_{\theta>1} \frac{\theta}{2\{\psi(\theta)+\gamma\}} \approx 0.976 \] almost surely and in $L^{p}$ for every fixed $p>1$ as $n \to \infty$. Here $\psi$ is the digamma function and $\gamma$ is Euler's constant. This answers \cite[Open Problem~4]{AldousJansonII} of Aldous and Janson.