Pith. sign in

REVIEW 3 minor 2 cited by

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

T0 review · 0 major / 3 minor · reviewed 2026-06-25 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A refined centrality measure based on iterated Jordan centralities improves overestimation tails for arrival-time estimates in uniform random recursive trees while retaining optimal risk.

desk verdict The paper introduces a refined iterated Jordan centrality that improves the upper tail for pointwise arrival-time estimation in uniform random recursive trees while worsening the lower tail, and shows this tradeoff is invisible to the usual risk but the measure still hits optimal risk order for all parameters. read the letter →

arxiv 2606.24465 v1 pith:MOVLNKGD submitted 2026-06-23 math.PR math.STstat.MLstat.TH

Johannes Bäumler , Simon Briend , Joost Jorritsma This is my paper · ORCID
classification math.PRmath.STstat.MLstat.TH
keywords randomrecursivetreesarrivaltimeestimationJordancentralitytailboundspointwisehistoryrelativeerroruniform
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper analyzes how well one can recover the arrival times of vertices in a uniform random recursive tree when only the final unlabeled tree is observed. It derives uniform tail bounds on the relative estimation error for two centrality-based estimators. Standard Jordan centrality produces an overestimation probability that decays like 1/S and an underestimation probability that decays exponentially in S. The refined measure changes these rates to order (log S)/S² for overestimation and 1/S² for underestimation. The work shows that this tradeoff is invisible when performance is measured only by average risk, yet the refined estimator still meets the optimal risk rate for every choice of its parameters.

What carries the argument

The refined centrality measure constructed by iterating the Jordan centrality on the tree.

What would settle it

Simulate many uniform random recursive trees of increasing size, compute the refined centrality ranks, form the relative estimation errors for each vertex, and check whether the empirical upper tail decays at rate (log S)/S² and the lower tail at rate 1/S².

Watch

Extended reading notes

Core claim

The authors prove that ranking vertices by a refined centrality measure obtained through iteration of the Jordan centrality yields relative arrival-time estimates whose probability of overestimating the true time by a factor S decays as (log S)/S², while the probability of underestimating by a factor 1/S decays as 1/S²; these tail bounds are uniform over all vertices and all tree sizes, the refined measure attains the optimal risk order for every parameter value, and the revealed upper-lower tail tradeoff cannot be seen from the risk functional alone.

Load-bearing premise

The observed tree is generated exactly as a uniform random recursive tree.

Editorial extensions

If this is right

  • Overestimation probability for the refined measure decays as (log S)/S².
  • Underestimation probability for the refined measure decays as 1/S².
  • The refined measure attains the optimal order of risk for every parameter value.
  • The upper-lower tail tradeoff is invisible when performance is judged only by average risk.
  • All tail bounds hold uniformly across vertices and tree sizes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Pointwise tail analysis can expose performance distinctions that aggregate risk measures miss in other network reconstruction tasks.
  • Iteration of centrality computations may improve estimation accuracy in related models of growing random structures.
  • Uniform tail bounds could support reliable inference procedures even when trees are large or only partially observed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper claims to derive tail bounds on the relative estimation error for vertex arrival times in uniform random recursive trees that are uniform over both vertices and tree size n. Using Jordan centrality, the overestimation probability decays as 1/S while underestimation decays exponentially in S. A refined iterated centrality measure improves the overestimation tail to order (log S)/S² (at the expense of a 1/S² lower tail) and is shown to attain the optimal risk order for every value of its parameter.

Significance. If the derivations hold, the work supplies a pointwise analysis that exposes an upper/lower-tail tradeoff invisible to integrated risk functionals and establishes that the refined measure is risk-optimal across its full parameter range. The uniform-in-n-and-vertex tail bounds and the explicit optimality statement for all parameter values are concrete strengths of the manuscript.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction should state the precise range of the iteration depth parameter for the refined centrality and whether the tail exponents remain uniform when this depth grows with n.
  2. [Notation] Notation for the relative error (over- and under-estimation factors) should be introduced once in a dedicated notation subsection rather than redefined inline in multiple places.
  3. [Figures] Figure captions for any simulation plots should include the exact number of Monte-Carlo repetitions and the range of n used, to allow direct comparison with the stated uniform bounds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were listed in the report, so there are no specific points requiring point-by-point response or manuscript changes at this stage.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity in derivation chain

