pith. machine review for the scientific record. sign in

arxiv: 2604.20139 · v1 · submitted 2026-04-22 · 🧮 math.PR

Recognition: unknown

Atypical Decay Rates for Atypical Heights in Random Recursive Trees

Xinxin Chen , Heng Ma
Authors on Pith no claims yet

Pith reviewed 2026-05-09 22:51 UTC · model grok-4.3

classification 🧮 math.PR
keywords large deviationsrandom recursive treestree heightupper taillower tailstretched exponentialatypical prefactor
0
0 comments X

The pith

The height of a random recursive tree deviates from its mean with polynomial probability on the high side and stretched-exponential probability on the low side, carrying an atypical prefactor.

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

The paper derives the exact large-deviation probabilities for the maximum height H_n of a random recursive tree on n nodes. It finds that the chance the height exceeds its typical value by a fixed multiple of log n decays like a negative power of n, while the chance it falls short of that value decays like a stretched exponential whose rate is slower than any power of log n. The lower-tail probability is further multiplied by a prefactor that tends to infinity more slowly than every iterated logarithm. These rates matter because they depart from the exponential decay that large-deviation principles usually produce on both sides, showing that the recursive attachment rule creates genuinely atypical tail behavior. A reader who accepts the result therefore obtains sharp control over the likelihood of both unusually tall and unusually short recursive trees.

Core claim

We establish the large deviation probabilities for the height of random recursive trees, revealing polynomial upper-tail decay and stretched-exponential lower-tail decay. Remarkably, the lower tail features an atypical prefactor that grows to infinity more slowly than any n-fold iterated logarithm.

What carries the argument

Large-deviation analysis of the height process under the uniform random attachment rule for recursive trees.

If this is right

  • Upper-tail events in which the tree is much taller than expected occur with power-law probability.
  • Lower-tail events in which the tree is much shorter occur with stretched-exponential probability multiplied by a slowly diverging prefactor.
  • The same distinction between polynomial and stretched-exponential regimes holds for the height process in the standard uniform-attachment construction.
  • The result supplies explicit asymptotics for the probability of atypical heights without additional model assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same tail distinction may appear in other recursively built random structures whose depth process obeys similar recursive distributional equations.
  • Simulations that track the prefactor across increasing n could test whether the growth is indeed slower than any iterated logarithm.
  • The atypical lower-tail behavior could affect algorithms whose running time is governed by the shortest path in a random recursive tree.

Load-bearing premise

The height process must satisfy sufficient concentration or moment bounds so that standard large-deviation techniques apply directly to the uniform attachment model without further restrictions.

What would settle it

Numerical sampling for n around 10^6 that shows the lower-tail probability decays exponentially rather than stretched-exponentially, or that the prefactor grows faster than every iterated logarithm, would refute the stated rates.

Figures

Figures reproduced from arXiv: 2604.20139 by Heng Ma, Xinxin Chen.

Figure 1
Figure 1. Figure 1: A realization of T1000 A fundamental statistic of interest is the height of the tree, defined as the maximum graph distance between the root v1 and any other vertex: Hn = H(Tn) := max 1≤k≤n dist(v1, vk) n ≥ 1, The asymptotic behavior of Hn has been studied extensively. The first-order asymptotic for the height Hn was established by Pittel [Pit94], who showed that Hn ∼ e ln n almost surely. Subsequently, Ad… view at source ↗
Figure 2
Figure 2. Figure 2: Example of the forest (T (j) 4,15)1≤j≤4 obtained from T15 by removing the edges between vertices in V[4] = {1, 2, 3, 4}. The highlighted blue edges on the left are precisely the removed edges. 2.1. Proof of Proposition 2.1. For the lower bound, we employ the following strategy, although a little bit crude, to ensure that Hn ≤ αe ln n. Fix a positive integer m ≤ n to ve determined later. For each 1 ≤ j ≤ m,… view at source ↗
Figure 3
Figure 3. Figure 3: A partition scheme: from a set A of size N + 1, one obtains d(N) − 1 blocks of size s(N) + 1 and one remainder block of size r(N); iterating the same rule on a size-s(N) + 1 block yields d(s(N)) − 1 blocks of size s(s(N)) + 1 and one remainder block of size r(s(N)). Using this scheme, we now construct the increasing tree on V[n+1] with height k. Assume that k ≥ 3 and n is large so that ln(k) (n) ≥ 1010. It… view at source ↗
Figure 4
Figure 4. Figure 4: From subset labeled tree to increasing tree It follows from (2.7) that ln [Psi(n) ] Li(n)  = Li(n) lnPsi(n) = n ln(i) (n) " 1 + o( 1 ln(i) (n) ) # ln(i) (n) h ln(i+1)(n) − ln(i+2)(n) + O(1)i = n h ln(i+1)(n) − ln(i+2)(n) + O(1)i . We obtain that the number of all possible configurations for Tset is bounded from below by exp  n ln n − n ln(k) n + Ok(n)  . Therefore this is also a lower bound for Ak(n + 1… view at source ↗
read the original abstract

