# History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities

arXiv: https://arxiv.org/abs/2606.24465 · HTML: https://mlsanity.com/paper/2606.24465/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 23 Jun 2026.

## Builds on (most cited first, 8 of 8)

- [Finding Adam in random growing trees](https://mlsanity.com/paper/1411.3317/) (2014)
- [Archaeology of random recursive dags and Cooper-Frieze random networks](https://mlsanity.com/paper/2207.14601/) (2022)
- [Persistence of centrality in random growing trees](https://mlsanity.com/paper/1511.01975/) (2015)
- [Estimating the history of a random recursive tree](https://mlsanity.com/paper/2403.09755/) (2024)
- [Leaf Stripping on Uniform Attachment Trees](https://mlsanity.com/paper/2410.06481/) (2024)
- [Finding the root in random nearest neighbor trees](https://mlsanity.com/paper/2411.14336/) (2024)
- [Optimal root recovery for uniform attachment trees and d-regular growing trees](https://mlsanity.com/paper/2411.18614/) (2024)
- [Correlated uniform attachment trees](https://mlsanity.com/paper/2606.02472/) (2026)

## Abstract (arXiv)

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)/S2, at the cost of a heavier lower tail of order 1/S2. 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.