full rationale

The paper derives tail bounds and risk optimality for Jordan centrality and its iterated refinement directly from the uniform random recursive tree generative model. The abstract and claims state explicit tail exponents and optimality conclusions under this explicit model without any reduction to fitted parameters, self-definitions, or load-bearing self-citations. The pointwise estimation analysis and tradeoff between tails are presented as consequences of the model, with no equations or steps that equate outputs to inputs by construction. This is a standard non-circular theoretical analysis on a stated probabilistic model.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Abstract-only review prevents identification of specific free parameters or additional axioms beyond the generative model.

assumptions (1)
  • domain assumption Input is a uniform random recursive tree
    The model under which all tail bounds and risk statements are derived, as stated in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities." pith.science (2026). https://pith.science/paper/MOVLNKGD

@misc{pith2026260624465,
  author       = {Pith},
  title        = {Pith review of: History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MOVLNKGD}},
  note         = {Machine review of arXiv:2606.24465}
}
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.

Figures

Figures reproduced from arXiv: 2606.24465 by the authors.

Figure 1
Figure 1. The Jordan-2 centrality of a vertex v in two trees t. The light-red tree represents (t, v(1))v↓. The tree contained in the turquoise area is (t, v(2))v (1)↓ . The Jordan-2 centrality ϕ (2) t (v) is given by the product of the number of vertices contained in the light-red and the turquoise areas for these examples. Typically, the turquoise tree is a superset of the light-red tree, but exceptions are possible, as show… view at source ↗
Figure 2
Figure 2. The left panel shows the empirical probabilities of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The fringe tree of 2 (blue, left panel), and the fringe tree of 2 witnessed after time [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: For v = 3, we have v (1) = 1 = pa(v) for the left tree, but v (1) = c = 4 ̸= pa(v) for the right tree. If pa(v) attains the minimum in the first equation in (2.11), then ϕn(v) = [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: The three cases we distinguish for the lower bound on [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: The indistinguishable vertices I7(t) in a recursive tree. For a recursive tree t of size 10, we display in white I7(t) = {5, 6, 7} as well as tτ for τ a permutation of I7(t). Lemma 4.2. Fix some v ≥ 1 and let I be a function acting in the space of recursive trees and r…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Finding Adam in noisy trees

    math.PR 2026-07 conditional novelty 7.0 of 10

    A uniform random recursive tree polluted by an Erdős–Rényi graph with p=o(log n/n) still admits a root confidence set of size depending only on ε, not on n.

  2. Subcritical percolation and network archaeology on random recursive tree substrate networks

    math.PR 2026-07 accept novelty 5.0 of 10

    For random recursive trees with independent Erdős–Rényi shortcut edges, subcritical bond percolation exposes a decorated tree structure on which Jordan centrality recovers the root within a deterministic-size confidence set.

Reference graph

Works this paper leans on

24 extracted references · 2 canonical work pages · cited by 2 Pith papers

  1. [1]

    Addario-Berry, A

    L. Addario-Berry, A. Brandenberger, S. Briend, N. Broutin, and G. Lugosi. Leaf stripping on uniform attachment trees.Random Structures & Algorithms, 67(1):e70023, 2025

    2025

  2. [2]

    Addario-Berry, C

    L. Addario-Berry, C. Fontaine, R. Khanfir, L.-R. Langevin, and S. Tˆ etu. Optimal root recovery for uniform attachment trees andd-regular growing trees.Preprint arXiv:2411.18614, 2024

    work page Pith review arXiv 2024

  3. [3]

    Banerjee and X

    S. Banerjee and X. Huang. Degree centrality and root finding in growing random networks.Electronic Journal of Probability, 28:1–39, 2023

    2023

  4. [4]

    B¨ aumler, C

    J. B¨ aumler, C. Kerriou, B. Lodewijks, J. Martin, E. Powierski, M. Z. R´ acz, and A. Sridhar. On the largest common subtree of uniform attachment trees.In preparation, 2026+

    2026

  5. [5]

    Correlated uniform attachment trees

    J. B¨ aumler, M. Z. R´ acz, N. Ross, and A. Sridhar. Correlated uniform attachment trees.Preprint arXiv:2606.02472, 2026

    work page Pith review arXiv 2026

  6. [6]

    Brandenberger, C

    A. Brandenberger, C. Marcussen, E. Mossel, and M. Sudan. Finding the root in random nearest neighbor trees.Random Structures & Algorithms, 68(2):e70057, 2026

    2026

  7. [7]

    A. M. Brandenberger, L. Devroye, and M. K. Goh. Root estimation in Galton–Watson trees.Random Structures & Algorithms, 61(3):520–542, 2022

    2022

  8. [8]

    Briend, F

    S. Briend, F. Calvillo, and G. Lugosi. Archaeology of random recursive dags and Cooper–Frieze random networks.Combinatorics, Probability and Computing, pages 1–15, 2023

    2023

Show all 24 references
  1. [9]

    Briend, C

    S. Briend, C. Giraud, G. Lugosi, and D. Sulem. Estimating the history of a random recursive tree. Bernoulli, 31(4):3260–3284, 2025

    2025

  2. [10]

    Bubeck, L

    S. Bubeck, L. Devroye, and G. Lugosi. Finding Adam in random growing trees.Random Structures & Algorithms, 50(2):158–172, 2017. 41

    2017

  3. [11]

    Contat, N

    A. Contat, N. Curien, P. Lacroix, E. Lasalle, and V. Rivoirard. Eve, Adam and the preferential attachment tree.Probability Theory and Related Fields, pages 1–16, 2024

    2024

  4. [12]

    Crane and M

    H. Crane and M. Xu. Inference on the history of a randomly growing tree.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 83(4):639–668, 2021

    2021

  5. [13]

    Crane and M

    H. Crane and M. Xu. Root and community inference on latent network growth processes using noisy attachment models.Journal of the Royal Statistical Society Series B: Statistical Methodology, 2023

    2023

  6. [14]

    Dereich and P

    S. Dereich and P. M¨ orters. Random networks with sublinear preferential attachment: Degree evolu- tions.Electronic Journal of Probability, (14):1222–1267, 2009

    2009

  7. [15]

    D. P. Dubhashi and D. Ranjan. Balls and bins: A study in negative dependence.BRICS Report Series, 3(25), 1996

    1996

  8. [16]

    Eggenberger and G

    F. Eggenberger and G. P´ olya. ¨Uber die statistik verketteter vorg¨ ange.ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift f¨ ur Angewandte Mathematik und Mechanik, 3(4):279–289, 1923

    1923

  9. [17]

    Goldschmidt

    C. Goldschmidt. A short introduction to random trees.Mongolian Math. J, 20:53–72, 2016

    2016

  10. [18]

    N. Hens, L. Calatayud, S. Kurkela, T. Tamme, and J. Wallinga. Robust reconstruction and analysis of outbreak data: influenza a (h1n1) v transmission in a school-based population.American journal of epidemiology, 176(3):196–203, 2012

    2012

  11. [19]

    Jog and P.-L

    V. Jog and P.-L. Loh. Persistence of centrality in random growing trees.Random Structures and Algorithms, 52(1):136–157, 2018

    2018

  12. [20]

    M. J. Keeling and K. T. Eames. Networks and epidemic models.Journal of the Royal Society Interface, 2(4):295–307, 2005

    2005

  13. [21]

    A. N. Magner, J. K. Sreedharan, A. Y. Grama, and W. Szpankowski. Times: Temporal information maximally extracted from structures. InProceedings of the 2018 World Wide Web Conference, pages 389–398, 2018

    2018

  14. [22]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal.Probability and computing: Randomization and probabilistic tech- niques in algorithms and data analysis. Cambridge university press, 2017

    2017

  15. [23]

    J. Neveu. Arbres et processus de Galton–Watson. InAnnales de l’IHP Probabilit´ es et statistiques, volume 22, pages 199–207, 1986

    1986

  16. [24]

    Young, G

    J.-G. Young, G. St-Onge, E. Laurence, C. Murphy, L. H´ ebert-Dufresne, and P. Desrosiers. Phase transition in the recoverability of network history.Physical Review X, 9(4):041056, 2019. 42

    2019

Pith tools

Reviewed June 25, 2026 · model on record in the stance chip above.