Estimating the history of random recursive tree

Link to Join Zoom Meeting

**This talk will be broadcast at 13:30 BST / 14:30 CEST / 15:30 EEST, September 30th, 2026 on Zoom only. **

Meeting-ID: 667 4776 1513 Passcode: 834059

Abstract

In this joint work with Johannes Bäumler and Joost Jorristma, we estimate the arrival time of vertices in a uniform random recursive tree from its unlabeled structure. Using centrality-based rankings, we derive tail bounds for the relative estimation error that are uniform in 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 that it is smaller than the true arrival time by a factor $1/S$ decays exponentially in $S$. We introduce a refined centrality measure whose overestimation probability decays on the order of $(\log S)/S^{2}$, at the cost of a heavier lower tail of order $1/S^{2}$. These results identify a tradeoff between upper- and lower-tail performance in arrival-time estimation.

About Simon

Simon is a postdoc at Unidistance in the Team of David Belius. Before that, he was a postdoc fellow at the Simons Laufer Mathematical Science Institute for the Probability and Statistics of Discrete Structures program. He was a PhD student at Universitat Pompeu Fabra and Université Paris Saclay. His advisors were Gabor Lugosi and Christophe Giraud.

Simon works on probability and statistics problems. Most of his research is in combinatorial statistics, where he is interested in inferring the past of growing random graphs from a snapshot of their present state. He is also interested in Spin-Glasses models. Finally, he is interested in theoretical machine learning and high dimensional statistics.