We establish the large deviation probabilities for the height of random recursive trees, revealing polynomial upper-tail decay and stretched-exponential lower-tail decay. Remarkably, the lower tail features an atypical prefactor that grows to infinity more slowly than any $n$-fold iterated logarithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript establishes the large deviation probabilities for the height H_n of a random recursive tree on n nodes under the uniform attachment model. It proves that the upper tail P(H_n > (1+ε)log n) decays polynomially in n, while the lower tail P(H_n < (1-ε)log n) decays as a stretched exponential with an atypical prefactor that tends to infinity slower than any n-fold iterated logarithm.

Significance. If the results hold, the work makes a solid contribution to large-deviation theory for recursive combinatorial structures. The explicit verification of the necessary moment and concentration conditions, together with the refined renewal argument that isolates the slowly-varying prefactor, adds technical value beyond standard applications of large-deviation machinery. The atypical prefactor is a genuine novelty that may influence subsequent work on heights and depths in random trees.

minor comments (3)
  1. [§2] §2 (Main results): the statement of the lower-tail theorem should explicitly display the form of the stretched-exponential rate function and the slowly-varying prefactor (currently only described qualitatively in the abstract and introduction).
  2. [§4] §4 (Renewal argument): the passage from the renewal equation to the precise prefactor asymptotics would benefit from a short roadmap paragraph that isolates the key Tauberian or singularity-analysis step.
  3. [§1] Notation: the random variable H_n is introduced without a parenthetical reminder that it is the height of the tree on n nodes; a single clarifying sentence in the first paragraph of §1 would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. We are pleased that the significance of the polynomial upper-tail decay, the stretched-exponential lower-tail decay, and especially the atypical prefactor growing slower than any iterated logarithm is recognized as a genuine novelty. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No significant circularity

full rationale

This is a pure theoretical proof paper deriving large-deviation tail probabilities for the height of random recursive trees via standard large-deviation machinery, direct moment comparisons for the polynomial upper tail, and a refined renewal-type argument for the stretched-exponential lower tail with slowly-varying prefactor. All concentration and moment conditions are verified explicitly from the uniform attachment model without fitted parameters, self-definitional constructs, or load-bearing self-citations. The central claims rest on independent probabilistic estimates that do not reduce to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of the uniform random recursive tree and classical large-deviation principles for dependent processes; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption Uniform attachment model for random recursive trees
    The model is the canonical one in the literature; the abstract assumes its standard properties hold.
  • domain assumption Existence of large-deviation rate functions for the height process
    Invoked implicitly to obtain the stated decay rates.

