History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities
Johannes Bäumler, Simon Briend, Joost Jorritsma
Abstract
We study the problem of estimating the arrival times of vertices in a uniform random recursive tree from its unlabeled structure. We adopt a pointwise perspective and analyze the distribution of the relative estimation error, and derive tail bounds that are uniform in both the vertex and the tree size. For the ranking induced by Jordan centrality, the probability that the estimate exceeds the true arrival time by a factor $S$ decays on the order of $1/S$, while the probability of underestimating the arrival time by a factor $1/S$ decays exponentially in $S$. We introduce a refined centrality measure whose overestimation tail decays on the order of $(\log S)/S^{2}$, at the cost of a heavier lower tail of order $1/S^{2}$. These results reveal a tradeoff between upper- and lower-tail performance in arrival-time estimation that is invisible to the previously studied risk functional. Nevertheless, the refined centrality measure attains the optimal order of the risk for all its parameter values.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.