We study a model of random binary trees grown “by the leaves" in the style of Luczak and Winkler [LW04]. If $\tau _n$ is a uniform plane binary tree of size $n$, Luczak and Winkler, and later explicitly Caraceni and Stauffer, constructed a measure $\nu _{\tau _n}$ such that the tree obtained by adding a cherry on a leaf sampled according to $\nu _{\tau _n}$ is still uniformly distributed on the set of all plane binary trees with size $n+1$. It turns out that the measure $\nu _{\tau _n}$, which we call the leaf-growth measure, is noticeably different from the uniform measure on the leaves of the tree $\tau _n$. In fact we prove that, as $n \rightarrow \infty $, with high probability it is almost entirely supported by a subset of only $n^{3 (2 - \sqrt{3})+o(1)} \approx n^{0.8038...} \text{ leaves}$. In the continuous setting, we construct the scaling limit of uniform binary trees equipped with this measure, which is the Brownian Continuum Random Tree equipped with a probability measure supported by a fractal set of dimension $ 6 (2 - \sqrt{3})$. We also compute the full (discrete) multifractal spectrum. This work is a first step towards understanding the diffusion limit of the discrete leaf-growth procedure.
Nous étudions un modèle d’arbres aléatoires croissant « par les feuilles », dans l’esprit de Luczak et Winkler [LW04]. Si $\tau _n$ désigne un arbre plan binaire uniforme de taille $n$, Luczak et Winkler, puis plus explicitement Caraceni et Stauffer, ont construit une mesure $\nu _{\tau _n}$ telle que l’arbre obtenu en ajoutant une « cerise » à une feuille choisie selon la distribution $\nu _{\tau _n}$ soit encore uniforme dans l’ensemble des arbres plans binaires de taille $n+1$. La mesure $\nu _{\tau _n}$ s’avère remarquablement différente de la mesure uniforme sur les feuilles de $\tau _n$. En particulier, nous prouvons que, lorsque $n \rightarrow \infty $, avec grande probabilité, elle est presque entièrement supportée par $n^{3(2-\sqrt{3})+o(1)} \approx n^{0.8038\ldots }$ feuilles. Nous construisons également sa limite d’échelle, une mesure de probabilité sur l’arbre continu brownien dont le support est fractal, de dimension $6(2-\sqrt{3})$. Nous calculons de plus son spectre multifractal. Ce travail constitue une première étape vers la compréhension de la diffusion obtenue comme limite de la procédure de croissance par les feuilles.
Accepté le :
Publié le :
Keywords: Random trees, scaling limits, self-similar fragmentations, Hausdorff dimension, multifractal spectrum
Mots-clés : Arbres aléatoires, limites d’échelle, fragmentations auto-similaires, dimension de Hausdorff, spectre multifractal
Alessandra Caraceni 1 ; Nicolas Curien 2 ; Robin Stephenson 3
CC-BY 4.0
Alessandra Caraceni; Nicolas Curien; Robin Stephenson. Where do (random) trees grow leaves?. Journal de l’École polytechnique — Mathématiques, Tome 13 (2026), pp. 1151-1184. doi: 10.5802/jep.345
@article{JEP_2026__13__1151_0,
author = {Alessandra Caraceni and Nicolas Curien and Robin Stephenson},
title = {Where do (random) trees grow leaves?},
journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
pages = {1151--1184},
year = {2026},
publisher = {\'Ecole polytechnique},
volume = {13},
doi = {10.5802/jep.345},
language = {en},
url = {https://jep.centre-mersenne.org/articles/10.5802/jep.345/}
}
TY - JOUR AU - Alessandra Caraceni AU - Nicolas Curien AU - Robin Stephenson TI - Where do (random) trees grow leaves? JO - Journal de l’École polytechnique — Mathématiques PY - 2026 SP - 1151 EP - 1184 VL - 13 PB - École polytechnique UR - https://jep.centre-mersenne.org/articles/10.5802/jep.345/ DO - 10.5802/jep.345 LA - en ID - JEP_2026__13__1151_0 ER -
%0 Journal Article %A Alessandra Caraceni %A Nicolas Curien %A Robin Stephenson %T Where do (random) trees grow leaves? %J Journal de l’École polytechnique — Mathématiques %D 2026 %P 1151-1184 %V 13 %I École polytechnique %U https://jep.centre-mersenne.org/articles/10.5802/jep.345/ %R 10.5802/jep.345 %G en %F JEP_2026__13__1151_0
[AB14] - “Growing random 3-connected maps”, Electron. Comm. Probab. 19 (2014), article ID 54, 12 pages | DOI
[ADH13] - “A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces”, Electron. J. Probab. 18 (2013), article ID 14, 21 pages | DOI
[Ald91a] - “The continuum random tree. I”, Ann. Probab. 19 (1991) no. 1, p. 1-28
[Ald91b] - “The continuum random tree. II. An overview”, in Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser., vol. 167, Cambridge Univ. Press, Cambridge, 1991, p. 23-70 | DOI
[Ald93] - “The continuum random tree. III”, Ann. Probab. 21 (1993) no. 1, p. 248-289
[ALW16] - “The gap between Gromov-vague and Gromov–Hausdorff-vague topology”, Stochastic Process. Appl. 126 (2016) no. 9, p. 2527-2553 | DOI
[BBJ17] - “Efficient random sampling of binary and unary-binary trees via holonomic equations”, Theoret. Comput. Sci. 695 (2017), p. 42-53
[Ber02] - “Self-similar fragmentations”, Ann. Inst. H. Poincaré Probab. Statist. 38 (2002) no. 3, p. 319-340
[Bil65] - Ergodic theory and information, Wiley Series in Probab. and Math. Stat., Wiley, 1965
[BK16] - “Self-similar scaling limits of Markov chains on the positive integers”, Ann. Appl. Probab. 26 (2016) no. 4, p. 2556-2595 | DOI
[CFT25] - “Growing self-similar Markov trees”, 2025, work in progress
[CH13] - “The stable trees are nested”, Probab. Theory Relat. Fields 157 (2013) no. 3-4, p. 847-883 | DOI
[CLG17] - “The harmonic measure of balls in random trees”, Ann. Probab. 45 (2017) no. 1, p. 147-209
[CPY97] - “On the distribution and asymptotic results for exponential functionals of Lévy processes”, in Exponential functionals and principal values related to Brownian motion, Bibl. Rev. Mat. Iberoamericana, Revista Matemática Iberoamericana, Madrid, 1997, p. 73-130
[CS20] - “Polynomial mixing time of edge flips on quadrangulations”, Probab. Theory Relat. Fields 176 (2020) no. 1-2, p. 35-76 | DOI
[CS23] - “Growing uniform planar maps face by face”, Random Structures Algorithms 63 (2023) no. 4, p. 942-967 | DOI
[DLG05] - “Probabilistic and fractal aspects of Lévy trees”, Probab. Theory Relat. Fields 131 (2005) no. 4, p. 553-603
[DLG06] - “The Hausdorff measure of stable trees”, Alea 1 (2006), p. 393-415
[EPW06] - “Rayleigh processes, real trees, and root growth with re-grafting”, Probab. Theory Relat. Fields 134 (2006) no. 1, p. 81-126 | DOI
[EW06] - “Subtree prune and regraft: a reversible tree-valued Markov process”, Ann. Probab. 34 (2006) no. 3, p. 81-126
[FPRW18] - “Aldous diffusion I: a projective system of continuum -tree evolutions”, 2018 | arXiv
[FPRW20] - “Projections of the Aldous chain on binary trees: intertwining and consistency”, Random Structures Algorithms 57 (2020) no. 3, p. 745-769 | DOI
[FPRW23] - “The Aldous diffusion: a stationary evolution of the Brownian CRT”, 2023 | arXiv
[GP19] - “Parking on a random tree”, Combin. Probab. Comput. 28 (2019) no. 1, p. 23-45
[HM04] - “The genealogy of self-similar fragmentations with negative index as a continuum random tree”, Electron. J. Probab. 9(4) (2004), p. 57-97
[HM12] - “Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees”, Ann. Probab. 40 (2012) no. 6, p. 2589-2666
[HS15] - “Scaling limits of -ary growing trees”, Ann. Inst. H. Poincaré Probab. Statist. 51 (2015) no. 4, p. 1314-1341 | DOI
[Khe20] - “Metrization of the Gromov–Hausdorff(-Prokhorov) topology for boundedly-compact metric spaces”, Stochastic Process. Appl. 130 (2020) no. 6, p. 3842-3864
[Khe23] - “A unified framework for generalizing the Gromov-Hausdorff metric”, Probab. Surv. 20 (2023), p. 837-896
[Lam62] - “Semi-stable stochastic processes”, Trans. Amer. Math. Soc. 104 (1962), p. 62-78
[Law93] - “A discrete analogue of a theorem of Makarov”, Combin. Probab. Comput. 2 (1993) no. 2, p. 181-199
[LG05] - “Random trees and applications”, Probab. Surv. 2 (2005), p. 245-311 | DOI
[LMW20] - “The Aldous chain on cladograms in the diffusion limit”, Ann. Probab. 48 (2020) no. 5, p. 2565-2590 | DOI
[LPP95] - “Ergodic theory on Galton–Watson trees: speed of random walk and dimension of harmonic measure”, Ergodic Theory Dynam. Systems 15 (1995) no. 3, p. 593-619
[LPS08] - “Growth of the number of spanning trees of the Erdős–Rényi giant component”, Combin. Probab. Comput. 17 (2008) no. 5, p. 711-726
[LW04] - “Building uniformly random subtrees”, Random Structures Algorithms 24 (2004) no. 4, p. 420-443 | DOI
[Mar03] - “Constructing a sequence of random walks strongly converging to Brownian motion”, in Discrete random walks (Paris, 2003), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003, p. 181-190
[Mar23] - “Growing random uniform d-ary trees”, Ann. Comb. 27 (2023) no. 1, p. 51-66
[MT99] - “On the mixing time of the triangulation walk and other Catalan structures”, in Randomization methods in algorithm design (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 43, American Mathematical Society, Providence, RI, 1999, p. 147-160 | DOI
[PW15] - “Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes”, Ann. Probab. 43 (2015) no. 5, p. 2611-2646 | DOI
[Rém85] - “Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire”, RAIRO Inform. Théor. 19 (1985) no. 2, p. 179-195
[Ste13] - “General fragmentation trees”, Electron. J. Probab. 18(101) (2013), p. 1-45
Cité par Sources :