pith-pipeline@v0.9.0 · 5319 in / 1254 out tokens · 46828 ms · 2026-05-09T22:51:44.475573+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 35 canonical work pages

  1. [1]

    Electron

    Iksanov, Alexander and Kabluchko, Zakhar , title =. Electron. Commun. Probab. , issn =. 2018 , language =. doi:10.1214/18-ECP188 , keywords =

    work page doi:10.1214/18-ecp188 2018

  2. [2]

    Bryc, Wlodek and Minda, David and Sethuraman, Sunder , title =. Adv. Appl. Probab. , issn =. 2009 , language =. doi:10.1239/aap/1253281066 , keywords =

    work page doi:10.1239/aap/1253281066 2009

  3. [3]

    J. L. Gastwirth and P. K. Bhattacharya , journal =. Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating That Their Promotional Claims Are Unreliable , urldate =

  4. [4]

    and Heyde, C

    Najock, D. and Heyde, C. C. , title =. J. Appl. Probab. , issn =. 1982 , language =. doi:10.2307/3213526 , keywords =

    work page doi:10.2307/3213526 1982

  5. [5]

    Chen, Xinxin and He, Hui , title =. Ann. Inst. Henri Poincar. 2020 , language =. doi:10.1214/20-AIHP1048 , keywords =

    work page doi:10.1214/20-aihp1048 2020

  6. [6]

    Ding, Jian , title =. Probab. Theory Relat. Fields , issn =. 2013 , language =. doi:10.1007/s00440-012-0457-9 , keywords =

    work page doi:10.1007/s00440-012-0457-9 2013

  7. [7]

    Random Struct

    Baur, Erich , title =. Random Struct. Algorithms , issn =. 2016 , language =. doi:10.1002/rsa.20603 , keywords =

    work page doi:10.1002/rsa.20603 2016

  8. [8]

    and Mahmoud, Hosam M

    Smythe, Robert T. and Mahmoud, Hosam M. , title =. Teor. 1994 , language =

    1994

  9. [9]

    Kingman, J. F. C. , title =. Ann. Probab. , issn =. 1975 , language =. doi:10.1214/aop/1176996266 , keywords =

    work page doi:10.1214/aop/1176996266 1975

  10. [10]

    , title =

    Devroye, L. , title =. Acta Inf. , issn =. 1987 , language =. doi:10.1007/BF00265991 , keywords =

    work page doi:10.1007/bf00265991 1987

  11. [11]

    2025 , howpublished =

    Alice Contat and Lucile Laulin , title =. 2025 , howpublished =

    2025

  12. [12]

    Broadcasting on random recursive trees , fjournal =

    Addario-Berry, Louigi and Devroye, Luc and Lugosi, G. Broadcasting on random recursive trees , fjournal =. Ann. Appl. Probab. , issn =. 2022 , language =. doi:10.1214/21-AAP1686 , keywords =

    work page doi:10.1214/21-aap1686 2022

  13. [13]

    Probabilistic methods for algorithmic discrete mathematics , isbn =

    Devroye, Luc , title =. Probabilistic methods for algorithmic discrete mathematics , isbn =. 1998 , publisher =

    1998

  14. [14]

    Holmgren, Cecilia and Janson, Svante , title =. Probab. Surv. , issn =. 2017 , language =. doi:10.1214/16-PS272 , keywords =

    work page doi:10.1214/16-ps272 2017

  15. [15]

    and Fill, James Allen , title =

    Dobrow, Robert P. and Fill, James Allen , title =. Comb. Probab. Comput. , issn =. 1999 , language =. doi:10.1017/S0963548399003855 , keywords =

    work page doi:10.1017/s0963548399003855 1999

  16. [16]

    Fuchs, Michael , title =. Comb. Probab. Comput. , issn =. 2008 , language =. doi:10.1017/S0963548308009243 , keywords =

    work page doi:10.1017/s0963548308009243 2008

  17. [17]

    Fuchs, Michael , title =. Comb. Probab. Comput. , issn =. 2012 , language =. doi:10.1017/S096354831100071X , keywords =

    work page doi:10.1017/s096354831100071x 2012

  18. [18]

    Bubeck, S. Finding. Random Struct. Algorithms , issn =. 2017 , language =. doi:10.1002/rsa.20649 , keywords =

    work page doi:10.1002/rsa.20649 2017

  19. [19]

    2024 , eprint=

    Optimal root recovery for uniform attachment trees and d -regular growing trees , author=. 2024 , eprint=

    2024

  20. [20]

    Random Struct

    Addario-Berry, Louigi and Eslava, Laura , title =. Random Struct. Algorithms , issn =. 2018 , language =. doi:10.1002/rsa.20753 , keywords =

    work page doi:10.1002/rsa.20753 2018

  21. [21]

    Goh, William and Schmutz, Eric , title =. J. Comput. Appl. Math. , issn =. 2002 , language =. doi:10.1016/S0377-0427(01)00460-5 , keywords =

    work page doi:10.1016/s0377-0427(01)00460-5 2002

  22. [22]

    Random Struct

    Dovroye, Luc and Lu, Jiang , title =. Random Struct. Algorithms , issn =. 1995 , language =. doi:10.1002/rsa.3240070102 , keywords =

    work page doi:10.1002/rsa.3240070102 1995

  23. [23]

    Random Struct

    Janson, Svante , title =. Random Struct. Algorithms , issn =. 2005 , language =. doi:10.1002/rsa.20046 , keywords =

    work page doi:10.1002/rsa.20046 2005

  24. [24]

    Electron

    Janson, Svante , title =. Electron. Commun. Probab. , issn =. 2020 , language =. doi:10.1214/20-ECP345 , keywords =

    work page doi:10.1214/20-ecp345 2020

  25. [25]

    Kabluchko, Zakhar and Marynych, Alexander and Sulzbach, Henning , title =. Ann. Appl. Probab. , issn =. 2017 , language =. doi:10.1214/17-AAP1285 , keywords =

    work page doi:10.1214/17-aap1285 2017

  26. [26]

    Algorithmica , issn =

    Fuchs, Michael and Hwang, Hsien-Kuei and Neininger, Ralph , title =. Algorithmica , issn =. 2006 , language =. doi:10.1007/s00453-006-0109-5 , keywords =

    work page doi:10.1007/s00453-006-0109-5 2006

  27. [27]

    , title =

    Gastwirth, Joseph L. , title =. Am. Stat. , issn =. 1977 , language =. doi:10.2307/2683046 , keywords =

    work page doi:10.2307/2683046 1977

  28. [28]

    Moon, J. W. , editor=. The distance between nodes in recursive trees , booktitle=. 1974 , pages=

    1974

  29. [29]

    Na, H. S. and Rapoport, Anatol , title =. Math. Biosci. , issn =. 1970 , language =. doi:10.1016/0025-5564(70)90071-4 , url =

    work page doi:10.1016/0025-5564(70)90071-4 1970

  30. [30]

    Drmota, Michael , Title =. Ann. Comb. , ISSN =. 2009 , Language =. doi:10.1007/s00026-009-0009-x , Keywords =

    work page doi:10.1007/s00026-009-0009-x 2009

  31. [31]

    and Reed, B

    Addario-Berry, L. and Reed, B. A. , title =. Horizons of combinatorics. Survey papers related to the conference, Balatonalm\'adi, Hungary, July 17--21, 2006 , isbn =. 2008 , publisher =

    2006

  32. [32]

    Dembo and Z

    Dembo, Amir and Zeitouni, Ofer , title =. 2010 , publisher =. doi:10.1007/978-3-642-03311-7 , keywords =

    work page doi:10.1007/978-3-642-03311-7 2010

  33. [33]

    Devroye, Luc and Fawzi, Omar and Fraiman, Nicolas , title =. Proceeding of the 21st international meeting on probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms (AofA'10), Vienna, Austria, June 28 -- July 2, 2010 , pages =. 2010 , publisher =

    2010

  34. [34]

    Cambridge University Press, 2017

    Mitzenmacher, Michael and Upfal, Eli , title =. 2005 , publisher =. doi:10.1017/CBO9780511813603 , keywords =

    work page doi:10.1017/cbo9780511813603 2005

  35. [35]

    Approximation, randomization, and combinatorial optimization

    Impagliazzo, Russell and Kabanets, Valentine , Title =. Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1--3, 2010. Proceedings , ISBN =. 2010 , Publisher =. doi:10.1007/978-3-642-15369-3_46 , Keywords =

    work page doi:10.1007/978-3-642-15369-3_46 2010

  36. [36]

    2011 , eprint=

    On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands , author=. 2011 , eprint=

    2011

  37. [37]

    Random Struct

    Pittel, Boris , Title =. Random Struct. Algorithms , ISSN =. 1994 , Language =. doi:10.1002/rsa.3240050207 , Keywords =

    work page doi:10.1002/rsa.3240050207 1994

  38. [38]

    Correction terms for the height of weighted recursive trees , FJournal =

    Pain, Michel and S. Correction terms for the height of weighted recursive trees , FJournal =. Ann. Appl. Probab. , ISSN =. 2022 , Language =. doi:10.1214/21-AAP1756 , Keywords =

    work page doi:10.1214/21-aap1756 2022

  39. [39]

    Height of weighted recursive trees with sub-polynomially growing total weight , FJournal =

    Pain, Michel and S. Height of weighted recursive trees with sub-polynomially growing total weight , FJournal =. Ann. Inst. Henri Poincar. 2024 , Language =. doi:10.1214/23-AIHP1379 , Keywords =

    work page doi:10.1214/23-aihp1379 2024

  40. [40]

    Convergence in law of the minimum of a branching random walk , FJournal =

    A. Convergence in law of the minimum of a branching random walk , FJournal =. Ann. Probab. , ISSN =. 2013 , Language =. doi:10.1214/12-AOP750 , Keywords =

    work page doi:10.1214/12-aop750 2013

  41. [41]

    Addario-Berry, Louigi and Ford, Kevin , Title =. Ann. Appl. Probab. , ISSN =. 2013 , Language =. doi:10.1214/12-AAP840 , Keywords =

    work page doi:10.1214/12-aap840 2013

  42. [42]

    2009 , Publisher =

    Drmota, Michael , Title =. 2009 , Publisher =. doi:10.1007/978-3-211-75357-6 , Keywords =

    work page doi:10.1007/978-3-211-75357-6 2009

  43. [43]

    Drmota, Michael , Title =. J. ACM , ISSN =. 2003 , Language =. doi:10.1145/765568.765572 , Keywords =

    work page doi:10.1145/765568.765572 2003

  44. [44]

    , Title =

    Drmota, M. , Title =. Algorithmica , ISSN =. 2001 , Language =

    2001

  45. [45]

    Reed, Bruce , Title =. J. ACM , ISSN =. 2003 , Language =. doi:10.1145/765568.765571 , Keywords =

    work page doi:10.1145/765568.765571 2003