---
abstract: |
    We consider a family of random trees satisfying a Markov branching property. Roughly, this property says that the subtrees above some given height are independent with a law that depends only on their total size, the latter being either the number of leaves or vertices. Such families are parameterized by sequences of distributions on partitions of the integers, that determine how the size of a tree is distributed in its different subtrees. Under some natural assumption on these distributions, stipulating that "macroscopic" splitting events are rare, we show that Markov branching trees admit the so-called self-similar fragmentation trees as scaling limits in the Gromov-Hausdorff-Prokhorov topology.

    The main application of these results is that the scaling limit of random uniform unordered trees is the Brownian continuum random tree. This extends a result by Marckert-Miermont and fully proves a conjecture by Aldous. We also recover, and occasionally extend, results on scaling limits of consistent Markov branching model, and known convergence results of Galton-Watson trees towards the Brownian and stable continuum random trees.
author:
- 'Bénédicte Haas[^1] and Grégory Miermont[^2]'
bibliography:
- 'BibJune08.bib'
title: |
    Scaling limits of Markov branching trees\
    <span>with applications to Galton-Watson and random unordered trees [^3]</span>
---

Introduction and main results {#MBTrees}
=============================

The goal of this paper is to discuss the scaling limits of a model of random trees satisfying a simple Markovian branching property, that was considered in @HMPW06, and considered in different forms in a number of places @Devroye [@Aldous96; @BrDeMcLdlS]. Markov branching trees are natural models of random trees, defined in terms of discrete fragmentation processes. The laws of these trees are indexed by an integer $n$ giving the "size" of the tree, which leads us to consider two distinct (but related) models, in which the sizes are respectively the number of leaves and the number of vertices. We first provide a slightly informal description of our results.

Let $q=(q_n,n\geq 1)$ be a family of probability distributions, respectively on the set ${\mathcal{P}}_n$ of partitions of the integer $n$, i.e. of non-increasing integer sequences with sum $n$. We assume that $q_n$ does not assign mass $1$ to the trivial partition $(n)$: $$q_n((n))<1\, ,\qquad \mbox{for every } n\geq 1\, .$$ In order that this makes sense for $n=1$, we add an extra "empty partition" $\emptyset$ to ${\mathcal{P}}_1$.

One constructs a random rooted tree with $n$ leaves according to the following procedure. Start from a collection of $n$ indistinguishable balls, and with probability $q_n(\lambda_1,\ldots,\lambda_p)$, split the collection into $p$ sub-collections with $\lambda_1,\ldots,\lambda_p$ balls. Note that there is a chance $q_n((n))<1$ that the collection remains unchanged during this step of the procedure. Then, re-iterate the splitting operation independently for each sub-collection using this time the probability distributions $q_{\lambda_1},\ldots,q_{\lambda_p}$. If a sub-collection consists of a single ball, it can remain single with probability $q_1((1))$ or get wiped out with probability $q_1(\emptyset)$. We continue the procedure until all the balls are wiped out. There is a natural genealogy associated with this process, which is a tree with $n$ leaves consisting in the $n$ isolated balls just before they are wiped out, and rooted at the initial collection of $n$ balls. See Figure \[fig:CMB\] for an illustration. We let ${\mathsf{P}}^q_n$ be the law of this tree.

![A sample tree $T_{11}$. The first splitting arises with probability $q_{11}(4,4,3)$.<span data-label="fig:CMB"></span>](CMB)

This construction can be seen as the most general form of <span> *splitting trees*</span> of Broutin & al. @BrDeMcLdlS, and was referred to as trees bearing the so-called <span>*Markov branching property*</span> in @HMPW06. There is also a variant of this procedure that constructs a random tree with $n$ vertices rather than $n$ leaves. This one does not need the hypothesis $q_n((n))<1$ for $n\geq 1$, and in fact we only assume $q_1((1))=1$ for consistency of the description to follow. Informally, starting from a collection of $n$ balls, we first remove a ball, split the $n-1$ remaining balls in sub-collections with $\lambda_1,\ldots,\lambda_p$ balls with probability $q_{n-1}((\lambda_1,\ldots,\lambda_p))$, and iterate independently on sub-collections until no ball remains. We let ${\mathsf{Q}}^q_n$ be the law of the random tree associated to this procedure.

While most papers so far have been focusing on families of trees having more structure, such as a consistency property when $n$ varies @Aldous96 [@HMPW06; @Devroye] (with the notable exception of Broutin & al. @BrDeMcLdlS), the main goal of the present work is to study the structure of trees with laws ${\mathsf{P}}^q_n$ or ${\mathsf{Q}}^q_n$ as $n\to\infty$ in a very general situation. The main assumption that we make is that, as $n\to\infty$,

> macroscopic splitting events of the form $n\to (ns_1,ns_2,\ldots)\in
> {\mathcal{P}}_n$ for a non-increasing sequence ${\mathbf{s}}=(s_1,s_2,\ldots)$ with sum $1$ and such that $s_1<1-{\varepsilon}$, for some ${\varepsilon}\in (0,1)$, are rare events, occurring with probability of order $n^{-\gamma}\nu_{\varepsilon}({\mathrm{d}}{\mathbf{s}})$ for some $\gamma>0$, for some finite "intensity" measure $\nu_{\varepsilon}$.

Note that the measures $\nu_{\varepsilon}$ should satisfy a consistency property as ${\varepsilon}$ varies, and as ${\varepsilon}$ goes to $0$, $\nu_{\varepsilon}$ should increase to a possibly infinite measure on the set of non-increasing sequences with sum $1$. This means that splitting events that only remove tiny parts from a large collection of balls are allowed to remain more frequent than the order $n^{-\gamma}$. Under this assumption, formalized in hypothesis <span>**(H)**</span> below, we show in Theorem \[sec:main-result-1\] that a tree $T_n$ with law ${\mathsf{P}}^q_n$, considered as a metric space by viewing its edges as being real segments of lengths of order $n^{-\gamma}$, converges in distribution towards a limiting structure ${\mathcal{T}}_{\gamma,\nu}$, the so-called self-similar fragmentation tree of @HM04: $$\frac{1}{n^\gamma}T_n\longrightarrow {\mathcal{T}}_{\gamma,\nu}\, .$$ When $\gamma\in (0,1)$, a similar result (Theorem \[sec:main-result-2\]) holds when $T_n$ has distribution ${\mathsf{Q}}^q_n$.

The limiting tree ${\mathcal{T}}_{\gamma,\nu}$ can be seen as the genealogical tree of a continuous model for mass splitting, in some sense analogous to the Markov branching property described above. The above convergence holds in distribution in a space of measured metric spaces, endowed with the so-called Gromov-Hausdorff-Prokhorov topology. This result contrasts with the situation of @BrDeMcLdlS, where it is assumed that macroscopic splitting events occur at every step of the construction. In that case, the height of $T_n$ is of order $\log n$, and no interesting scaling limit exists. A key step in our study will be to use the results from @HaMi09, where scaling limits of non-increasing Markov chains were considered: such Markov chains are indeed obtained by considering the successive sizes of collections containing a particular marked ball when going up in the tree $T_n$.

This general statement allows to recover, and sometimes improve, many results of @HMPW06 [@HPW; @PiWi08; @CFW] dealing specifically with Markov branching trees. It also applies to models of random trees that are not <span>*a priori*</span> directly connected to our study. In particular, we recover the results of Aldous @AldousCRTIII and Duquesne @duq02 showing that the so-called Brownian and stable trees @AldousCRTI [@LeGall/LeJan; @dlg02; @dlg05] are universal limits for conditioned Galton-Watson trees.

More notably, our results allow to prove that uniform unordered trees with $n$ vertices and degrees bounded by some integer $m+1\in
[3,\infty]$ admit the Brownian continuum random tree as a scaling limit. This was conjectured by Aldous @AldousCRTII and proved in @MaMi09 in the particular case $m=2$ of a binary branching, using completely different methods from ours. The difficulty of handling such families of random trees comes from the fact that they have no 'nice' probabilistic representations, using for instance branching processes or growth models. As a matter of fact, uniform random unordered trees do not even have the Markov branching property, but turn out to 'almost' bear this property, in a sense that will be explained below.

The rest of this section is devoted to a detailed formalization of our results. Throughout the paper, we use the notations $${\mathbb{N}}=\{1,2,3,\ldots\}\, ,\qquad {\mathbb{Z}}_+=\{0\}\cup {\mathbb{N}}\, ,\qquad
[n]=\{1,2,\ldots,n\}\, ,\quad n\in {\mathbb{N}}\, .$$ The random variables appearing in this paper are either canonical or defined on some probability space $(\Omega,{\mathcal{F}},{\mathbb{P}})$.

<span>**Acknowledgment.** </span>We are deeply indebted to Jean-François Marckert, who suggested that the methods of @HMPW06 could be relevant to tackle the problem of scaling limits of uniform unordered trees. This provided the initial spark for the present work and @HaMi09.

Discrete trees {#sec:discrete-trees}
--------------

We briefly introduce some formalism for trees. Set ${\mathbb{N}}^0=\{\varnothing\}$, and let $$\mathcal{U}=\bigcup_{n\geq 0}{\mathbb{N}}^n\, .$$ For $u=(u_1,\ldots,u_n)\in
\mathcal{U}$, we denote by $|u|$ the length of $u$, also called the height of $u$. If $u=(u_1,\ldots,u_n)$ with $n\geq 1$, we let $\mathrm{pr}(u)=(u_1,\ldots,u_{n-1})$, and for $i\geq 1$, we let $ui=(u_1,\ldots,u_n,i)$. More generally, for $u=(u_1,\ldots,u_n)$ and $v=(v_1,\ldots,v_m)$ in $\mathcal{U}$, we let $uv=(u_1,\ldots,u_n,v_1,\ldots,v_m)$ be their concatenation, and for $A\subset \mathcal{U}$ and $u\in \mathcal{U}$, we let $uA=\{uv:v\in
A\}$, and simply let $iA=(i)A$ for $i\in {\mathbb{N}}$. We say that $u$ is a prefix of $v$ if $v\in u\mathcal{U}$, and write $u\preceq v$, defining a partial order on $\mathcal{U}$.

A plane tree is a non-empty, finite subset ${\mathbbm{t}}\subset \mathcal{U}$ (whose elements are called <span>*vertices*</span>), such that

-   If $u\in {\mathbbm{t}}$ with $|u|\geq 1$, then $\mathrm{pr}(u)\in {\mathbbm{t}}$,

-   If $u\in {\mathbbm{t}}$, then there exists a number $c_u({\mathbbm{t}})\in {\mathbb{Z}}_+$ (the number of children of $u$) such that $ui\in {\mathbbm{t}}$ if and only if $1\leq
    i\leq c_u({\mathbbm{t}})$.

Let $\partial{\mathbbm{t}}=\{u\in {\mathbbm{t}}:c_u({\mathbbm{t}})=0\}$ be the set of <span>*leaves*</span> of ${\mathbbm{t}}$. If ${\mathbbm{t}}^{(1)},\ldots,{\mathbbm{t}}^{(k)}$ are plane trees, we can define a new plane tree by $$\langle{\mathbbm{t}}^{(1)},\ldots,{\mathbbm{t}}^{(k)}\rangle=\{\varnothing\}\cup \bigcup_{i=1}^k i{\mathbbm{t}}^{(i)}\, .$$

A plane tree has a natural graphical representation, in which every $u\in {\mathbbm{t}}$ is a vertex, joined to its $c_u({\mathbbm{t}})$ children by as many edges. But ${\mathbbm{t}}$ carries more information than the graph, as it has a natural ordered structure. In this work, we will not be interested in this order, and we present one way to get rid of this unwanted structure. Let ${\mathbbm{t}}$ be a plane tree, and ${\boldsymbol{\sigma}}=(\sigma_u,u\in
{\mathbbm{t}})$ be a sequence of permutations, respectively $\sigma_u\in\mathfrak{S}_{c_u({\mathbbm{t}})}$. For $u=(u_1,\ldots,u_n)\in {\mathbbm{t}}$, let $${\boldsymbol{\sigma}}(u)=\big(\sigma_{\varnothing}(u_1),
\sigma_{(u_1)}(u_2),\sigma_{(u_1,u_2)}(u_3),\ldots,
\sigma_{(u_1,\ldots,u_{n-1})}(u_n)\big)\, ,$$ and ${\boldsymbol{\sigma}}(\varnothing)=\varnothing$. Then the set ${\boldsymbol{\sigma}}{\mathbbm{t}}=\{{\boldsymbol{\sigma}}(u):u\in {\mathbbm{t}}\}$ is a plane tree, obtained intuitively by shuffling the set of children of $u$ in ${\mathbbm{t}}$ according to the permutation $\sigma_u$. We say that ${\mathbbm{t}},{\mathbbm{t}}'$ are equivalent if there exists some ${\boldsymbol{\sigma}}$ such that ${\boldsymbol{\sigma}}({\mathbbm{t}})={\mathbbm{t}}'$. Equivalence classes of plane trees will be called (rooted) <span>*unordered trees*</span>, or simply <span>*trees*</span> as opposed to plane trees, and denoted by lowercase letters ${\mathsf{t}}$. When dealing with a tree ${\mathsf{t}}$, we will freely adapt some notations from plane trees when dealing with quantities that do not depend on particular plane representatives. For instance, $\#{\mathsf{t}},\#\partial{\mathsf{t}}$ will denote the number of vertices and leaves of ${\mathsf{t}}$, while $\varnothing,
c_\varnothing({\mathsf{t}})$ will denote the root of ${\mathsf{t}}$ and its degree.

We let ${\mathsf{T}}$ be the set of trees, and for $n\geq 1$, $${\mathsf{T}}^\partial_n=\{{\mathsf{t}}\in {\mathsf{T}}:\#\partial{\mathsf{t}}= n\}\, ,\qquad
{\mathsf{T}}_n=\{{\mathsf{t}}\in {\mathsf{T}}:\#{\mathsf{t}}= n\}$$ be the set of trees with $n$ leaves, resp. $n$ vertices. The class of $\{\varnothing\}$ is the vertex tree $\bullet\in {\mathsf{T}}_1={\mathsf{T}}^\partial_1$.

Heuristically, the information carried in a tree is its graph structure, with a distinguished "root" vertex corresponding to $\varnothing$, and considered up to root-preserving graph isomorphisms — it is not embedded in any space, and its vertices are unlabeled. It is a simple exercise to see that if ${\mathsf{t}}^{(i)},1\leq i\leq k$ are trees, and ${\mathbbm{t}}^{(i)}$ is a choice of a plane representative of ${\mathsf{t}}^{(i)}$ for each $i$, then the class of $\langle {\mathbbm{t}}^{(i)},1\leq
i\leq k\rangle $ does not depend on the particular choice for ${\mathbbm{t}}^{(i)}$. We denote this common class by $\langle{\mathsf{t}}^{(i)},1\leq
i\leq k\rangle$. Note that $j({\mathsf{t}}):=\langle{\mathsf{t}}\rangle$ can be seen as the tree ${\mathsf{t}}$ whose root has been attached to a new root by an edge, and $j^l ({\mathsf{t}})$, for $l\geq 0$, is tree ${\mathsf{t}}$ whose root has been attached to a new root by a string of $l$ edges. For instance, $j^l(\bullet)$ is the line-tree consisting of a string with length $l$, rooted at one of its ends. Finally, for trees ${\mathsf{t}}^{(1)},\ldots,{\mathsf{t}}^{(k)}$ and $l\geq 1$ we let $$\langle{\mathsf{t}}^{(1)},\ldots,{\mathsf{t}}^{(k)}\rangle_l=
j^l(\langle{\mathsf{t}}^{(1)},\ldots,{\mathsf{t}}^{(k)}\rangle)\, ,$$ so $j^l(\bullet)=\langle\bullet\rangle_l$ with these notations.

Markov branching trees {#sec:mark-branch-models}
----------------------

A partition of an integer $n\geq 1$ is a sequence of integers $\lambda=(\lambda_1,\ldots,\lambda_p)$ with $\lambda_1\geq\ldots\geq
\lambda_p\geq 1$ and $\lambda_1+\ldots+\lambda_p = n$. The number $p=p(\lambda)$ is called the number of parts of the partition $\lambda$, and the partition is called non-trivial if $p(\lambda)\geq
2$. We let ${\mathcal{P}}_n$ be the set of partitions of the integer $n$. We also add an extra element $\emptyset$ to ${\mathcal{P}}_1$, so that ${\mathcal{P}}_1=\{(1),\emptyset\}$.

For $\lambda\in {\mathcal{P}}_n$ and $1\leq j\leq n$, we define $$m_j(\lambda)=\#\{i\in\{1,2,\ldots,p(\lambda)\}:\lambda_i=j\}\, ,$$ the multiplicity of parts of $\lambda$ equal to $j$.

By convention, it is sometimes convenient to set $\lambda_i=0$ for $i>p(\lambda)$, and to identify the sequence $\lambda$ with the infinite sequence $(\lambda_i,i\geq 1)$. Such identifications will be implicit when needed.

### Markov branching trees with a prescribed number of leaves {#sec:mark-branch-trees}

In this paragraph, the size of a tree ${\mathsf{t}}\in {\mathsf{T}}$ is going to be the number $\#\partial{\mathsf{t}}$ of its leaves.

Let $q=(q_n,n\geq 1)$ be a sequence of probability distributions respectively on $\mathcal{P}_n$, $$q_n=(q_n(\lambda),\lambda\in \mathcal{P}_n)\, ,\qquad
\sum_{\lambda\in {\mathcal{P}}_n}q_n(\lambda)=1\, ,$$ such that $$\label{eq:6}
q_n((n))<1\, ,\qquad n\geq 1\, .$$ Consider a family of probability distributions ${\mathsf{P}}^q_n,n\geq 1$ on ${\mathsf{T}}^\partial_n$ respectively, such that

1.  ${\mathsf{P}}^q_1$ is the law of the line-tree $\langle\bullet\rangle_G$, where $G$ has a geometric distribution given by $$\mathbb P(G=k)=q_1(\emptyset)(1-q_1(\emptyset))^{k}\, ,\qquad k\geq 0\, ,$$

2.  for $n\geq 2$, ${\mathsf{P}}^q_n$ is the law of $$\langle T^{(i)},1\leq i\leq 
      p(\Lambda)\rangle\, ,$$ where $\Lambda$ has distribution $q_n$, and conditionally on the latter, the trees $T^{(i)},1\leq i\leq
    p(\Lambda)$ are independent with distributions ${\mathsf{P}}^q_{\Lambda_i}$ respectively.

Alternatively, for $n\geq 2$, ${\mathsf{P}}^q_n$ is the law of $\langle T^{(i)},1\leq i\leq p(\Lambda)
\rangle_G$ where $G$ is independent of $\Lambda$ and geometric with $$\mathbb P(G=k)=(1-q_n((n)))q_n((n))^k\, ,\qquad k\geq 1\, ,$$ and conditionally on $\Lambda$ with law $q_n(\cdot\, |\,
{\mathcal{P}}_n\setminus\{(n)\})$, the trees $T^{(1)}, \ldots,T^{(p(\Lambda))}$ are independent with distributions ${\mathsf{P}}_{\Lambda_i}$ respectively. A simple induction argument shows that there exists a unique family ${\mathsf{P}}^q_n$ satisfying the properties 1 and 2 above.

A family of random trees $T_n, n\geq 1$ with respective distributions ${\mathsf{P}}^q_n, n \geq 1$ is called a Markov branching family. The law of the tree $T_n$ introduced in the beginning of the Introduction to describe the genealogy of splitting collections of $n$ balls is $ {\mathsf{P}}^q_n$.

### Markov branching trees with a prescribed number of vertices {#sec:mark-branch-trees-1}

We now consider the following variant of the above construction, in which the size of a tree ${\mathsf{t}}$ is the number of its vertices. For every $n\geq 1$, let again $q_n$ be a probability distribution on ${\mathcal{P}}_n$. We do not assume (\[eq:6\]), rather, we make the sole assumption that $q_1((1))=1$. For every $n\geq 1$, we construct inductively a family of random trees $T_n$ respectively in the set ${\mathsf{T}}_n$ of trees with $n$ vertices, by assuming that for $\lambda=(\lambda_1,\ldots, \lambda_p)\in {\mathcal{P}}_{n-1}$, with probability $q_{n-1}(\lambda)$, the $n-1$ vertices distinct from the root vertex are dispatched in $p$ subtrees with $\lambda_1\geq \ldots\geq
\lambda_p$ vertices, and that, given these sizes, the $p$ subtrees are independent with same distribution as $T_{\lambda_1},\ldots,T_{\lambda_p}$ respectively.

Formally,

1.  let ${\mathsf{Q}}^q_1$ be the law of $\bullet$, and

2.  for $n\geq 1$, let ${\mathsf{Q}}^q_{n+1}$ be the law of $$\langle T^{(i)},1\leq i\leq 
      p(\Lambda)\rangle\, ,$$ where $\Lambda$ has distribution $q_n$, and conditionally on the latter, the trees $T^{(i)},1\leq i\leq
    p(\Lambda)$ are independent with distributions ${\mathsf{Q}}^q_{\Lambda_i}$ respectively.

By induction, these two properties determine the laws ${\mathsf{Q}}_n^q,n\geq
1$ uniquely.

The construction is very similar to the previous one, and can in fact be seen as a special case, after a simple transformation on the tree; see Section \[proof-theor2\] below.

Topologies on metric spaces {#gh-topology}
---------------------------

The main goal of the present work is to study scaling limits of trees with distributions ${\mathsf{P}}^q_n, {\mathsf{Q}}^q_n$, as $n$ becomes large. For this purpose, we need to consider a topological "space of trees" in which such limits can be taken, and define the limiting objects.

A <span>*rooted*</span>[^4] metric space is a triple $(X,d,\rho)$, where $(X,d)$ is a metric space and $\rho\in X$ is a distinguished point, called the root. We say that two rooted spaces $(X,\rho,d),(X^{\prime},\rho^{\prime},d^{\prime})$ are isometry-equivalent if there exists a bijective isometry from $X$ onto $X$ that sends $\rho$ to $\rho'$.

A measured, rooted metric space is a 4-tuple $(X,d,\rho,\mu)$, where $(X,d,\rho)$ is a rooted metric space and $\mu$ is a Borel probability measure on $X$. Two measured, rooted spaces $(X,d,\rho,\mu)$ and $(X,d',\rho',\mu')$ are isometry-equivalent if there exists a root-preserving, bijective isometry $\phi$ from $(X,d,\rho)$ to $(X,d',\rho')$ such that the push-forward of $\mu$ by $\phi$ is $\mu'$. In the sequel we will almost always identify two isometry-equivalent (rooted, measured) spaces, and will often use the shorthand notation $X$ for the isometry class of a rooted space or a measured, rooted space, in a way that should be clear from the context. Also, if $X$ is such a space and $a>0$, then we denote by $aX$ the space in which the distance function is multiplied by $a$.

We denote by ${\mathscr{M}}$ the set of equivalence classes of compact rooted spaces, and by ${\mathscr{M}_{{\rm w}}}$ the set of equivalence classes of compact measured spaces. It is well-known (this is an easy extension of the results of @EPW) that ${\mathscr{M}}$ is a Polish space when endowed with the so-called pointed Gromov-Hausdorff distance $d_{\mathrm{GH}}$, where by definition the distance $d_{\mathrm{GH}}((X,\rho),(X^{\prime},\rho^{\prime}))$ is equal to the infimum of the quantities $${\mathrm{dist}}(\phi(\rho),\phi'(\rho'))\vee
{\mathrm{dist}}_{\mathrm{H}}(\phi(X),\phi'(X'))$$ where $\phi,\phi'$ are isometries from $X,X^{\prime}$ into a common metric space $(M,{\mathrm{dist}})$, and where ${\mathrm{dist}}_{\mathrm{H}}$ is the Hausdorff distance between compact subsets of $(M,{\mathrm{dist}})$. It is elementary that this distance does not depend on particular choices in the equivalence classes of $(X,\rho)$ and $(X^{\prime},\rho^{\prime})$. We endow ${\mathscr{M}}$ with the associated Borel $\sigma$-algebra. Of course, $d_{\mathrm{GH}}$ satisfies a homogeneity property, $d_{\mathrm{GH}}(aX,aX')=ad_{\mathrm{GH}}(X,X')$ for $a>0$.

We also need to define a distance on ${\mathscr{M}_{{\rm w}}}$, that is in some sense compatible with the Gromov-Hausdorff distance. Several complete distances can be constructed, and we use a variation of the Gromov-Hausdorff-Prokhorov distance used in @miermont09. The induced topology is the same as that introduced earlier in @EW. The reader should bear in mind that the topology used in the present paper involves a little extension of the two previous references, since we are interested in pointed spaces. We let $d_{\mathrm{GHP}}((X,d,\rho,\mu),(X',d',\rho',\mu'))$ be the infimum of the quantities $${\mathrm{dist}}(\phi(\rho),\phi'(\rho'))\vee
{\mathrm{dist}}_{\mathrm{H}}(\phi(X),\phi'(X'))\vee
{\mathrm{dist}}_{\mathrm{P}}(\phi_*\mu,\phi'_*\mu')\, ,$$ where again $\phi,\phi'$ are isometries from $X,X'$ into a common space $(M,{\mathrm{dist}})$, $\phi_*\mu,\phi'_*\mu'$ are the push-forward of $\mu,\mu'$ by $\phi,\phi'$, and ${\mathrm{dist}}_{\mathrm{P}}$ is the Prokhorov distance between Borel probability measures on $M$ @EK [Chapter 3]: $${\mathrm{dist}}_{\mathrm{P}}(m,m')=\inf\{{\varepsilon}>0:m(C)\leq
m'(C^{\varepsilon})+{\varepsilon}\mbox{ for every }C\subset M\mbox{ closed}\}\, ,$$ where $C^{\varepsilon}=\{x\in M:\inf_{y\in C}{\mathrm{dist}}(x,y)<{\varepsilon}\}$ is the ${\varepsilon}$-thickening of $C$. A simple adaptation of the results of @EW and Section 6 in @miermont09 (in order to take into account the particular role of the distinguished point $\rho$) shows that:

\[sec:r-trees-gromov-1\] The function $d_{\mathrm{GHP}}$ is a distance on ${\mathscr{M}_{{\rm w}}}$ that makes it complete and separable.

This distance is called the pointed Gromov-Hausdorff-Prokhorov distance. One must be careful that contrary to $d_{\mathrm{GH}}$, this distance is not homogeneous: $d_{\mathrm{GHP}}(aX,aX')$ is in general different from $ad_{\mathrm{GHP}}(X,X')$, because only the distances, not the measures, are multiplied in $aX,aX'$.

### Trees viewed as metric spaces {#sec:r-trees-gromov}

A plane tree ${\mathbbm{t}}$ can be naturally seen as a metric space by endowing ${\mathbbm{t}}$ with the <span>*graph distance*</span> between vertices. Namely, $$d_{\mathrm{gr}}(u,v)=|u|+|v|-2|u\wedge v|\, ,\qquad u,v\in {\mathbbm{t}}\, ,$$ where $u\wedge v$ is the longest prefix common to $u,v$. This coincides with the number of edges on the only simple path going from $u$ to $v$. The space $({\mathbbm{t}},d_{\mathrm{gr}})$ is naturally rooted at $\varnothing$. We can put two natural probability measures on ${\mathbbm{t}}$, the uniform measures on the leaves or on the vertices: $$\mu_{\partial{\mathbbm{t}}}=\frac{1}{\#\partial{\mathbbm{t}}}\sum_{u\in
  \partial{\mathbbm{t}}}\delta_{\{u\}}\, ,\qquad \mu_{\mathbbm{t}}=\frac{1}{\#{\mathbbm{t}}}\sum_{u\in
  {\mathbbm{t}}}\delta_{\{u\}}\, .$$ If ${\mathsf{t}}\in {\mathsf{T}}$ is a tree and ${\mathbbm{t}},{\mathbbm{t}}'$ are two plane representatives of ${\mathsf{t}}$, then it is elementary that the spaces $({\mathbbm{t}},d_{\mathrm{gr}},\varnothing,\mu_{\partial {\mathbbm{t}}})$ and $({\mathbbm{t}}',d_{\mathrm{gr}},\varnothing,\mu_{\partial{\mathbbm{t}}'})$ are isometry-equivalent rooted measured metric spaces. The same holds with $\mu_{{\mathbbm{t}}},\mu_{{\mathbbm{t}}'}$ instead of $\mu_{\partial{\mathbbm{t}}},\mu_
{\partial{\mathbbm{t}}'}$. We denote by $({\mathsf{t}},d_{\mathrm{gr}},\rho,\mu_{\partial{\mathsf{t}}})$ and $({\mathsf{t}},d_{\mathrm{gr}},\rho,\mu_{\mathsf{t}})$ the corresponding elements of ${\mathscr{M}_{{\rm w}}}$. Conversely, it is possible to recover uniquely the discrete tree (not a plane tree!) from the element of ${\mathscr{M}_{{\rm w}}}$ thus defined.

### ${\mathbb{R}}$-trees {#sec:r-trees}

An $\mathbb{R}$-tree is a metric space $(X,d)$ such that for every $
x,y\in X$,

1.  there is an isometry $\varphi_{x,y}:[0,d(x,y)]\to X$ such that $
    \varphi_{x,y}(0)=x$ and $\varphi_{x,y}(d(x,y))=y$, and

2.  for every continuous, injective function $c:[0,1]\to X$ with $c(0)=x,$ $c(1)=y$, one has $c([0,1])=\varphi_{x,y}([0,d(x,y)])$.

In other words, any two points in $X$ are linked by a geodesic path, which is the only simple path linking these points, up to reparameterisation. This is a continuous analogue of the graph-theoretic definition of a tree as a connected graph with no cycle. We denote by $[[x,y]]$ the range of $\varphi_{x,y}$.

We let ${\mathscr{T}}$ (resp. ${\mathscr{T}_{{\rm w}}}$) be the set of isometry classes of compact rooted ${\mathbb{R}}$-trees (resp. compact, rooted measured ${\mathbb{R}}$-trees). An important property is the following (these are easy variations on results by @EPW [@EW]).

\[sec:spaces-metric-spaces\] The spaces ${\mathscr{T}}$ and ${\mathscr{T}_{{\rm w}}}$ are closed subspaces of $({\mathscr{M}},d_{\mathrm{GH}})$ and $({\mathscr{M}_{{\rm w}}},d_{\mathrm{GHP}})$.

If ${\mathcal{T}}\in{\mathscr{T}}$ and for $x\in{\mathcal{T}}$, we call the quantity $d(\rho,x)$ the *height* of $x$. If $x,y\in{\mathcal{T}}$, we say that $x$ is an ancestor of $y$ whenever $x\in[{{[\rho,y]}}]$. We let $x\wedge y\in{\mathcal{T}}$ be the unique element of ${\mathcal{T}}$ such that $[[\rho,x]]\cap[{{[\rho,y]}}]
=[[\rho,x\wedge y]]$, and call it the highest common ancestor of $x$ and $y$ in ${\mathcal{T}}$. For $x\in{\mathcal{T}}$, we denote by ${\mathcal{T}}_x$ the set of $
y\in{\mathcal{T}}$ such that $x$ is an ancestor of $y$. The set ${\mathcal{T}}_x$, endowed with the restriction of the distance $d$, and rooted at $x$, is in turn a rooted $\mathbb{R}$-tree, called the subtree of ${\mathcal{T}}$ rooted at $x$. If $({\mathcal{T}},d,\rho,\mu)$ is an element of ${\mathscr{T}_{{\rm w}}}$ and $\mu({\mathcal{T}}_x)>0$, then ${\mathcal{T}}_x$ can be seen as an element of ${\mathscr{T}_{{\rm w}}}$ by endowing it with the measure $\mu(\cdot\cap {\mathcal{T}}_x)/\mu({\mathcal{T}}_x)$.

We say that $x\in{\mathcal{T}}$, $x\neq\rho$, in a rooted $\mathbb{R}$-tree is a *leaf* if its removal does not disconnect ${\mathcal{T}}$. Note that this always exclude the root from the set of leaves, which we denote by $\mathcal{L}({\mathcal{T}})$. A *branch point* is an element of ${\mathcal{T}}$ of the form $x\wedge y$ where $x$ is not an ancestor of $y$ nor vice-versa. It is also characterized by the fact that the removal of a branch point disconnects the $\mathbb{R}$-tree into three or more components (two or more for the root). We let $\mathcal{B}({\mathcal{T}})$ be the set of branch points of ${\mathcal{T}}$.

Self-similar fragmentations and associated ${\mathbb{R}}$-trees  {#sec:self-simil-fragm}
----------------------------------------------------------------

Self-similar fragmentation processes are continuous-time processes that describe the dislocation of a massive object as time passes. Introduce the set of partitions of a unit mass $${{\mathcal{S}^{\downarrow}}}:=\Big\{{\mathbf{s}}=(s_1,s_2,\ldots):s_1\geq s_2\geq \ldots\geq
0,\sum_{i\geq 1}s_i\leq 1\Big\}\, .$$ This space is endowed with the $\ell^1$-metric $d({\mathbf{s}},{\mathbf{s}}')=\sum_{i\geq 1}|s_i-s'_i|$, which makes it a compact space.

\[sec:self-simil-fragm-4\] A self-similar fragmentation is an ${{\mathcal{S}^{\downarrow}}}$-valued Markov process $({\mathbf{X}}(t),t\geq 0)$ which is continuous in probability and satisfies the following fragmentation property. For some $a\in {\mathbb{R}}$, called the self-similarity index, it holds that conditionally given ${\mathbf{X}}(t)=(s_1,s_2,\ldots)$, the process $({\mathbf{X}}(t+t'),t'\geq 0)$ has same distribution as the process whose value at time $t'$ is the decreasing rearrangement of the sequences $s_i{\mathbf{X}}^{(i)}(s_i^at'),i\geq
1$, where $({\mathbf{X}}^{(i)},i\geq 1)$ are i.i.d. copies of ${\mathbf{X}}$.

Bertoin @BertoinSSF and Berestycki @berest02 have shown that the laws of self-similar fragmentation processes are characterized by three parameters: the index $a$, a non-negative erosion coefficient, and a dislocation measure $\nu$ on ${{\mathcal{S}^{\downarrow}}}$. The idea is that every sub-object of the initial object, with mass $x$ say, will suddenly split into sub-sub-objects of masses $xs_1,xs_2,\ldots$ at rate $x^a\nu({\mathrm{d}}{\mathbf{s}})$, independently of the other sub-objects. Erosion accounts for the formation of zero-mass particles that are continuously ripped off the fragments.

For our concerns, we will consider only the special case where the erosion phenomenon has no role and the dislocation measure does not charge the set $\{{\mathbf{s}}\in
{{\mathcal{S}^{\downarrow}}}:\sum_is_i<1\}$. One says that $\nu$ is <span>*conservative*</span>. This motivates the following definition.

A <span>*dislocation measure*</span> is a $\sigma$-finite measure $\nu$ on ${{\mathcal{S}^{\downarrow}}}$ such that $\nu(\{(1,0,0,\ldots)\})=0$ and $$\label{eq:1}
  \nu\Big(\Big\{\sum_{i\geq 1}s_i<1\Big\}\Big)=0\, , \qquad \int_{{\mathcal{S}^{\downarrow}}}(1-s_1)\nu({\mathrm{d}}{\mathbf{s}})<\infty \, .$$ We say that the measure is <span>*binary*</span> when $\nu(\{s_1+s_2<1\})=0$. A binary measure is characterized by its image $\nu(s_1\in {\mathrm{d}}x)$ through the mapping ${\mathbf{s}}\mapsto s_1$.

A <span>*fragmentation pair*</span> is a pair $(a,\nu)$ where $a\in {\mathbb{R}}$ is called the self-similarity index, and $\nu$ is a dislocation measure.

Fragmentation pairs $(a,\nu)$ therefore characterize the distributions of the self-similar fragmentations we are focusing on. When $a=-\gamma<0$, small fragments tend to split faster, and it turns out that they all disappear in finite time, a property known as <span> *formation of dust*</span>. Using this property, it is shown in @HM04 how to construct a "continuum random tree" encoding the process with characteristic pair $(-\gamma,\nu)$. This tree is a random element of ${\mathscr{M}_{{\rm w}}}$, $${\mathcal{T}}_{\gamma,\nu}=({\mathcal{T}},d,\rho,\mu)\, ,$$ such that $({\mathcal{T}},d)$ is a random ${\mathbb{R}}$-tree, and such that almost-surely

1.  the measure $\mu$ is supported on the set ${\cal
      L}({\mathcal{T}})$ of leaves of ${\mathcal{T}}$

2.  $\mu$ has no atom,

3.  for every $x\in {\mathcal{T}}\setminus\mathcal{L}({\mathcal{T}})$, it holds that $\mu({\mathcal{T}}_x)>0$.

\[Theorem 1 and Proposition 1 in @HM04\] \[sec:self-simil-fragm-6\] The law of ${\mathcal{T}}_{\gamma,\nu}$ is characterized by properties <span>1, 2, 3</span> above, together with the fact that if $t\geq 0$ and ${\mathcal{T}}_{i}(t),i\geq
1$ are the connected components of the open set $\{x\in
{\mathcal{T}}:d(\rho,x)>t\}$, then the process $((\mu({\mathcal{T}}_{i}(t)),i\geq
1)^{\downarrow},t\geq 0)$ of the non-increasing rearrangement of the $\mu$-masses of these components has the same law as the ${{\mathcal{S}^{\downarrow}}}$-valued self-similar fragmentation with characteristic pair $(-\gamma,\nu)$.

The previous proposition is not really constructive, and we postpone a more detailed description of ${\mathcal{T}}_{\gamma,\nu}$ to Section \[sec:cont-fragm-trees\].

It was shown in @HM04 that one can recover the celebrated Brownian and stable continuum random trees @AldousCRTI [@LeGall/LeJan; @dlg02] as special instances of fragmentation trees. The parameters $\gamma$ and $\nu$ corresponding to these trees will be recalled when we discuss applications in Sections \[sec:appl-galt-wats\] and \[sec:appl-polya-trees\].

Main results {#sec:main-result}
------------

Let $(q_n(\lambda),\lambda\in {\mathcal{P}}_n),n\geq 1$ satisfy (\[eq:6\]). With it, we associate a finite non-negative measure ${\overline}{q}_n$ on ${{\mathcal{S}^{\downarrow}}}$, defined by its integral against measurable $f:{{\mathcal{S}^{\downarrow}}}\to {\mathbb{R}}_+$ as $${\overline}{q}_n(f)=\sum_{\lambda\in {\mathcal{P}}_n}q_n(\lambda)
f\Big(\frac{\lambda}{n}\Big)\, .$$ Note that in the left-hand side, we have identified $\lambda/n$ with an element of ${{\mathcal{S}^{\downarrow}}}$, in accordance with our convention that $\lambda$ is identified with the infinite sequence $(\lambda_i,i\geq 1)$. We make the following basic assumption.

> <span>**(H)**</span> There exists a fragmentation pair $(-\gamma,\nu)$, with $\gamma>0$, and a function $\ell:(0,\infty)\to (0,\infty)$ slowly varying at $\infty$, such that we have the weak convergence of finite non-negative measures on ${{\mathcal{S}^{\downarrow}}}$: $$\label{eq:3}
> n^\gamma\ell(n) (1-s_1){\overline}{q}_n({\mathrm{d}}{\mathbf{s}})
> \overset{(w)}{\underset{n\to\infty}{\longrightarrow}}
> (1-s_1)\nu({\mathrm{d}}{\mathbf{s}})\, .$$

\[sec:main-result-1\] Assume $q=(q_n(\lambda),\lambda\in {\mathcal{P}}_n),n\geq 1$ satisfies assumption <span> **(H)**</span>. Let $T_n$ have distribution ${\mathsf{P}}^q_n$, and view $T_n$ as a random element of ${\mathscr{M}_{{\rm w}}}$ by endowing it with the graph distance and the uniform probability measure $\mu_{\partial T_n}$ on $\partial
T_n$. Then we have the convergence in distribution $$\frac{1}{n^\gamma \ell(n)}T_n\underset{n\to\infty}{\overset{{(d)}}
  {\longrightarrow}}{\mathcal{T}}_{\gamma,\nu}\, ,$$ for the rooted Gromov-Hausdorff-Prokhorov topology.

There is a similar statement for the trees with laws ${\mathsf{Q}}^q_n$. Consider a family $(q_n(\lambda),\lambda\in {\mathcal{P}}_n),n\geq 1$ with $q_1((1))=1$.

\[sec:main-result-2\] Assume $q=(q_n(\lambda),\lambda\in {\mathcal{P}}_n),n\geq 1$ satisfies assumption <span>**(H)**</span>, with

-   either $\gamma\in(0,1)$, or

-   $\gamma=1$ and $\ell(n)\to 0$ as $n\to\infty$.

Let $T_n$ have distribution ${\mathsf{Q}}^q_n$. We view $T_n$ as a random element of ${\mathscr{M}_{{\rm w}}}$ by endowing it with the graph distance and the uniform probability measure $\mu_{T_n}$ on $T_n$. Then we have the convergence in distribution $$\frac{1}{n^\gamma \ell(n)}T_n\underset{n\to\infty}{\overset{{(d)}}
  {\longrightarrow}}{\mathcal{T}}_{\gamma,\nu}\, ,$$ for the rooted Gromov-Hausdorff-Prokhorov topology.

Theorem \[sec:main-result-2\] deals with a more restricted set of values of values of $\gamma$ than Theorem \[sec:main-result-1\]. This comes from the fact that, contrary to the set ${\mathsf{T}}^\partial_n$ which contains trees with arbitrary height, the set ${\mathsf{T}}_n$ of trees with $n$ vertices has elements with height at most $n-1$. Therefore, we cannot hope to find non-trivial limits in Theorem \[sec:main-result-2\] when $\gamma>1$, or when $\gamma=1$ and $\ell(n)$ has limit $+\infty$ as $n\to\infty$. The intermediate case where $\ell(n)$ admits finite non-zero limiting points cannot give such a convergence with a continuum fragmentation tree in the limit either. The reason being that the support of the height of a continuum fragmentation tree is unbounded, whereas the heights of $T_n/n \ell(n)$ are all bounded from above by $1/\inf_n(\ell(n))$, which is finite under our assumption.

Note that Theorem \[sec:main-result-1\] (resp. Theorem \[sec:main-result-2\]) implies that any fragmentation tree $\mathcal
T_{\gamma, \nu}$ is the continuous limit of a rescaled family of discrete Markov branching trees with a prescribed number of leaves (resp. with a prescribed number of vertices, provided $\gamma<1$), since we have the following approximation result.

\[Propexemple\] For every fragmentation pair $(-\gamma,\nu)$ with $\gamma>0$, there exists a family of distributions $(q_n,n \geq 1)$ satisfying (\[eq:6\]) and such that (\[eq:3\]) holds, with $\ell(x)=1$ for every $x>0$.

After some preliminaries gathered in Section \[secprelim\], we prove Theorems \[sec:main-result-1\] and \[sec:main-result-2\] and Proposition \[Propexemple\] in Section \[sec:proof-theor-refs\]. Before embarking in the proofs, we present in Section \[applications\] some important applications of these theorems to Galton-Watson trees, unordered random trees and particular families of Markov branching trees studied in earlier works. Of these applications, the first two actually involve a substantial amount of work, so that the details are postponed to Section \[sec:cond-galt-wats\] and \[SectionPolya\].

Applications
============

Galton-Watson trees {#sec:appl-galt-wats}
-------------------

A natural application is the study of Galton-Watson trees conditioned on their total number of vertices. Let $\xi$ be a probability measure on ${\mathbb{Z}}_+$ such that $\xi(0)>0$ and $$\label{eq:9}
\sum_{k\geq 0}k\xi(k)=1\, .$$ The law of the Galton-Watson tree with offspring distribution $\xi$ is the probability measure on the set of plane trees defined by $${\rm GW}_\xi(\{{\mathbbm{t}}\})=\prod_{u\in {\mathbbm{t}}}\xi(c_u({\mathbbm{t}}))\, ,$$ for ${\mathbbm{t}}$ a plane tree. That this does define a probability distribution on the set of plane trees comes from the fact that a Galton-Watson process with offspring distribution $\xi$ becomes a.s. extinct in finite time, due to the criticality condition (\[eq:9\]). In order to fit in the framework of this paper, we view ${\rm GW}_\xi$ as a distribution on the set of discrete, rooted trees, by taking its push-forward under the natural projection from plane trees to trees.

In order to avoid technicalities, we also assume that the support of $\xi$ generates the additive group ${\mathbb{Z}}$. This implies that $\mathrm{GW}_\xi(\{\#{\mathbbm{t}}= n\})>0$ for every $n$ large enough. For such $n$, we let ${\mathrm{GW}_\xi}^{(n)}={\mathrm{GW}_\xi}(\cdot\, |\, \{\#{\mathbbm{t}}= n\})$, and view it as a law on ${\mathsf{T}}_n$.

We distinguish two different regimes.

Case 1.

:   The offspring distribution has finite variance $$\sigma^2=\sum_{k\geq 0}k(k-1)\xi(k)<\infty\, .$$

Case 2.

:   For some $\alpha \in (1,2)$ and $c\in (0,\infty)$, it holds that $\xi(k)\sim ck^{-\alpha-1}$ as $k\to\infty$. In particular, $\xi$ is in the domain of attraction of a stable law of index $\alpha$.

The <span>*Brownian dislocation measure*</span> is the unique binary dislocation measure such that $$\nu_{2}(s_1\in {\mathrm{d}}x)=\sqrt{\frac{2}{\pi x^3(1-x)^3}}\, {\mathrm{d}}x\,
{\mathbf{1}}_{\{1/2\leq x< 1\}}\, .$$ Otherwise said, for every measurable $f:{{\mathcal{S}^{\downarrow}}}\to{\mathbb{R}}_+$, $$\int_{{\mathcal{S}^{\downarrow}}}\nu_2({\mathrm{d}}{\mathbf{s}})\,  f({\mathbf{s}})
=\int_{1/2}^1\sqrt{\frac{2}{\pi
    x^3(1-x)^3}}\, {\mathrm{d}}x\, f(x,1-x,0,0,\ldots)\, .$$ We also define a one-parameter family of measures in the following way. For $\alpha\in(1,2)$, let $\sum_{i\geq 1}\delta_{\Delta_i}$ be a Poisson random measure on $(0,\infty)$ with intensity measure $$\frac{1}{\alpha\Gamma\big(1-\frac{1}{\alpha}\big)}\frac{{\mathrm{d}}x}{x^{1+1/\alpha}}{\mathbf{1}}_{\{x>0\}}\, ,$$ with the atoms $\Delta_i,i\geq 1$ labeled in such a way that $\Delta_1\geq
\Delta_2\geq \ldots$. Let $T=\sum_{i\geq 1}\Delta_i$, which is finite a.s. by standard properties of Poisson measures. In fact, $T$ follows a stable distribution with index $1/\alpha$, with Laplace transform $$\mathbb{E}[\exp(-\lambda T)]=\exp(-\lambda^{1/\alpha})\, ,\qquad
\lambda \geq 0\, .$$ It can be seen as a stable subordinator evaluated at time $1$, its jumps up to this time being the atoms $\Delta_i,i\geq
1$). The measure $\nu_\alpha$ is defined by its action against a measurable function $f:{{\mathcal{S}^{\downarrow}}}\to {\mathbb{R}}_+$: $$\int_{{\mathcal{S}^{\downarrow}}}\nu_\alpha({\mathrm{d}}{\mathbf{s}})\,
f({\mathbf{s}})=\frac{\alpha^2\Gamma(2-1/\alpha)}{ \Gamma(2-\alpha)} \mathbb E\bigg[T\,
  f\Big(\frac{\Delta_i}{T},i\geq 1\Big)\bigg]\, .$$ Because $\mathbb E[T]=\infty$, this formula defines an infinite $\sigma$-finite measure on ${{\mathcal{S}^{\downarrow}}}$, which turns out to satisfy (\[eq:1\]).

\[sec:main-results-1\] Let $\xi$ satisfy (\[eq:9\]), with support that generates the additive group ${\mathbb{Z}}$. Let $T_n$ be a random element of ${\mathsf{T}}_n$ with distribution ${\mathrm{GW}_\xi}^{(n)}$. Consider $T_n$ as an element of ${\mathscr{M}_{{\rm w}}}$ by endowing it with the graph distance and the uniform probability measure $\mu_{T_n}$ on $T_n$. Then we have, in distribution for the Gromov-Hausdorff-Prokhorov topology, $$\begin{aligned}
{\bf Case\ 1:} &\qquad &
\frac{1}{\sqrt{n}}T_n\underset{n\to\infty}{\overset{(d)}{
    \longrightarrow}}\frac{2}{\sigma}{\mathcal{T}}_{1/2,\nu_2}\, , \\ {\bf
  Case\ 2:}& \qquad &
\frac{1}{n^{1-1/\alpha}}T_n\underset{n\to\infty}{\overset{(d)}{
    \longrightarrow}}\left(\frac{\alpha(\alpha-1)}{c\Gamma(2-\alpha)}
\right)^{1/\alpha}{\mathcal{T}}_{1-1/\alpha,\nu_\alpha}\, .\end{aligned}$$

This result will be proved in Section \[sec:cond-galt-wats\] below, by first showing that ${\mathrm{GW}_\xi}^{(n)}$ is of the form ${\mathsf{Q}}^q_n$ for some appropriate choice of $q$.

The trees ${\mathcal{T}}_{1/2,\nu_2}$ and ${\mathcal{T}}_{1-1/\alpha,\nu_\alpha}$ appearing in the limit are important models of continuum random trees, called respectively the Brownian Continuum Random Tree and the stable tree with index $\alpha$. The Brownian tree is somehow the archetype in the theory of scaling limits of trees. The above theorem is very similar to a result due to Duquesne @duq02, but our method of proof is totally different. While @duq02 relies on quite refined aspects of Galton-Watson trees and their encodings by stochastic processes, our approach requires only to have some kind of global structure, namely the Markov branching property, and to know how mass is spread in one generation. We do not claim that our method is more powerful than the one used in @duq02 (as a matter of fact, the limit theorem of @duq02 holds in the more general case where $\mu$ is in the domain of attraction of a totally asymmetric stable law with index $\alpha\in (1,2]$). However, our method has some robustness, allowing to shift from Galton-Watson trees to other models of trees. Our next example will try to illustrate this.

Uniform unordered trees {#sec:appl-polya-trees}
-----------------------

Our next application is on a different model of random trees, which is by nature not a model of plane or labelled trees, contrary to the previous examples. It is actually not either a Markov branching model, but is very close from being one, as we will see.

For $2\leq m\leq \infty$, we consider the set ${\mathsf{T}}^{(m)}_n\subset
{\mathsf{T}}_n$ of trees with $n$ vertices, in which every vertex has at most $m$ children. In particular, we have ${\mathsf{T}}^{(\infty)}_n={\mathsf{T}}_n$. The sets ${\mathsf{T}}_n^{(m)}$ are harder to enumerate than sets of ordered or labeled trees, like plane trees or Cayley trees, and there is no closed expression for the numbers $\#{\mathsf{T}}^{(m)}_n$. However, Otter @otter48 (see also @FlSe09 [Section VII.5]) derived the asymptotic enumeration result $$\label{eq:18}
\#{\mathsf{T}}^{(m)}_n\underset{n\to\infty}{\sim} \kappa_m\frac{(\rho_m)^n}{n^{3/2}}\, ,$$ for some $m$-dependent constants $\kappa_m>0,\rho_m>1$. This can be achieved by studying the generating function $$\psi^{(m)}(x)=\sum_{n\geq 1} \#{\mathsf{T}}^{(m)}_n\, x^n\, ,$$ which has a square-root singularity at the point $1/\rho_m$. The behavior (\[eq:18\]) indicates that a uniformly chosen element of ${\mathsf{T}}^{(m)}_n$ should converge as $n\to\infty$, once renormalized suitably, to the Brownian continuum random tree. We show that this is indeed the case for any value of $m$. To state our result, let $${\widetilde}{{\mathsf{T}}}_n^{(m)}=\{{\mathsf{t}}\in {\mathsf{T}}_n^{(m)}:c_\varnothing({\mathsf{t}})\leq
 m-2\}\, .$$ For instance, ${\widetilde}{{\mathsf{T}}}_n^{(2)}=\emptyset$ for $n \geq
 2$, while ${\widetilde}{{\mathsf{T}}}^{(\infty)}_n={\mathsf{T}}^{(\infty)}_n$ for all $n$. Let $${\widetilde}{\psi}^{(m)}(x)=\sum_{n\geq 1}\#{\widetilde}{{\mathsf{T}}}^{(m)}_n\, x^n\, ,$$ and define a finite constant $c_m$ by $$c_m=\frac{\sqrt{2}}{\sqrt{\pi}\kappa_m{\widetilde}{\psi}^{(m)} (1/\rho_m)}\,
 .$$ Note that ${\widetilde}{\psi}^{(2)}(x)=x$ for every $x$, while ${\widetilde}{\psi}^{(\infty)}(1/\rho_\infty)=1$ @FlSe09 [Section VII.5]. Therefore, we get $$c_2=\frac{\sqrt{2}\rho_2}{\sqrt{\pi}\kappa_2}\, ,\qquad
 c_\infty=\frac{\sqrt{2}}{\sqrt{\pi}\kappa_\infty}\, .$$

\[sec:main-results-2\] Fix $m\in \{2,3,\ldots\}\cup \{\infty\}$. Let $T_n$ be uniformly distributed in ${\mathsf{T}}^{(m)}_n$. We view $T_n$ as an element of ${\mathscr{M}_{{\rm w}}}$ by endowing it with the measure $\mu_{T_n}$, then $$\frac{1}{\sqrt{n}}T_n\underset{n\to\infty}{\overset{(d)}{
    \longrightarrow}}c_m{\mathcal{T}}_{1/2,\nu_2}\, .$$

The proof of this result is given in Section \[SectionPolya\]. We note that this implies a similar, maybe more natural, statement for $m$-ary trees. We say that ${\mathsf{t}}\in {\mathsf{T}}$ is $m$-ary if every vertex has either $m$ children or no child, and we say that the vertex is internal in the first case, i.e. when it is not a leaf. Summing over the degrees of vertices in an $m$-ary tree with $n$ internal vertices, we obtain that $\#{\mathsf{t}}=mn+1$, and $\#\partial{\mathsf{t}}=(m-1)n+1$.

Assume now that $m<\infty$. Starting from an $m$-ary tree ${\mathsf{t}}$ with $n$ internal vertices, and removing the leaves — equivalently, keeping only the internal vertices — gives an element $\phi({\mathsf{t}})\in{\mathsf{T}}^{(m)}_n$. The mapping $\phi$ is inverted by attaching $m-k$ leaves to each vertex with $k$ children, for an element of ${\mathsf{T}}^{(m)}_n$. Moreover, we leave as an easy exercise that $d_{\mathrm{GHP}}(a{\mathsf{t}},a\phi({\mathsf{t}}))\leq a$ for every $a>0$, when the trees are endowed with the uniform measures $\mu_{\mathsf{t}},\mu_{\phi({\mathsf{t}})}$ on vertices. Theorem \[sec:main-results-2\] thus implies:

\[sec:unif-unord-trees\] Let $m\in \{2,3,\ldots,\}$ and $T_n^{[m]}$ be a uniform $m$-ary tree with $n$ internal vertices, endowed with the measure $\mu_{T_n^{[m]}}$. Then $$\frac{1}{\sqrt{n}}T^{[m]}_n\underset{n\to\infty}{
  \overset{(d)}{\longrightarrow} }c_m{\mathcal{T}}_{1/2,\nu_2}\, .$$

The problem of scaling limits of random rooted unlabeled trees has attracted some attention in the recent literature, see @BrFl08 [@MaMi09; @DrGi10]. For $m=2$, Corollary \[sec:unif-unord-trees\] readily yields the main theorem of @MaMi09, which was derived using a completely different method. Indeed, it is based in a stronger way on combinatorial aspects of ${\mathsf{T}}^{(2)}_n$. Here, we really make use of a fragmentation property satisfied by the laws ${\mathsf{P}}_n^{(m)}$. As alluded to at the begining of this section, these are not actually laws of Markov branching trees. Nevertheless, they can be coupled with laws of Markov branching trees in a way that the coupled trees are close in the $d_{\mathrm{GHP}}$ metric. In the general case $m\neq 2$, Theorem \[sec:main-results-2\] and Corollary \[sec:unif-unord-trees\] are new, and were implicitly conjectured by Aldous @AldousCRTII. In @DrGi10, the authors prove a result on the scaling limit of the so-called profile of the uniform tree for $m=\infty$, which is related to our results, although it is not a direct consequence. Finally, we note that the problem of the scaling limit of <span>*unrooted*</span> unordered trees is still open, although we expect the Brownian tree to arise again as the limiting object.

Consistent Markov branching models {#sec:appl-cons-models}
----------------------------------

Considering again in a more specific way the Markov branching models, we stress that Theorem \[sec:main-result-1\] also encompasses the results of @HMPW06, which hold for particular families $(q_n,n\geq 1)$ satisfying a further consistency property. In this setting, it is assumed that $q_n((n))=0$ for every $n\geq 1$, so that the trees $T_n$ do not have any vertex having only one child. The consistency property can be formulated as follows:

> <span>**Consistency property.** </span>Starting from $T_n$ with $n\geq 2$, select one of the leaves uniformly at random, and remove this leaf as well as the edge that is attached to it. If this removal creates a vertex with only one child, then remove this vertex and merge the two edges incident to this vertex into one. Then the random tree thus constructed has same distribution as $T_{n-1}$.

A complete characterization of families $(q_n,n\geq 1)$ giving rise to Markov branching trees with this consistency property is given in @HMPW06. Namely, such families can be constructed in terms of a pair $(c,\nu)$, which is uniquely defined up to multiplication by a common positive constant, such that $c\geq 0$ is an "erosion coefficient" and $\nu$ is a dislocation measure as described above (except that $\nu(\sum s_i<1)=0$ is not required). The cases where $c=0$ and $\nu(\sum s_i<1)=0$ are the most interesting ones, so we will assume henceforth that this is the case. The associated distributions $q_n,n\geq 2$ are given by the following explicit formula: for $\lambda\in {\mathcal{P}}_n$ having $p\geq 2$ parts, $$\label{eq:7}
q_n(\lambda)=\frac{1}{Z_n}C_\lambda\int_{{{\mathcal{S}^{\downarrow}}}}\nu({\mathrm{d}}{\mathbf{s}})
\sum_{\substack{i_1,\ldots,i_p\geq 1\\{\rm
      distinct}}}\prod_{j=1}^ps_{i_j}^{\lambda_j}\, ,$$ where $$C_\lambda=\frac{n!}{\prod_{i\geq 1}\lambda_i !\prod_{j\geq
    1}m_j(\lambda)!}$$ is a combinatorial factor, the same that appears in the statement of Lemma \[sec:partitions-1\] below, and $Z_n$ is a normalizing constant defined by $$Z_n=\int_{{{\mathcal{S}^{\downarrow}}}}\nu({\mathrm{d}}{\mathbf{s}})\Big(1-\sum_{i\geq 1}s_i^n\Big)\, .$$ Assume further that $\nu$ satisfies the following regularity condition: $$\label{eq:8}
\nu(s_1\leq 1-{\varepsilon})={\varepsilon}^{-\gamma}\ell(1/{\varepsilon})\, ,$$ where $\gamma \in (0,1)$ and $\ell$ is a function that is slowly varying at $\infty$. Then

\[sec:main-results\] If $\nu$ is a dislocation measure satisfying (\[eq:1\]) and (\[eq:8\]), and if $(q_n,n\geq 1)$ is the consistent family of probability measures defined by (\[eq:7\]), then the Markov branching trees $T_n$, viewed as random measured ${\mathbb{R}}$-trees by endowing the set of their leaves with the uniform probability measures, satisfies $$\frac{1}{\Gamma(1-\gamma)n^\gamma
  \ell(n)}T_n\underset{n\to\infty}{\overset{(d)}{\longrightarrow}}
{\mathcal{T}}_{\gamma_\nu,\nu}\, ,$$ for the Gromov-Hausdorff-Prokhorov topology.

This theorem is in some sense more powerful than @HMPW06 [Theorem 2], because the latter result needed one extra technical hypothesis that is discarded here. Moreover, our result holds for the Gromov-Hausdorff-Prokhorov topology, which is stronger than the Gromov-Hausdorff topology considered in @HMPW06. However, the setting of @HMPW06 also provided a natural coupling of the trees $T_n,n\geq 1$ and ${\mathcal{T}}_{\gamma_\nu,\nu}$ on the same probability space, for which the convergence in Theorem \[sec:main-results\] can be strengthened to a convergence in probability. This coupling is not provided in our case.

**Proof.** Let $\mathbf s \in \mathcal S^{\downarrow}$ be such that $\sum_{i \geq 1} s_i=1$. Let $K_1,\ldots,K_n$ be i.i.d. random variables in ${\mathbb{N}}$ such that ${\mathbb{P}}(K_1=i)=s_i$ for every $i
\geq 1$. Call $ \Lambda^{(i)}(n)$ the number of variables $K_j$ equal to $i$, and let $\Lambda^{(\mathbf
  s)}(n)=\left(\Lambda^{(1)}(n),\Lambda^{(2)}(n),\ldots\right)^{\downarrow}$ , where $\mathbf{x}^\downarrow$ denotes the decreasing rearrangement of the non-negative sequence $\mathbf{x}=(x_1,x_2,\ldots)$ with finite sum. It is not hard to see that the probability distributions $q_n$ defined by (\[eq:7\]) are also given, for $\lambda \neq (n)$, by $$q_n(\lambda)=\frac{1}{Z_n}\int_{\mathcal S^{\downarrow}} \mathbb
P(\Lambda^{(\mathbf s)}(n)= \lambda) \nu(\mathrm d \mathbf s ).$$ See for example the forthcoming Lemma \[sec:partitions-1\] in Section \[sec:discrete-model\]. The normalizing constant $Z_n$ is regularly varying, according to the assumption of regular variation (\[eq:8\]). Indeed, by Karamata's Tauberian Theorem (see @BGT [Th. 1.7.1']), we have that $$Z_n=\int_{\mathcal S^{\downarrow}}\left(1-\sum_{i \geq
  1}s_i^n\right)\nu(\mathrm d \mathbf s) \underset{n \rightarrow
  \infty }\sim \int_{\mathcal S^{\downarrow}}(1-s_1^n)\nu(\mathrm d
\mathbf s) \underset{n \rightarrow \infty }\sim
\Gamma(1-\gamma)\nu(s_1 \leq
1-1/n)=\Gamma(1-\gamma)n^{\gamma}\ell(n).$$ Now, to get a convergence of the form (\[eq:3\]), note that for all continuous functions $f :
\mathcal S^{\downarrow} \rightarrow \mathbb R_+$, $$\begin{aligned}
Z_n \sum_{\lambda \in \mathcal P_n} q_n(\lambda) \left(1-\frac{\lambda_1}
     {n}\right) f\left( \frac{\lambda}{n}\right) &=& \int_{\mathcal
       S^{\downarrow}}     \nu(\mathrm d \mathbf s) \mathbb E\left [ \left
       (1-\frac{\Lambda^{(\mathbf s)}_1(n)}{n}
       \right)f\left(\frac{\Lambda^{(\mathbf s)}(n)}{n} \right) \right]
\\ & \underset{ n \rightarrow \infty}\rightarrow& \int_{\mathcal
  S^{\downarrow}}\nu(\mathrm d \mathbf s) (1-s_1)f(\mathbf s)\, ,\end{aligned}$$ which follows by dominated convergence, since $f$ is bounded (say by $K$) on the compact space $\mathcal S^{\downarrow}$ and $$\mathbb
E\left[ \left(1-\frac{\Lambda^{(\mathbf s)}_1(n)}{n} \right)
  f\left(\frac{\Lambda^{(\mathbf s)}(n)} {n} \right) \right] \leq
K\mathbb E\left [1-\frac{\Lambda^{(\mathbf s)}_1(n)}{n} \right] \leq
K\mathbb E\left [1-\frac {\Lambda^{(1)}(n)}{n} \right] =K(1-s_1)\, .$$ We conclude by applying Theorem \[sec:main-result-1\].

Further non-consistent cases: $(\alpha,\theta)$-trees {#sec:some-natural-non}
-----------------------------------------------------

Another application concerns a family of binary labeled trees introduced by Pitman and Winkel @PiWi08 and built inductively according to a growth rule depending on two parameters $ \alpha \in
(0,1)$ and $\theta \geq 0$. Roughly, at each step, given that the tree $T_n^{\alpha,\theta, \mathrm {lab}}$ with $n$ leaves branches at the branch point adjacent to the root into two subtrees with $k\geq 1$ leaves for the subtree containing the smallest label in $T_n^{\alpha,\theta, \mathrm {lab}}$ and $n-k \geq 1$ leaves for the other one, a weight $ \alpha$ is assigned to the root edge and weights $k-\alpha$ and $n-k-1+\theta$ are assigned respectively to the trees with sizes $k$, $n-k$. Then choose either the root edge or one of the two subtrees according with probabilities proportional to these weights. If a subtree with two or more leaves is selected, apply this weighting procedure inductively to this subtree until the root edge or a subtree with a single leaf is selected. If a subtree with single leaf is selected, insert a new edge and leaf at the unique edge of this subtree. Similarly, if the root edge is selected, add a new edge and leaf to this root edge. We denote by $T_n^{\alpha,\theta}$ the tree $T_n^{\alpha,\theta, \mathrm {lab}}$ without labels.

Pitman and Winkel show that the family $(T_n^{\alpha,\theta}, n\geq
1)$ is not consistent in general (@PiWi08 [Proposition 1]), except when $\theta=1-\alpha$ or $\theta=2- \alpha$, and has the Markov branching property (@PiWi08 [Proposition 11]) with the following probabilities $q_n$:

1.  $q_n\left((k,n-k,0,\ldots) \right) =
      q_{\alpha,\theta}(n-1,k)+q_{\alpha,\theta}(n-1,n-k), \quad$ for $n-k<k \leq n-1$

2.  $ q_n \left(n/2,n/2 \right)=
      q_{\alpha,\theta}(n-1,n/2) $,

where $$q_{\alpha,\theta}(n,k)= \binom{n}{k} \frac{ \alpha (n-k) +\theta k }{n}
\frac{\Gamma(k-\alpha)\Gamma(n-k+\theta)}{\Gamma(1-\alpha)\Gamma(n+\theta)},
\quad 1 \leq k \leq n.$$ Now consider the binary measure $\nu_{\alpha,\theta}$ defined on $\mathcal S^{\downarrow}$ by $\nu_{\alpha,\theta}(s_1+s_2<1)=0$ and $\nu_{\alpha,\theta}(s_1 \in
\mathrm dx)=f_{\alpha,\theta}(x) \mathrm dx$ where $f_
        {\alpha,\theta}$ is defined on $[1/2,1)$ by $$f_{\alpha,\theta}(x)=\frac{1}{\Gamma(1-\alpha)}\left( \left( \alpha
        \left(1-x \right) + \theta x \right) x^{-
          \alpha-1}(1-x)^{\theta-1} + \left( \alpha x + \theta (1-x)
        \right) (1-x)^{-\alpha-1}x^{\theta-1}\right).$$

Endow, as usual, $T_n^{\alpha,\theta}$ with the uniform probability measure on $\partial T_n^{\alpha,\theta}$. Then, $$\frac{1}{n^{\alpha}}T_n^{\alpha,\theta} \overset{(d)}
{\underset{n\rightarrow \infty} \rightarrow} \mathcal
T_{\alpha,\nu_{\alpha,\theta}}$$ for the rooted Gromov-Hausdorff-Prokhorov topology.

This result reinforces Proposition 2 of @PiWi08 which states the a.s. convergence of $T_n^{\alpha,\theta} $, in a certain finite dimensional sense, to a continuum fragmentation tree with parameters $\alpha,
  \nu_{\alpha,\theta}$. In view of Theorem \[sec:main-result-1\], it suffices to check that hypothesis <span>**(H)**</span> holds, which in the present case states that for any $f:{{\mathcal{S}^{\downarrow}}}\to {\mathbb{R}}$ continuous and bounded with $|f({\mathbf{s}})|\leq(1-s_1)$, $$n^{\alpha}\sum_{k=\lceil n/2 \rceil}^{n-1} f
\left(\frac{k}{n},\frac{n-k}{n},0,\ldots \right) q_n\left((k,n-k,0,\ldots)
\right) \rightarrow \int_{1/2}^1 f(x,1-x,0,\ldots)
f_{\alpha,\theta}(x)\mathrm dx\, .$$ To prove this, we use that $\int_0^1 x^{a-1}(1-x)^{b-1} \mathrm dx = \Gamma(a) \Gamma
(b)/\Gamma(a+b)$, and rewrite $q_{\alpha,\theta}(n-1,k)$ as $$q_{\alpha,\theta}(n-1,k)=\binom{n-1}{k}  \frac{\alpha \left(n-1-k\right)
+ \theta k}{n-1}
\frac{\Gamma(n-1+\theta-\alpha)}{\Gamma(1-\alpha)\Gamma
  (n-1+\theta)} \int_0^1 x^{k-\alpha-1}(1-x)^{n-k+\theta-2} \mathrm
dx.$$ Then set for $x \in [0,1]$, $$F(x):=f(x, 1-x,0,\ldots) \mathbf
1_{\{x > 1/2\}} +f(1-x, x,0,\ldots) \mathbf 1_{\{x \leq 1/2\}}$$ and note that $F(0)=0$ and $|F(x) |\leq (1-x) \wedge x$, for every $x \in
[0,1]$. We have, $$\begin{aligned}
&&\sum_{k=\lceil n/2 \rceil}^{n-1} f
  \left(\frac{k}{n},\frac{n-k}{n},0,\ldots \right) q_n\left((k,n-k,0,\ldots)
  \right)= \sum_{k=0}^{n-1} F \left(\frac{k}{n}\right)
  q_{\alpha,\theta}(n-1,k) \\ &=&
  \frac{\Gamma(n-1+\theta-\alpha)}{\Gamma(1-\alpha)\Gamma(n-1+\theta)}
  \int_0^1 \sum_ {k=0}^{n-1} \binom{n-1}{k}  \frac{ \alpha \left(n-1-k\right)
  +  \theta k}{n-1}  F \left(\frac{k}{n} \right)
  x^{k-\alpha-1}(1-x)^{n-k+\theta-2} \mathrm dx \\ &=&
  \frac{\Gamma(n-1+\theta-\alpha)}{\Gamma(1-\alpha)\Gamma(n-1+\theta)}
  \int_0^1 \mathbb E \left[ \left( \alpha
    \left(1-\frac{B_{n-1}^{(x)}}{n-1} \right)+ \theta \frac{  B_{n-1}^{(x)}}{n-1}
    \right) F \left(\frac {B_{n-1}^{(x)}}{n} \right)\right]
  x^{-\alpha-1}(1-x)^{\theta-1} \mathrm dx,\end{aligned}$$ where $B_{n-1}^{(x)}$ denotes a binomial random variable with parameters $(n-1, x)$. We can assume that $B_{n-1}^{(x)}/n \rightarrow
x$ a.s. on the probability space $(\Omega,{\mathcal{F}},{\mathbb{P}})$, and since $F$ is continuous and bounded on $[0,1]$, we have $$\mathbb E \left[ \left( \alpha \left(1-\frac{B_{n-1}^{(x)}}{n-1}
  \right)+\theta \frac{B_{n-1}^{(x)}}{n-1} \right) F
  \left(\frac{B_{n-1}^{(x)}}{n} \right)\right] \rightarrow \left( \alpha
\left(1-x \right) + \theta x \right) F(x)\, , \quad \mbox{ for every
}x \in [0,1].$$ Moreover, $$\begin{aligned}
\label{eqexp}
 \lefteqn{  \mathbb E \left[ \left( \alpha \left(1-\frac{B_{n-1}^{(x)}}{n-1}
   \right)+\theta \frac{B_{n-1}^{(x)}}{n-1} \right) F
   \left(\frac{B_{n-1}^{(x)}}{n} \right)\right]} \\
   &\leq& \left(\left(\alpha + \theta
 \right) \mathbb E \left[ \frac{B_{n-1}^{(x)}}{n} \right] \right) \wedge \left(\alpha \mathbb E \left[
  1-\frac{B_{n-1}^{(x)}}{n-1}\right]  + \theta \mathbb E \left[\frac{B_{n-1}^{(x)}}{n-1} \right] \right) \\
&\leq & \left(\left(\alpha +
 \theta \right)x \right) \wedge \left( \alpha (1-x) + \theta x\right).\end{aligned}$$ This is enough to conclude by dominated convergence that $$\begin{aligned}
\lefteqn{\!\!\!\!\!\!\!\!\!\!\!\!\int_0^1 \mathbb E \left[ \left( \alpha
    \left(1-\frac{B_{n-1}^{(x)}}{n-1} \right)+\theta \frac{B_{n-1}^{(x)}}
         {n-1} \right) F \left(\frac{B_{n-1}^{(x)}}{n} \right)\right]
  x^{-\alpha-1}(1-x)^{\theta-1} {\mathrm{d}}x} \\ &\underset{n \rightarrow
  \infty} \longrightarrow& \int_0^1 \left( \alpha \left(1-x \right) +
\theta x \right) F (x)x^{-\alpha-1}(1-x)^{\theta-1} \mathrm dx\\ &=&
\Gamma(1-\alpha) \int_{1/2}^1 f(x,1-x,\ldots) f_{\alpha,
  \theta}(x)\mathrm dx.\end{aligned}$$ Last, Stirling's formula implies that $$\frac{\Gamma(n-1+\theta-\alpha)}{\Gamma(n-1+\theta)} \underset{n
  \rightarrow \infty} \sim n^{- \alpha},$$ as wanted.

Preliminaries on self-similar fragmentations and trees {#secprelim}
======================================================

Partition-valued self-similar fragmentations {#sec:sett-prel}
--------------------------------------------

In this section, we recall the aspects of the theory of self-similar fragmentations that will be needed to prove Theorems \[sec:main-result-1\] and \[sec:main-result-2\]. We refer the reader to @BertoinBook for more details.

### Partitions of sets of integers {#sec:partitions}

Let $B\subset {\mathbb{N}}$ be a possibly infinite, nonempty subset of the integers, and $\pi=\{\pi_1,\pi_2,\ldots\}$ be a partition of $B$. The (nonempty) sets $\pi_1,\pi_2,\ldots$ are called the <span>*blocks*</span> of $\pi$, we denote their number by $b(\pi)$. In order to lift the ambiguity in the labeling of the blocks, we will use, unless otherwise specified, the convention that $\pi_i,i\geq 1$ is defined inductively as follows: $\pi_i$ is the block of $\pi$ that contains the least integer of the set $$B\setminus\bigcup_{j=1}^{i-1}\pi_j\, ,$$ if the latter is not empty. For $i\in B$, we also let $\pi_{(i)}$ be the block of $\pi$ that contains $i$.

We let ${\mathcal{P}}_B$ be the set of partitions of $B$. This forms a partially ordered set, where we let $\pi \preceq \pi'$ if the blocks of $\pi'$ are all included in blocks of $\pi$ (we also say that $\pi'$ is finer than $\pi$). The minimal element is $\mathbbm{O}_B=\{B\}$, and the maximal element is $\mathbbm{I}_B=\{\{i\}:i\in B\}$.

If $B'\subseteq B$ is nonempty, the restriction of $\pi$ to $B'$, denoted by $\pi|_{B'}$ or $B'\cap \pi$ with a slight abuse of notations, is the element of ${\mathcal{P}}_{B'}$ whose blocks are the non-empty elements of $\{B'\cap \pi_1,B'\cap \pi_2,\ldots\}$.

If $B\subset {\mathbb{N}}$ is finite, with say $n$ elements, then any partition $\pi\in {\mathcal{P}}_B$ with $b$ blocks induces an element $\lambda(\pi)\in
{\mathcal{P}}_n$ with $b$ parts, given by the non-increasing rearrangement of the sequence $(\#\pi_1,\ldots,\#\pi_b)$.

A subset $B\subset {\mathbb{N}}$ is said to admit an asymptotic frequency if the limit $$\lim_{n\to\infty}\frac{\#\left(B\cap [n]\right)}{n}$$ exists. It is then denoted by $|B|$. It is a well-known fact, due to Kingman, that if $\pi$ is a random partition of ${\mathbb{N}}$ with distribution invariant under the action of permutations (simply called exchangeable partition), then a.s. every block of $\pi$ admits an asymptotic frequency. The law of $\pi$ is then given by the paintbox construction of next section, for some probability measure $\nu$. We let $|\pi|^{\downarrow}\in {{\mathcal{S}^{\downarrow}}}$ be the non-increasing rearrangement of the sequence $(|\pi_i|,i\geq 1)$. The exchangeable partition $\pi$ is called <span> *proper*</span> if $\sum_{i=1}^{b(\pi)}|\pi_i|=1$, which is equivalent to the fact that $\pi$ has a.s. no singleton blocks.

### Paintbox construction {#sec:paintb-constr}

Let $\nu$ be a dislocation measure, as defined around (\[eq:1\]). We construct a $\sigma$-finite measure on ${\mathcal{P}}_{\mathbb{N}}$ by the so-called <span> *paintbox construction*</span>. Namely, for every ${\mathbf{s}}\in {{\mathcal{S}^{\downarrow}}}$ with $\sum_{i\geq 1}s_i=1$, consider an i.i.d. sequence $(K_i,i\geq 1)$ such that $$\mathbb P(K_1=k)=s_k\, ,\qquad k\geq 1\, .$$ Then the partition $\pi$ such that $i,j$ are in the same block of $\pi$ if and only if $K_i=K_j$ is exchangeable. We denote by $\rho_{\mathbf{s}}({\mathrm{d}}\pi)$ its law. Note that $\rho_{\mathbf{s}}({\mathrm{d}}\pi)$-a.s., it holds that $|\pi|^{\downarrow}={\mathbf{s}}$, and $\pi$ is a.s. proper under $\rho_{\mathbf{s}}$ if and only if ${\mathbf{s}}$ sums to $1$. The measure $$\kappa_\nu({\mathrm{d}}\pi):=\int_{{{\mathcal{S}^{\downarrow}}}}\nu(\mathrm d {\mathbf{s}})\rho_{\mathbf{s}}({\mathrm{d}}\pi)$$ is a $\sigma$-finite measure on ${\mathcal{P}}_{\mathbb{N}}$, invariant under the action of permutations. From the integrability condition (\[eq:1\]) on $\nu$, it is easy to check that for $k\geq 2$, if $$A_k=\{\pi\in {\mathcal{P}}_{\mathbb{N}}:\pi|_{[k]}\neq \{[k]\}\}$$ is the set of partitions whose trace on $[k]$ has at least two blocks, then $$\label{eq:2}
  \kappa_\nu(A_k)=\int_{{{\mathcal{S}^{\downarrow}}}}\nu({\mathrm{d}}{\mathbf{s}})\Big(1-\sum_{i\geq
  1}s_i^k\Big)<\infty\, ,$$ for every $k\geq 2$, since $1-\sum_{i\geq 1}s_i^k\leq 1-s_1^k\leq
k(1-s_1)$.

### Exchangeable partitions of finite and infinite sets {#sec:exch-part-finite}

In this section, we establish some elementary results concerning exchangeable partitions of $[n]$ or ${\mathbb{N}}$. The set of partitions with variable size, namely $${\mathcal{P}}={\mathcal{P}}_{\mathbb{N}}\cup\bigcup_{n\geq 1}{\mathcal{P}}_{[n]}\, ,$$ is endowed with the distance $$d_{\mathcal{P}}(\pi,\pi')=\exp(-\sup\{k\geq 1:\pi|_{[k]}=\pi'|_{[k]}\})\, .$$ In the sequel, convergence in distribution for partitions will be understood with respect to the separable and complete space $({\mathcal{P}},d_{\mathcal{P}})$. We will use the falling factorial notation $$(x)_n=x(x-1)\ldots(x-n+1)=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}$$ for $x$ a real number and $n \in {\mathbb{N}}$, $n <x+1$. When $x \in \mathbb N$, we extend the notation to all $n \in \mathbb N$, by setting $(x)_n=0$ for $n \geq x+1$.

\[sec:exch-part-finite-1\] Let $\pi$ be an exchangeable partition of $[n]$, and let $k\leq
n$. Then for every $B\subset [k]$ with $l$ elements such that $1\in
B$, $$\mathbb P\left([k]\cap \pi_{(1)}=B\, |\,
\#\pi_{(1)} \right)=\frac{(\#\pi_{(1)}-1)_{l-1}(n-\#\pi_{(1)})_{k-l}}{(n-1)_{k-1}}\,
.$$

<span>**Proof.** </span> By exchangeability, the probability under consideration does depends on $B$ only through its cardinality, and this equal to $\mathbb P\left(i_2,\ldots,i_l\in
\pi_{(1)},j_1,\ldots,j_{k-l}\notin \pi_{(1)}|\#\pi_{(1)}\right)$ for any pairwise disjoint $i_2,\ldots,i_l,j_1,\ldots,j_{k-l}\in
\{2,3,\ldots,n\}$ (note that there are $\binom{n-1}{l-1}\binom{n-l}{k-l}$ such choices). Consequently, $$\begin{aligned}
\mathbb P([k]\cap \pi_{(1)}=B\, |\,
\#\pi_{(1)})&=&\frac{\mathbb E\bigg[\sum_{\substack{i_2,\ldots,i_l\\j_1,\ldots,j_{k-l}}}
    {\mathbf{1}}_{\{i_2,\ldots,i_l\in
      \pi_{(1)}\}}{\mathbf{1}}_{\{j_1,\ldots,j_{k-l}\notin \pi_{(1)}\}}\,
    \big|\,
    \#\pi_{(1)}\bigg]}{\binom{n-1}{l-1}\binom{n-l}{k-l}}\\ &=&\frac{\binom{\#\pi_{(1)}-1}{l-1}\binom{n-\#\pi_{(1)}}{k-l}}{\binom{n-1}{l-1}\binom{n-l}{k-l}}\,
,\end{aligned}$$ where the sum in the expectation is over indices considered above. This yields the result.

\[sec:tightness-1\] Let $(\pi^{(n)},n\geq 1)$ be a sequence of random exchangeable partitions respectively in ${\mathcal{P}}_{[n]}$. We assume that $\pi^{(n)}$ converges in distribution to $\pi$. Then $\pi$ is exchangeable and $$\frac{\#\pi^{(n)}_{(i)}}{n}
\underset{n\to\infty}{\overset{(d)}{\longrightarrow}}|\pi_{(i)}|\, ,$$ the latter convergences holding jointly for $i\geq 1$, and jointly with the convergence $\pi^{(n)}\to\pi$.

<span>**Proof.** </span> The fact that $\pi$ is invariant under the action of permutations of ${\mathbb{N}}$ with finite support is inherited from the exchangeability of $\pi^{(n)}$, and one concludes that $\pi$ is exchangeable @aldous85.

The random variables $(\#\pi^{(n)}_{(i)}/n,i\geq 1)$ take values in $[0,1]$, so their joint distribution is tight, and up to extraction, we may assume that they converge in distribution to a random vector $(x_{(i)},i\geq 1)$, jointly with the convergence $\pi^{(n)}\to\pi$. We want to show that a.s. $x_{(i)}=|\pi_{(i)}|$, which will characterize the limiting distribution. For $k\geq l\geq 1$ fixed, by summing the formula of Lemma \[sec:exch-part-finite-1\] over all $B\subset [k]$ containing $i$, with $l$ elements, we get $$\begin{aligned}
\mathbb P\big(\#([k]\cap\pi_{(i)}^{(n)})=l\, \big|\, \#\pi^{(n)}_{(i)}\big)&=&
\binom{k-1}{l-1}\frac{(\#\pi^{(n)}_{(i)}-1)_{l-1}(n-\#\pi^{(n)}_{(i)})_{k-l}}{
  (n-1)_{k-1}}\\ &\underset{n\to\infty}{\longrightarrow}&
\binom{k-1}{l-1}x_{(i)}^{l-1}(1-x_{(i)})^{k-l}\, ,\end{aligned}$$ which entails that, conditionally on $x_{(i)}$, $\#([k]\cap
\pi_{(i)})-1$ follows a binomial distribution with parameters $(k-1,x_{(i)})$. Therefore, $$|\pi_{(i)}|=\lim_{k\to\infty}\frac{\#([k]\cap
  \pi_{(i)})}{k}=x_{(i)}\qquad \text{a.s.}\, ,$$ by the law of large numbers. $\hfill \square$

\[sec:self-simil-fragm-5\] Let $(\pi^{(i)},1\leq i\leq r)$ be a sequence of random elements of ${\mathcal{P}}_{\mathbb{N}}$, which is exchangeable in the sense that $(\sigma\pi^{(i)},1\leq i\leq r)$ has same distribution as $(\pi^{(i)},1\leq i\leq r)$, for every permutation $\sigma$ of ${\mathbb{N}}$. Then for every $k\geq 2$, $$\mathbb P\big(2,3,\ldots,k\in \pi^{(1)}_{(1)}\, \big|\, |\pi^{(i)}_{(j)}|,1\leq
i\leq r,j\geq 1\big)=|\pi_{(1)}^{(1)}|^{k-1}\, .$$

<span>**Proof.** </span>Let $n\geq k$ and set $\pi^{(i,n)}=\pi^{(i)}|_{[n]}$, so that $(\pi^{(i,n)},1\leq i\leq r)$ is a random sequence of ${\mathcal{P}}_{[n]}$ that is exchangeable. Then, by using the same argument as in the proof of Lemma \[sec:exch-part-finite-1\], it holds that $$\mathbb P\big(2,3,\ldots,k\in \pi_{(1)}^{(1,n)}\, \big|\,
\#\pi^{(i,n)}_{(j)},1\leq i\leq r,1\leq j\leq n\big)=\frac{
  (\#\pi^{(1,n)}_{(1)}-1)_{k-1}}{(n-1)_{k-1}}\, .$$ Using Lemma \[sec:tightness-1\], and the fact that $(\pi^{(i,n)},1\leq i\leq r)$ converges in distribution to $(\pi^{(i)},1\leq i\leq r)$ as $n\to
\infty$, it is then elementary to get the result by taking limits.

### Poisson construction of homogeneous fragmentations {#sec:poiss-constr-homog}

We now recall a useful construction of homogeneous fragmentations using Poisson point processes. We again fix a dislocation measure $\nu$.

Consider a Poisson random measure $\mathcal{N}({\mathrm{d}}t{\mathrm{d}}\pi{\mathrm{d}}i)$ on the set ${\mathbb{R}}_+\times {\mathcal{P}}_{\mathbb{N}}\times {\mathbb{N}}$, with intensity measure ${\mathrm{d}}t\otimes\kappa_\nu({\mathrm{d}}\pi)\otimes\#_{\mathbb{N}}({\mathrm{d}}i)$, where $\#_{\mathbb{N}}$ is the counting measure on ${\mathbb{N}}$. We use a Poisson process notation $(\pi^0_t,i^0_t)_{t\geq 0}$ for the atoms of ${\cal N}$: for $t\geq
0$, if $(t,\pi,i)$ is an atom of $\mathcal{N}$ then we let $(\pi^0_t,i^0_t)=(\pi,i)$, and if there is no atom of $\mathcal{N}$ of the form $(t,\pi,i)$, then we set $\pi^0_t=\mathbbm{O}_{\mathbb{N}}$ and $i^0_t=0$ by convention. One constructs a process $(\Pi^0(t),t\geq 0)$ by letting $\Pi^0(0)=\mathbbm{O}_{\mathbb{N}}$, and given that $\Pi^0(s),0\leq
s<t$ has been defined, we let $\Pi^0(t)$ be the element of ${\mathcal{P}}_{\mathbb{N}}$ obtained from $\Pi^0(t-)$ by leaving its blocks unchanged, except the $i^0_t$-th block $\Pi^0_{i^0_t}(t-)$, which is intersected with $\pi^0_t$. Of course, this construction is only informal, since the times $t$ of occurrence of an atom of $\mathcal{N}$ are everywhere dense in ${\mathbb{R}}_+$. However, using (\[eq:2\]), it is possible to perform a similar construction for partitions restricted to $[k]$, and check that these constructions are consistent as $k$ varies @BertoinBook [Section 3.1.1]. The process $(\Pi^0(t),t\geq 0)$ is called a partition-valued homogeneous fragmentation with dislocation measure $\pi$.

Note in particular that the block $\Pi_{(1)}^0(t)$ that contains $1$ at time $t$, is given by $$\label{eq:23}
\Pi_{(1)}^0(t)=\bigcap_{\substack{0<s\leq t\\i^0_s=1}} (\pi^0_s)_{(1)}\, ,$$ and that the restriction of $\mathcal{N}$ to ${\mathbb{R}}_+\times {\mathcal{P}}_{\mathbb{N}}\times
\{1\}$ is a Poisson measure with intensity ${\mathrm{d}}t\otimes
\kappa_\nu({\mathrm{d}}\pi)$.

For $k\geq 2$, let $D_k^0=\inf\{t\geq 0:\Pi^0(t)\in A_k\}$ be the first time when the restriction of $\Pi^0(t)$ to $[k]$ has at least two blocks. By the previous construction, it is immediate to see that $D_k^0$ has an exponential distribution with parameter $\kappa_\nu(A_k)$: it is the first time $t$ such that $i^0_t=1$ and $\pi^0_t\in A_k$. Moreover, by standard properties of Poisson random measures, conditionally on $D_k^0=s$, the random variables $\pi^0_s$ and $(\pi^0_t,i^0_t)_{0\leq t<s}$ are independent, and the law of $\pi^0_s$ equals $\kappa_\nu(\cdot\, |\, A_k)=\kappa_\nu(\cdot\cap
A_k)/\kappa_\nu(A_k)$, while $(\pi^0_t,i^0_t)_{0\leq t<s}$ has same distribution as the initial process conditioned on $\{(\pi^0_t,i_t^0)\notin
A_k \times \{1\},0\leq t<s\}=\{D^0_k\geq s\}$, which has probability $e^{-s\kappa_\nu(A_k)}$. It is also equivalent to condition on $\{D^0_k>s\}$, since $\mathbb P(D^0_k=s)=0$. The next statement sums up this discussion. By definition, we let $X(t\wedge
s-)=X(t){\mathbf{1}}_{\{t<s\}}+X(s-){\mathbf{1}}_{\{t\geq s\}}$ for $X$ càdlàg.

\[sec:continuous-model-1\] Let $F,f$ be non-negative measurable functions. Then $$\begin{aligned}
  \lefteqn{\mathbb E\Big[F(\Pi^0(t\wedge D^0_k-),t\geq 0)f(\pi^0_{D_k^0})\Big]}\\
  &=&\kappa_\nu(f|A_k) \int_0^\infty
  \kappa_\nu(A_k){\mathrm{d}}s\, \mathbb E\big[F(\Pi^0(t\wedge
    s),t\geq 0)\, {\mathbf{1}}_{\{ D_k^0> s\}}\big]\, . \end{aligned}$$ Otherwise said, $\pi^0_{D^0_k}$ and $(\Pi^0(t\wedge
D^0_k-),t\geq 0)$, are independent with respective laws $\kappa_\nu(\cdot\, |\, A_k)$, and the law of $(\Pi^0(t\wedge
\mathbbm{e}),t\geq 0)$ where $\mathbbm{e}$ is an exponential random variable, independent of $\Pi^0$, and with parameter $\kappa_\nu(A_k)$.

### Self-similar fragmentations {#sec:self-simil-fragm-1}

From a homogeneous fragmentation $\Pi^0$ constructed as above, one can associate a one-parameter family of ${\mathcal{P}}_{\mathbb{N}}$-valued processes by a time-changing method. Let $a\in {\mathbb{R}}$. For every $i\geq 1$ we let $(\tau_{(i)}^a(t),t\geq 0)$ be defined as the right-continuous inverse of the non-decreasing process $$\int_0^t|\Pi^0_{(i)}(u)|^{-a}{\mathrm{d}}u\, ,\qquad t\geq 0\, .$$ For $t\geq 0$, let $\Pi(t)$ be the random partition of ${\mathbb{N}}$ whose blocks are given by $\Pi_{(i)}^0(\tau_{(i)}^a(t)),i\geq 1$. One can check that this definition is consistent, namely, that for every $j\in
\Pi_{(i)}^0(\tau_{(i)}^a(t))$, one has $\Pi_{(i)}^0(\tau_{(i)}^a(t))=\Pi_{(j)}^0(\tau_{(j)}^a(t))$.

The process $(\Pi(t),t\geq 0)$ is called the self-similar fragmentation with index $a$ and dislocation measure $\nu$ @BertoinBook [Chapter 3.3]. We now assume that $a=-\gamma<0$ is fixed once and for all. Let $D_k=\inf\{t\geq 0:\Pi(t)\in A_k\}$.

\[sec:self-simil-fragm-2\] Conditionally given $\sigma\{\Pi_{(i)}(t\wedge D_k):t\geq 0,1\leq
i\leq k\}$, and letting $\pi=\Pi(D_k)$, the random variable $(\Pi_i(t+D_k),t\geq 0)_{1\leq i\leq b([k]\cap\pi)}$ has same distribution as $(\pi_i\cap \Pi^{(i)}(|\pi_i|^at),t\geq 0)_{1\leq
  i\leq b([k]\cap \pi)}$, where $(\Pi^{(i)},i\geq 1)$ are i.i.d. copies of $\Pi$.

<span>**Proof.** </span>For every $i\geq 1$ we let $L_i=\inf\{t\geq
0:\Pi_{(i)}(t)\cap [k]\neq [k]\}$. Then $L=(L_i,i\geq 1)$ is a so-called <span>*stopping line*</span>, i.e. for every $i\geq 1$, $L_i$ is a stopping time with respect to the natural filtration of $\Pi_{(i)}$, while $L_i=L_j$ for every $j\in \Pi_{(i)}(L_i)$. We let $\Pi(L)$ be the partition whose blocks are $\Pi_{(i)}(L_i),i\geq 1$ — by definition of a stopping line, two such blocks are either equal or disjoint. Note that $t+L=(t+L_i,i\geq 1)$ is also a stopping line, as well as $t\wedge L=(t\wedge L_i,i\geq 1)$.

From the so called <span>*extended branching property*</span> @BertoinBook [Lemma 3.14], we obtain that conditionally given $\sigma\{\Pi(t\wedge L),t\geq 0\}$, the process $(\Pi(t+L),t\geq 0)$ has same distribution as $$(\{\pi_i\cap \Pi^{(i)}(|\pi_i|^at)),i\geq 1\},t\geq 0)\, ,$$ where $\pi=\Pi(L)$ and $(\Pi^{(i)},i\geq 1)$ are i.i.d. copies of $\Pi$. The result is then a specialization of this, when looking only at the blocks of $\Pi$ that contain $1,2,\ldots,k$.

It will be of key importance to characterize the joint distribution of $D_k,(\Pi_{(i)}(D_k),1\leq i\leq k)$. This can be obtained as a consequence of Lemma \[sec:continuous-model-1\]. Recall the construction of $\Pi$ from $\Pi^0$, let $\tau_{(i)}=\tau_{(i)}^a$, and define $\pi_t=\pi^0_{\tau_{(1)}(t)}$. The latter is equal to $\pi^0_{\tau_{(i)}(t)}$ for every $i\in [k]$ and $t\leq D_k$.

\[sec:poiss-constr-homog-1\] Let $F,f$ be non-negative, measurable functions. Then $$\begin{aligned}
\lefteqn{\mathbb E\Big[F(|\Pi_{(1)}(t\wedge D_k-)|,t\geq 0)f(\pi_{D_k})\Big]}\\
&=&\kappa_\nu(f|A_k)
 \int_0^\infty{\mathrm{d}}u\,
\kappa_\nu(A_k)\mathbb E \left[|\Pi_{(1)}(u)|^{k-1+a} \mathbf 1_{\{ |\Pi_{(1)}(u)|>0\}}F(|\Pi_{(1)}(t\wedge
  u)|,t\geq 0)\right]\end{aligned}$$

<span>**Proof.** </span>By definition, $D_k$ (resp. $D^0_k$) is the first time when $[k]\cap \Pi(t)\neq [k]$ (resp. $[k]\cap
\Pi^0(t)\neq [k]$). It follows that $D^0_k=\tau_{(1)}(D_k)$, and that the process $$\Pi_{(1)}(t\wedge D_k-)=\Pi^0_{(1)}(\tau_{(1)}(t\wedge
D_k-))=\Pi^0_{(1)}(\tau_{(1)}(t)\wedge D^0_k-)\, ,\qquad t\geq 0$$ is measurable with respect to $\sigma\{\Pi^0_{(1)}(t\wedge D^0_k-),t\geq
0\}$. Lemma \[sec:continuous-model-1\] implies that $$\begin{aligned}
\lefteqn{\mathbb E\Big[F(|\Pi_{(1)}(t\wedge D_k-)|,t\geq
    0)f(\pi_{D_k})\Big]}
\\ &=&\mathbb E\Big[F(|\Pi_{(1)}^0(\tau_{(1)}(t)\wedge D^0_k-)|,t\geq
  0)f(\pi^0_{D^0_k})\Big] \\&=&\kappa_\nu(f|A_k) \int_0^\infty{\mathrm{d}}s\, \kappa_\nu(A_k)\mathbb E\Big[F\big(|\Pi_{(1)}^{0}(\tau_{(1)}(t)\wedge
  s)|,t\geq 0\big){\mathbf{1}}_{\{
    D_k^0>s\}}\Big]\\ &=&\kappa_\nu(f|A_k)\mathbb E\bigg[\int_0^\infty{\mathrm{d}}u\,
  \kappa_\nu(A_k)|\Pi_{(1)}(u)|^aF(|\Pi_{(1)}^0(\tau_{(1)}(t)\wedge
  \tau_{(1)}(u))|,t\geq 0){\mathbf{1}}_{\{
    D_k>u\}}\bigg]\\ &=&\kappa_\nu(f|A_k)\mathbb E\bigg[\int_0^\infty{\mathrm{d}}u\, \kappa_\nu(A_k)|\Pi_{(1)}(u)|^aF(|\Pi_{(1)}(t\wedge u)|,t\geq
  0){\mathbf{1}}_{\{ D_k>u\}}\bigg]\, ,\end{aligned}$$ where in the third equality, we used successively Fubini's theorem and the change of variables $s=\tau_{(1)}(u)$, so that ${\mathrm{d}}s=|\Pi_{(1)}(u)|^{a}{\mathrm{d}}u$. We conclude by using the fact that $$\label{eq:24}
\mathbb P\Big(D_k>u\, \big|\, |\Pi_{(1)}(t)|,0\leq t\leq u\Big)=
|\Pi_{(1)}(u)|^{k-1}\, ,$$ which can be argued as follows. Let $0\leq
t_1<t_2<\ldots<t_r=u$ be fixed times, then by applying Lemma \[sec:self-simil-fragm-5\] to the sequence $(\Pi(t_i),1\leq i\leq
r)$, we obtain that $$\mathbb P\Big(D_k>u\, \big|\, |\Pi_{(1)}(t_i)|,1\leq i\leq r\Big)=
|\Pi_{(1)}(u)|^{k-1}\, .$$ This yields (\[eq:24\]) by a monotone class argument, using the fact that $\sigma\{|\Pi_{(1)}(t)|,0\leq
t\leq u\}$ is generated by finite cylinder events.

The last important property of self-similar fragmentation is that the process $(|\Pi_{(1)}(t)|,t\geq 0)$ is a Markov process, which can be described as follows @BertoinBook. Let $(\xi_t,t\geq 0)$ be a subordinator with Laplace transform $$\mathbb E\left[\exp(-r\xi_t)\right]=\exp\bigg(-t\int_0^\infty\Big(1-\sum_{i\geq
  1}s_i^{r+1}\Big)\nu({\mathrm{d}}{\mathbf{s}})\bigg)\, .$$ Then $(|\Pi^0_{(1)}(t)|,t\geq 0)$ as same distribution as $(\exp(-\xi_t),t\geq0)$, and consequently, the process $(|\Pi_{(1)}(t)|,t\geq
0)$ is a so-called self-similar Markov process:

\[Corollary 3.1 of @BertoinBook\] \[sec:self-simil-fragm-3\] The process $(|\Pi_{(1)}(t)|,t\geq
0)$ has same distribution as $\exp(-\xi_{\tau(t)},t\geq 0)$, where $\tau$ is the right-continuous inverse of the process $(\int_0^u\exp(a\xi_s){\mathrm{d}}s,u\geq 0)$.

Continuum fragmentation trees {#sec:cont-fragm-trees}
-----------------------------

This section is devoted to a more detailed description of the limiting self-similar fragmentation tree ${\mathcal{T}}_{\gamma,\nu}$ @HM04. In particular, we will need a new decomposition result of reduced trees at the first branchpoint (Proposition \[sec:cont-fragm-trees-2\]).

### Trees with edge-lengths and ${\mathbb{R}}$-trees {#tree-edge-lengths}

We saw in Section \[sec:r-trees-gromov\] how to turn a tree into a (finite) measured metric space. It is also easy to "turn discrete trees into ${\mathbb{R}}$-trees", viewing the edges as real segments of length $1$.

More generally, a plane tree <span>*with edge-length*</span> is a pair $\theta=({\mathbbm{t}},(\ell_u,u\in {\mathbbm{t}}))$ where $\ell_u\geq 0$ for every $u\in
{\mathbbm{t}}$, and a <span>*tree with edge-lengths*</span> is obtained by "forgetting the ordering" in a way that is adapted from the discussion of Section \[sec:discrete-trees\] in a straightforward way. Namely, the plane trees with edge-lengths $({\mathbbm{t}},(\ell_u,u\in {\mathbbm{t}}))$ and $({\mathbbm{t}}',(\ell'_u,u\in {\mathbbm{t}}'))$ are equivalent if there exist permutations ${\boldsymbol{\sigma}}=(\sigma_u,u\in {\mathbbm{t}})$ such that ${\boldsymbol{\sigma}}{\mathbbm{t}}={\mathbbm{t}}'$ and $\ell'_{{\boldsymbol{\sigma}}(u)}=\ell_u$, for every $u\in {\mathbbm{t}}$. We let ${\boldsymbol{\Theta}}$ be the set of trees with edge-lengths, i.e. of equivalence classes of plane trees with edge-lengths. There is a natural concatenation transformation, similar to $\langle\cdot\rangle$, for elements of ${\boldsymbol{\Theta}}$. Namely, if $\theta^{(i)}=({\mathbbm{t}}^{(i)},(\ell^{(i)}_u,u\in
{\mathbbm{t}})),1\leq i\leq k$ is a sequence of plane trees with edge-lengths and $\ell \geq 0$, let $$\langle\theta^{(i)},1\leq i\leq k\rangle_\ell=({\mathbbm{t}},(\ell_u,u\in
{\mathbbm{t}}))\, ,$$ be defined by $${\mathbbm{t}}=\langle {\mathbbm{t}}^{(i)},1\leq i\leq k\rangle\, ,$$ and $$\ell_{\varnothing}=\ell\, ,\qquad \ell_{iu}=\ell^{(i)}_u\, ,\quad
1\leq i\leq k,\, u\in {\mathbbm{t}}^{(i)}\, .$$ If we replace each $\theta^{(i)}$ by another equivalent plane tree with edge-lengths, then the resulting concatenation is equivalent to the first one, so that this operation is well-defined for elements of ${\boldsymbol{\Theta}}$

Let $\theta\in {\boldsymbol{\Theta}}$, and consider a plane representative $({\mathbbm{t}},(\ell_u,u\in{\mathbbm{t}}))$. We construct an ${\mathbb{R}}$-tree ${\mathcal{T}}$ by imagining that the edge from $\mathrm{pr}(u)$ to $u$ has length $\ell_u$. Note that this intuitively involves a new edge with length $\ell_\varnothing$ pointing from the root $\rho$ of the resulting ${\mathbb{R}}$-tree to $\varnothing$ (this is sometimes called <span>*planting*</span>). Formally, ${\mathcal{T}}$ is the isometry-equivalence class of a subset of ${\mathbb{R}}^{\mathbbm{t}}$ endowed with the $l^1$-norm $\|(x_u,u\in {\mathbbm{t}})\|_1=\sum_{u\in
  {\mathbbm{t}}}|x_u|$, defined as the union of segments $$\bigcup_{u\in {\mathbbm{t}}}\Big[\sum_{v\prec u}\ell_ve_v,\sum_{v\prec
  u}\ell_ve_v+\ell_u e_u \Big]\, ,$$ where $(e_u,u\in {\mathbbm{t}})$ is the canonical basis of ${\mathbb{R}}^{\mathbbm{t}}$ and $v\prec u$ means that $v$ is a strict ancestor of $u$ in ${\mathbbm{t}}$. This ${\mathbb{R}}$-tree is naturally rooted at $0\in
{\mathbb{R}}^{\mathbbm{t}}$. Of course, its isometry class does not depend on the choice of the plane representative of $\theta$, and can be written ${\mathcal{T}}(\theta)$ unambiguously. Note that there is a natural "embedding" mapping $\iota:{\mathsf{t}}\to{\mathcal{T}}(\theta)$ inherited from $$\label{eq:10}
\iota_0:{\mathbbm{t}}\to {\mathcal{T}}\, ,\qquad \iota_0(u)=\sum_{v\preceq
  u}\ell_ve_v\, ,$$ and the latter is an isometry if $\theta$ is endowed with the (semi-)metric $d_\theta$ on its vertices, defined by $$d_\theta(u,v)=\sum_{w\preceq u \, {\rm xor }\, w\preceq v}\ell_w\,
,$$ where xor denotes "exclusive or".

Conversely, it is an elementary exercise to see that any rooted ${\mathbb{R}}$-tree ${\mathcal{T}}$ with a finite number of leaves can be written in the form ${\mathcal{T}}={\mathcal{T}}(\theta)$ for some $\theta\in {\boldsymbol{\Theta}}$, which is in fact unique. In the sequel, we will often identify the tree $\theta\in
{\boldsymbol{\Theta}}$ with the ${\mathbb{R}}$-tree ${\mathcal{T}}(\theta)$. For instance, this justifies the notation $\langle{\mathcal{T}}^{(1)},\ldots,{\mathcal{T}}^{(r)}\rangle_\ell$ for ${\mathbb{R}}$-trees ${\mathcal{T}}^{(1)},\ldots,{\mathcal{T}}^{(r)}$ with finitely many leaves and for $\ell\geq 0$, which stands for the ${\mathbb{R}}$-tree in which the roots of ${\mathcal{T}}^{(1)},\ldots,{\mathcal{T}}^{(r)}$ have been identified, and attached to a segment of length $\ell$ to a new root.

With a discrete tree ${\mathsf{t}}$ , we canonically associate the tree with edge-lengths $\theta$ in which all lengths are equal to $1$, and the rooted ${\mathbb{R}}$-tree ${\mathcal{T}}({\mathsf{t}})={\mathcal{T}}(\theta)$. In this case, $d_\theta=d_{\mathrm{gr}}$ is the graph distance. Using the isometry $\iota:{\mathsf{t}}\mapsto{\mathcal{T}}({\mathsf{t}})$, we get the following statement, left as an exercise to the reader.

\[sec:trees-with-edge\] Viewing ${\mathsf{t}}\in {\mathsf{T}}$ as the element $({\mathsf{t}},d_{\mathrm{gr}},\rho,\mu_{\partial{\mathsf{t}}})$ of ${\mathscr{M}_{{\rm w}}}$ as in Section \[sec:r-trees-gromov\], and endowing ${\mathcal{T}}({\mathsf{t}})$ with the uniform probability distribution on $\mathcal{L}({\mathcal{T}}({\mathsf{t}}))$, it holds that $$d_{\mathrm{GHP}}(a{\mathsf{t}},a{\mathcal{T}}({\mathsf{t}}))\leq a\, ,\qquad a>0\, .$$

Due to this statement, in order to prove that the Markov branching tree $T_n$ with law ${\mathsf{P}}_n^q$ converges after rescaling towards ${\mathcal{T}}_{\gamma,\nu}$, it suffices to show the same statement for the ${\mathbb{R}}$-tree ${\mathcal{T}}(T_n)$. We will often make the identification of $T_n$ with ${\mathcal{T}}(T_n)$.

### Partition-valued processes and ${\mathbb{R}}$-trees {#sec:part-valu-proc}

Let $(\pi(t),t\geq 0)$ be a process with values in $C\subset {\mathbb{N}}$, finite or infinite, which is non-decreasing and indexed either by $t\in {\mathbb{Z}}_+$ or $t\in {\mathbb{R}}_+$, in which case we also assume that $\pi(\cdot)$ is right-continuous. We assume that there exists some $t_0>0$ such that $\pi(t_0)=\mathbbm{I}_C$. Let $B\subseteq C$ be finite. If $B=\{i\}$, we let $$D^\pi_{\{i\}}=\inf\{t\geq 0:\{i\}\in \pi(t)\}$$ be the first time where $i$ is isolated in a singleton block, and for $\#B\geq 2$, let $$D^\pi_{B}=\inf\{t\geq 0:B\cap \pi(t)\neq B\}\, .$$ We can build a tree with edge-lengths (and labeled leaves) $\theta(\pi(\cdot),B)$ by he following inductive procedure:

1.  If $B=\{i\}$ we let $\theta(\pi(\cdot), B)$ be the tree $\bullet$ with length $D^\pi_{\{i\}}$

2.  if $\#B\geq 2$, we let $$\theta(\pi(\cdot),B)=\langle\theta( \pi(D^\pi_{B}+\cdot),B\cap
      \pi_i(D^\pi_{B}) ),1\leq i\leq b\rangle_{D^\pi_{B}}\, ,$$ where $b$ is the number of blocks of $\pi(D^\pi_{B})$ that intersect $B$, and which are denoted by $\pi_1(D^\pi_{B}),\ldots,\pi_b(D^\pi_{B})$.

Note that the previous labeling convention for blocks may not agree with our usual convention of labeling with respect to order of least element.

If $(\pi(t),t\in {\mathbb{Z}}_+)$ is indexed by non-negative integers, and satisfies $\pi(0)=\mathbbm{O}_C$, there is a similar construction with trees rather than trees with edge-lengths. Namely, we let ${\mathsf{t}}_{\pi(\cdot)}$ be defined by

1.  ${\mathsf{t}}_{\pi(\cdot)}=\bullet$ if $\#C=1$, and

2.  ${\mathsf{t}}_{\pi(\cdot)}=\langle{\mathsf{t}}_{\pi_i(1)\cap\pi(\cdot+1)},1\leq
      i\leq b\rangle$ otherwise, where $b$ is the number of blocks of $\pi(1)$, denoted by $\pi_1(1),\ldots,\pi_b(1)$.

It is then easy to see that, with the notations of the previous section, $$\label{eq:12}
{\mathcal{T}}({\mathsf{t}}_{\pi(\cdot)})={\mathcal{T}}(\theta(\pi(\cdot),C))\, ,$$ And one can view $\theta(\pi(\cdot),B)$ as the subtree of ${\mathsf{t}}_{\pi(\cdot)}$ spanned by the root and the leaves with labels in $B$.

### Continuum fragmentation trees {#sec:continuous-model}

Let $(\Pi(t),t\geq 0)$ be the self-similar fragmentation process with index $-\gamma<0$ and dislocation measure $\nu$. The formation of dust property alluded to in Section \[sec:self-simil-fragm\] amounts to the fact that almost-surely, there exists some time $t_0>0$ such that $\Pi(t)=\mathbbm{I}_{\mathbb{N}}$ for every $t\geq t_0$. Consequently, the construction of the previous paragraph applies with $C={\mathbb{N}}$, and allows to construct a family of ${\mathbb{R}}$-trees $$\mathcal{R}_{B}=\theta(\Pi(\cdot),B)$$ indexed by finite subsets $B\subset {\mathbb{N}}$. Recall that a tree $\theta\in{\boldsymbol{\Theta}}$ has been identified with ${\mathcal{T}}(\theta)\in{\mathscr{T}_{{\rm w}}}$. These ${\mathbb{R}}$-trees have finitely many leaves that are naturally indexed by elements of $B$. Moreover, they satisfy an obvious consistency property, meaning that taking the subtree spanned by the root and the leaves indexed by $B'\subset B$ yields an ${\mathbb{R}}$-tree with same law as $\mathcal{R}_{B'}$. This is the key to the definition of the fragmentation tree ${\mathcal{T}}_{\gamma,\nu}$.

\[@HM04\]\[sec:cont-fragm-trees-1\] Conditionally given ${\mathcal{T}}_{\gamma,\nu}=({\mathcal{T}},d,\rho,\mu)$, let $L_1,L_2,\ldots$ be an i.i.d. sequence of leaves of ${\mathcal{T}}$ distributed according to $\mu$. Then for every finite $B\subset {\mathbb{N}}$, the <span> *reduced subtree*</span> $$\mathcal{R}({\mathcal{T}}_{\gamma,\nu},B)=\bigcup_{i\in B}[[\rho,L_i]]$$ has same distribution as $\mathcal{R}_B$.

Moreover, the law of ${\mathcal{T}}_{\gamma,\nu}$ is the only one having this property, among distributions on ${\mathscr{T}_{{\rm w}}}$ that charge only the set of $\{({\mathcal{T}},d,\rho,\mu)\in {\mathscr{T}_{{\rm w}}}:\, \forall\, x\in
{\mathcal{T}}, x\notin\mathcal{L}({\mathcal{T}})\implies\mu({\mathcal{T}}_x)>0\}$.

As an easy consequence, we have the following "converse construction" of fragmentations from ${\mathcal{T}}_{\gamma,\nu}$. With the notation of the proposition, for every $t\geq 0$, let $\Pi(t)$ be the partition of ${\mathbb{N}}$ such that $i,j$ are in the same block of $\Pi(t)$ if and only if $d(\rho,L_i\wedge L_j)>t$. Then $(\Pi(t),t\geq 0)$ is a self-similar fragmentation process with dislocation measure $\nu$ and index $-\gamma$.

Also, note that the <span>*reduced trees*</span> $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},B)$ rooted at $\rho$ and endowed with the empirical measure $$\mu_B=\frac{1}{\#B}\sum_{i\in B}\delta_{L_i}\, ,$$ converge in distribution as $\#B\to \infty$ in ${\mathscr{T}_{{\rm w}}}$ towards $({\mathcal{T}},d,\rho,\mu)$. In fact, the convergence holds a.s. if $B=[k]$ with $k\to\infty$: this is a simple exercise using the fact that $\{L_i,i\geq 1\}$ is a.s. dense in ${\cal L}({\mathcal{T}})$ (by property 3. in the definition of ${\mathcal{T}}_{\gamma,\nu}$), and the weak convergence of $\mu_{[k]}$ to $\mu$ as $k\to\infty$.

The following statement gives a decomposition of the reduced tree $\mathcal{R}({\mathcal{T}},[k])$ at its first branchpoint above the root. Recall the notation $D_k=\inf\{t\geq 0:\Pi(t)\in A_k\}$.

\[sec:cont-fragm-trees-2\] Let $k\geq 2$ and $\pi=\Pi(D_k),\pi'=\pi|_k, b=b(\pi')$. Then conditionally on $\{\pi,D_k\}$, the reduced tree $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},[k])$ has same distribution as $${\mathcal{T}}\Big(\big\langle|\pi_i|^\gamma\mathcal{R}({\mathcal{T}}^{(i)},\pi'_i),1\leq
i\leq b\big\rangle_{D_k}\Big)\, ,$$ where the ${\mathcal{T}}^{(i)}$ are i.i.d. with same distribution as ${\mathcal{T}}_{\gamma,\nu}$, independent of $\sigma\{\pi,D_k\}$.

Moreover, for every $i\in {\mathbb{N}}$, the tree $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},\{i\})$ has same distribution as the ${\mathbb{R}}$-tree associated with the tree $(\varnothing,D_1)\in{\boldsymbol{\Theta}}$, i.e. a real segment with length $D_1=\inf\{t\geq 0:\{1\}\in
\Pi(t)\}$.

<span>**Proof.** </span> The second statement is just a matter of definitions, so we only need to prove the first one. By Proposition \[sec:self-simil-fragm-2\], the process $\Pi(D_k+\cdot)$, in restriction to the blocks containing at least one element in $[k]$, has same distribution as the partitions-valued process whose blocks are those of $\pi_i\cap \Pi^{(i)}(|\pi_i|^{-\gamma}\cdot),1\leq i\leq
b$, for i.i.d. copies $\Pi^{(i)},i\geq 1$ of $\Pi$, independent on $\pi,D_k$. Therefore, one gets from the definition of $\mathcal{R}_B$ that $$\mathcal{R}_{[k]}\overset{(d)}{=}{\mathcal{T}}\langle\theta(
\Pi^{(i)}(|\pi_i|^{-\gamma}\cdot),\pi'_i),1\leq i\leq
b\rangle_{D_k}\, ,$$ from which the result follows immediately.

Note that Proposition \[sec:poiss-constr-homog-1\] gives the joint distribution of $D_k,|\pi_i|,1\leq i\leq b,\pi'$ as a special case, while Proposition \[sec:self-simil-fragm-3\] characterizes the law of $D_1$, since it is the first time where the process $(|\Pi_{(1)}(t)|,t\geq 0)$ attains $0$. This, together with the previous proposition, allows to characterize entirely the laws of the reduced trees of ${\mathcal{T}}_{\gamma,\nu}$, hence the law of ${\mathcal{T}}_{\gamma,\nu}$ itself.

### Markov branching trees as discrete fragmentation trees {#sec:discrete-model}

Recall the informal description of Markov branching trees ${\mathsf{P}}^q_n$ in the introduction, relying on collections of balls in urns. Rather than collections of indistinguishable balls that split randomly, it is convenient to consider instead a collection of balls that are distinguished by a random, exchangeable labeling. This is achieved by replacing partitions of integers by partitions of sets. We start with a preliminary lemma.

\[sec:partitions-1\] Let $n\geq 1$ be fixed, as well as a partition $\lambda\in {\mathcal{P}}_n$ with $p=p(\lambda)$ parts.

<span>(i)</span>There are $$C_\lambda=\frac{n!}{\prod_{i=1}^{p}\lambda_i!\prod_{j=1}^n
  m_j(\lambda)!}$$ partitions $\pi\in {\mathcal{P}}_{[n]}$ such that $\lambda(\pi)=\lambda$.

<span>(ii)</span> If $1\leq k\leq n$ and $\pi'\in {\mathcal{P}}_{[k]}$ has $b$ blocks, then for every $i_1,\ldots,i_b\in \{1,2,\ldots,p\}$ pairwise distinct, there are $$C_\lambda^{\pi'}(i_1,\ldots,i_b)=C_\lambda
\frac{1}{(n)_{k}}\prod_{j=1}^b(\lambda_{i_j})_{\#\pi'_j}$$ partitions $\pi\in {\mathcal{P}}_{[n]}$ such that $\lambda(\pi)=\lambda$, $\pi|_{[k]}=\pi'$ and $\#\pi_j=\lambda_{i_j},1\leq j\leq b$.

<span>**Proof.** </span>Let $p$ be the number of parts of $\lambda$. Then there are $p!/\prod_{j=1}^{n}m_j(\lambda)!$ sequences $(c_1,\ldots,c_p)$ whose non-increasing rearrangement is $\lambda$. With any such sequence, we can associate $$\frac{n!}{\prod_{i=1}^pc_i!}=\frac{n!}{\prod_{i=1}^p\lambda_i!}$$ sequences of the form $(B_1,\ldots,B_p)$ such that $\{B_1,\ldots,B_p\}$ is a partition of $[n]$ (beware that the labeling of the blocks $B_i$ will differ in general from labeling convention described above for the blocks of a partition), with $\#B_i=c_i,1\leq
i\leq p$. Finally, exactly $p!$ sequences of the form $(B_1,\ldots,B_p)$ induce the same partition $\{B_1,\ldots,B_p\}$. Putting things together easily yield the formula for $C_\lambda$.

For the second formula, if $\lambda\in {\mathcal{P}}_n,\pi'\in {\mathcal{P}}_{[k]}$ and $i_1,\ldots,i_b$ are given with $b=b(\pi')$, then any partition $\pi\in {\mathcal{P}}_{[n]}$ with $\lambda(\pi)=\lambda$ and $\pi| _{[k]}=\pi'$ must have $\pi_i|_{[k]}=(\pi|_{[k]})_i=\pi'_i$, for $1\leq i\leq b$, the first equality coming from our choice of the labeling of blocks of partitions. The restriction of $\pi$ to $[k]$ is thus entirely determined, while the restriction of $\pi$ to $[n]\setminus[k]$ is a partition of the latter set whose block-sizes are given by the sequence $\lambda_i,i\notin\{i_1,\ldots,i_b\},\lambda_{i_j}-\#\pi'_j,1
\leq j\leq b$. A simple adaptation of point <span>(i)</span> shows that there are $$\frac{(n-k)!}{\prod_{i\notin\{i_1,\ldots,i_b\}}\lambda_i!
  \prod_{j=1}^b(\lambda_{i_j}-\#\pi'_j)!}=C^{\pi'}_\lambda(i_1,\ldots,i_b)$$ such partitions.

Going back to Markov branching trees, let $B\subset {\mathbb{N}}$ have $n\geq 2$ elements. Let $q=(q_n,n\geq 1)$ satisfy (\[eq:6\]), and also assume that $q_1(\emptyset)=1$. For every $\pi\in {\mathcal{P}}_B$, set $$\label{eq:4}
p_B(\pi)=\frac{ q_n(\lambda(\pi))}{C_{\lambda(\pi)}}\, ,$$ where $C_\lambda$ is the constant appearing in Lemma \[sec:partitions-1\]. Given the partition of $n$ that it induces (which has distribution $q_n$), a $p_B$-distributed partition is thus uniform among possible choices of partitions of $B$. In particular, a random partition with distribution $p_B$ is exchangeable, i.e. its law is invariant under the action of permutations of $B$. By convention, the law $p_B$, if $B=\{i\}$ is a singleton, is the Dirac mass at the partition $\{\{i\}\}$.

For every $\pi\in {\mathcal{P}}_B$ with blocks $\pi_1,\pi_2,\ldots,\pi_k$ say, consider random partitions $\widetilde{\pi}^i,1\leq i\leq k$ of $\pi_1,\ldots,\pi_k$ respectively, chosen independently with respective distributions $p_{\pi_1},\ldots,p_{\pi_k}$. We let $Q(\pi,\cdot)$ be the law of the partition $\bigcup_{1\leq i\leq
  k}\widetilde{\pi}^i\in {\mathcal{P}}_B$. Then $Q$ is the transition kernel of a Markov chain on ${\mathcal{P}}_B$ (for any finite $B\subset{\mathbb{N}}$), that ends at the state $\mathbbm{I}_B$. It is easily seen that this Markov chain is exchangeable as a process. Moreover, the chain started from the state $\{B\}$, with $\#B = n$ has same distribution as the image of the chain started from $[n]$ under the action of any bijection $[n]\to B$.

For finite $C\subset {\mathbb{N}}$, we let $(\Pi^C(r),r\geq 0)$ be the chain with transition matrix $Q$ and started from $\Pi^C(0)=\mathbbm{O}_C$. Plainly, $\Pi^C$ is non-decreasing and attains $\mathbbm{I}_C$ in finite time a.s., so the construction of Section \[sec:part-valu-proc\] applies and yields a family $\theta(\Pi^C(\cdot),B)\in {\boldsymbol{\Theta}},B\subseteq C$, as well as a tree $T_C:={\mathsf{t}}_{\Pi^C(\cdot)}$. By construction, given that $\Pi^{C}(1)$ has blocks $\pi_1,\ldots,\pi_b$, the trees ${\mathsf{t}}_{\pi_i\cap
  \Pi^C(\cdot+1)},1\leq i\leq b$ are independent with same distribution as $T_{\pi_i},1\leq i\leq b$ respectively. Since the law of the non-increasing rearrangement of $\#\pi_i,1\leq i\leq b$ is $q_{\#C}$, we readily obtain the following statement[^5].

\[sec:mark-branch-trees-2\] The tree $T_C$ has law ${\mathsf{P}}^q_{\#C}$.

![An sample tree $T_{[n]}$ for $n=11$, with the labeled leaves. The process $\Pi^{(11)}$ can be easily deduced: for instance, $\Pi^{(11)}(1)=\{\{1,2,6,7\},\{3,5,10\},\{4,8,9,11\}\}$. As opposed to Figure \[fig:CMB\], leaves are all connected to vertices with at least $2$ children, because of the requirement $q_1(\emptyset)=1$. ](CMB2)

In fact, the leaves of the tree $T_C$ are naturally labeled by elements of $C$. We will use it in the sequel, without further formalizing the notion of trees with labeled leaves.

We will also use the shorthand notation $T_C^B$ for the <span>*reduced tree*</span> $\theta(\Pi^C(\cdot),B)$. Using the above description, and applying the Markov property for $\Pi^C$ at time $D^{\Pi^C}_B$ and the particular form of the Markov kernel $Q$, we immediately obtain the following, in the particular case $B=[k],C=[n]$.

\[sec:discrete-model-1\] Let $2\leq k\leq n$. Then, conditionally on $D^{\Pi^{[n]}}_{[k]}=\ell$ and $\Pi^{[n]}(D^{\Pi^{[n]}}_{[k]})=\pi$, with $\pi|_{[k]}=\pi'$, it holds that $T_{[n]}^{[k]}$ has same distribution as $$\langle \theta^{(i)},1\leq i\leq b(\pi')\rangle_{\ell}\, ,$$ where $\theta^{(i)},1\leq i\leq b$ are independent with respective laws that of $T_{\pi_i}^{\pi'_i},1\leq i\leq b(\pi')$.

**Proof.** The only subtle point is that $[k]\cap\pi_i=\pi'_i,1\leq i\leq b$, since the labeling of the blocks of $\pi,\pi'$ could differ. But since these partitions are respectively of $[n]$ and $[k]$, this cannot be the case. $\hfill \square$

Proofs of Theorems \[sec:main-result-1\] and \[sec:main-result-2\]  {#sec:proof-theor-refs}
===================================================================

Let $q=(q_n,n\geq 1)$ be a sequence of laws on ${\mathcal{P}}_n$ respectively, that satisfies (\[eq:6\]) and <span>**(H)**</span>, for some fragmentation pair $(-\gamma,\nu)$ and some slowly varying function $\ell$. In order to lighten notations, we let $a_n = n^\gamma\ell(n)$.

As we noticed in the introduction, it is easy to pass from the situation where $q_1(\emptyset)=1$ to the general situation, by adding independent linear strings with Geometric$(q_1(\emptyset))$-distributed lengths to the $n$ leaves of $T_n$. Since geometric distributions have exponential tails, the longest of these $n$ strings will have a length at most $C\log n$ with probability going to $1$ as $n\to\infty$, for some $C>0$. If we let $T_n^1$ be the tree for which $q_1(\emptyset)>0$ and $T_n^2$ the one for which $q_1(\emptyset)=1$, coupled in the way depicted above, we easily get, for any $\gamma>0$, $$\mathbb P(d_{\mathrm{GHP}}(a_n^{-1}T_n^1,a_n^{-1}T_n^2)\leq
Ca_n^{-1}\log n)\underset{n\to\infty}{\longrightarrow} 1\, .$$ Thus, we can deduce the convergence in distribution of $a_n^{-1}T_n^2$ to ${\mathcal{T}}_{\gamma,\nu}$ from that of $a_n^{-1}T_n^1$. Therefore, from now on and until the end of the present section, we make the following hypothesis, which will allow us to apply Lemma \[sec:mark-branch-trees-2\]:

> <span>**(H')**</span> The sequence $(q_n,n\geq 1)$ satisfies <span> **(H)**</span> and $q_1(\emptyset)=1$.

Preliminary convergence lemmas {#sec:prel-conv-lemm}
------------------------------

We now establish a couple of intermediate convergence results for the discrete model. Recall that the sequence of distributions $q_n,n\geq
2$ on ${\mathcal{P}}_n$ respectively induce distributions $p_B$ on ${\mathcal{P}}_B$ for finite $B$ by formula (\[eq:4\]). By convention we set $p_n=p_{[n]}$.

\[sec:prel-conv-lemm-1\] Let $k\geq 2$ and let $\pi'$ be an element in ${\mathcal{P}}_{[k]}$ with $b$ blocks, $b\geq 2$. Let $g:(0,\infty)^b\to{\mathbb{R}}$ be a continuous function with compact support. Then, under assumption <span>**(H')**</span>, $$a_np_n\bigg(
g\Big(\frac{\#\pi_1}{n},\ldots,\frac{\#\pi_b}{n}\Big){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}
\bigg)\underset{n\to\infty}{\longrightarrow}
\int_{{\mathcal{P}}_{\mathbb{N}}}\kappa_\nu({\mathrm{d}}\pi)
g(|\pi_1|,\ldots,|\pi_b|){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}\, ,$$ where $\kappa_\nu$ is the paintbox construction associated with $\nu$. Note that on the event $\{\pi|_{[k]}=\pi'\}$, the quantities $\#\pi_i/n$ and $|\pi_i|$ for $1\leq i\leq b$ that appear above are a.e. non-zero, respectively under $p_n$ and $\kappa_\nu$.

<span>**Proof.** </span> For simplicity, we let $$A_n=p_n\bigg(
g\Big(\frac{\#\pi_1}{n},\ldots,\frac{\#\pi_b}{n}\Big){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}
\bigg)\, .$$ By the definition of $q_n$ and Lemma \[sec:partitions-1\], $$\begin{aligned}
A_n&=&\sum_{\lambda\in {\mathcal{P}}_n}q_n(\lambda)
\sum_{\substack{i_1,\ldots,i_b\geq 1\\ {\rm
      pairwise\ distinct}}}g\Big(\frac{\lambda_{i_1}}{n},\ldots,\frac{\lambda_{i_b}}{n}\Big)\frac{C_
\lambda^{\pi'}(i_1,\ldots,i_b)}{C_\lambda}
\\ &=&\sum_{\lambda\in {\mathcal{P}}_n}q_n(\lambda)
\frac{1}{(n)_k}\sum_{\substack{i_1,\ldots,i_b\geq 1\\ {\rm
      pairwise\ distinct}}}g\Big(\frac{\lambda_{i_1}}{n},\ldots,\frac{\lambda_{i_b}}{n}\Big)
\prod_{j=1}^b(\lambda_{i_j})_{\#\pi'_j} \, .\end{aligned}$$ Now, the function $$h({\mathbf{s}})=\sum_{\substack{i_1,\ldots,i_b\geq 1\\ {\rm
      pairwise\ distinct}}}g(s_{i_1},\ldots,s_{i_b})
\prod_{j=1}^bs_{i_j}^{\#\pi'_j}
\, ,\qquad {\mathbf{s}}\in {{\mathcal{S}^{\downarrow}}}$$ is continuous and bounded, because $g$ is compactly supported in $(0,\infty)^b$, so that the sum is really a finite sum. Moreover, $$\label{eq:5}
h({\mathbf{s}})\leq K\sum_{\substack{0\leq
    k_1,k_2,\ldots< k\\k_1+k_2+\ldots=k}}\frac{k!}{\prod_{j\geq
    1}k_j!}\prod_{j\geq 1}s_j^{k_j}=K\Big(1-\sum_{j\geq
  1}s_j^k\Big)\leq kK(1-s_1)\, ,$$ where $K$ is an upper-bound of $|g|$, and for every $\lambda\in {\mathcal{P}}_n$, it is easily checked that for large $n$, if ${\varepsilon}>0$ is such that $g(x_1,\ldots,x_b)=0$ as soon as $\min_{1\leq i\leq b} x_i\leq {\varepsilon}$, $$\Big(1-\frac{k}{{\varepsilon}n}\Big)^kh(\lambda/n)\leq
\frac{1}{(n)_k}\sum_{\substack{i_1,\ldots,i_b\geq 1\\ {\rm
      pairwise\ distinct}}}g\Big(\frac{\lambda_{i_1}}{n},\ldots,
\frac{\lambda_{i_b}}{n}\Big) \prod_{j=1}^b(\lambda_{i_j})_{\#\pi'_j}
\leq\Big(\frac{n}{n-k}\Big)^kh(\lambda/n)\, .$$ Letting $n\to\infty$ and applying <span>**(H')**</span>, which is validated by (\[eq:5\]), $$\lim_{n\to\infty}a_nA_n=
\int_{{\mathcal{S}^{\downarrow}}}\nu({\mathrm{d}}{\mathbf{s}})h({\mathbf{s}})
$$ and letting ${\varepsilon}\to 0$, we conclude by monotone convergence that = \_<span>¶\_</span>\_() g(|\_1|,…,|\_b|)\_<span>{|\_<span>\[k\]</span>='}</span> ,$$ the latter equality being a simple consequence of the paintbox construction of Section \[sec:paintb-constr\].

Now, we associate with $(q_n,n\geq 1)$ a family of process $(\Pi^B(r),r\geq 0)$ with values in ${\mathcal{P}}_B$, as in Section \[sec:discrete-model\]. We let $\Pi^n=\Pi^{[n]}$ for simplicity, and set $$D_k^n=D_{[k]}^{\Pi^n}=\inf\{r\geq 0:[k]\cap\Pi^n(r)\neq \{[k]\}\}$$ for $2\leq k\leq n$, and $D_1^n=D^{\Pi^n}_{\{1\}}=\inf\{r\geq
0:\{1\}\in \Pi^n(r)\}$. Also, for $r\geq 0$ we let $$X_n(r)=\#\Pi^n_{(1)}(r)\, .$$

\[sec:prel-conv-lemm-2\] Let $n,k\in {\mathbb{N}}$ be fixed, with $n\geq k\geq 2$, and let $\pi'\in {\mathcal{P}}_{[k]}$ have $b \geq 2$ blocks. Let $F,f$ be measurable non-negative functions. Then $$\begin{aligned}
\lefteqn{\mathbb E\Big[F\Big(X_n\big(\cdot\wedge(D_{[k]}^n-1)\big)\Big)f(\#\Pi^n_i(D_{[k]}^n),1\leq i\leq b){\mathbf{1}}_{\{[k]\cap
      \Pi^n(D_{[k]}^n)=\pi'\}}\Big]}\\ & =&\sum_{r'>
  0}\mathbb E\bigg[\frac{(X_n(r'-1)-1)_{k-1}}{(n-1)_{k-1}}F\big(X_n(\cdot\wedge
  (r'-1))\big) \, p_{X_n(r'-1)}(f(\#\pi_i,1\leq i\leq
  b){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}})\bigg]\end{aligned}$$

<span>**Proof.** </span>We first consider an expression of a more general form. For non-negative functions $G,g$, we have, using the Markov property at time $r'-1$ in the second step, $$\begin{aligned}
\lefteqn{\mathbb E\Big[G\big(\Pi^n(\cdot\wedge(D_{[k]}^n-1))\big)
    g\big(\Pi^n_{(1)}(D_{[k]}^n-1)\cap\Pi^n(D_{[k]}^n)\big)\Big]}\\ &=&\sum_{r'>
  0}\mathbb E\Big[G\big(\Pi^n(\cdot\wedge(r'-1))\big){\mathbf{1}}_{\{[k]\subset
    \Pi^n_{(1)}(r'-1)\}}g\big(\Pi^n_{(1)}(r'-1)\cap\Pi^n(r')\big){\mathbf{1}}_{\{[k]\cap\Pi^n(r')\neq
    \{[k]\}\}}\Big]\\ &=&\sum_{r'>0}\mathbb E\Big[G\big(\Pi^n(\cdot\wedge(r'-1))\big){\mathbf{1}}_{\{[k]\subset
    \Pi^n_{(1)}(r'-1)\}}p_{\Pi^n_{(1)}(r'-1)}(g(\pi){\mathbf{1}}_{\{[k]\cap
    \pi\neq \{[k]\}\}})\Big]\end{aligned}$$ Specializing this formula to $G$ depending only on $X_n$ and $g(\pi)=f(\#\pi_1,\ldots,\#\pi_b){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}$, and using obvious exchangeability properties, we obtain $$\begin{aligned}
\lefteqn{\mathbb E\Big[F\big(X_n(\cdot\wedge(D_{[k]}^n-1))\big)
    f\big(\#\Pi^n_i(D_{[k]}^n),1\leq i\leq b\big){\mathbf{1}}_{\{[k]\cap
      \Pi^n(D_{[k]}^n)=\pi'\}}\Big]}\\ & =&\sum_{r'>
  0}\mathbb E\Big[F\big(X_n(\cdot\wedge(r'-1))\big)
  p_{X_n(r'-1)}(f(\#\pi_i,1\leq i\leq b){\mathbf{1}}_{\{ \pi|_{[k]}=\pi'
    \}}){\mathbf{1}}_{\{[k]\subset \Pi^n_{(1)}(r'-1)\}}\Big]\end{aligned}$$ All the terms in the expectation depend on $(X_n(r),0\leq r\leq
r'-1)$, except the last one which is a function of $\Pi^{n}_{(1)}(r'-1)$. But by Lemma \[sec:exch-part-finite-1\] (in fact, the variant used in the proof of Lemma \[sec:self-simil-fragm-5\]), $$\mathbb P\big([k]\subset \Pi^n_{(1)}(r'-1)\, \big|\, (X_n(r),0\leq r\leq
r'-1)\big) =\frac{(X_n(r'-1)-1)_{k-1}}{(n-1)_{k-1}}\, ,$$ giving the result.

In the sequel, $\Pi(\cdot)$ will denote a continuous-time self-similar fragmentation with characteristic pair $(-\gamma,\nu)$, and $D_k,k\geq 1$ will be defined as in Section \[sec:self-simil-fragm-1\].

\[sec:prel-conv-lemm-3\] Under assumption <span>**(H')**</span>, it holds that $$\Big(\frac{X_n(\lfloor a_n t\rfloor)}{n}, t\geq
0\Big)\underset{n\to\infty}{\overset{(d)}{\longrightarrow}}
(|\Pi_{(1)}(t)|,t\geq 0)\, ,$$ in distribution for the Skorokhod topology, jointly with the convergence $$\frac{1}{a_n}D^n_{1}
\underset{n\to\infty}{\overset{(d)}{\longrightarrow}}D_1\, .$$

<span>**Proof.** </span>For $n> k\geq 1$, let $p_{n,k}=\mathbb P(X_n(1)=k)$. Note that the process $X_n$ is a non-increasing Markov chain started from $n$, with probability transitions $p_{i,j}, 1 \leq j \leq i$. Then by a simple exchangeability argument, $$p_{n,k}= \sum_{\pi \in {\mathcal{P}}_{[n]}} p_n(\pi)m_k(\pi)\frac{k}{n}
=\sum_{\lambda \in {\mathcal{P}}_{n}} q_n(\lambda)m_k(\lambda)\frac{k}{n}, \quad 1 \leq k \leq n,$$ where $m_k(\pi)=m_k(\lambda(\pi))$ is the number of blocks of $\pi$ with size $k$. Consider the associated generating function for $x \geq 0$ $$F_n(x)=\sum_{k=1}^{n}
\left(\frac{k}{n}\right)^xp_{n,k}=\sum_{\lambda \in {\mathcal{P}}_{n}}
q_n(\lambda)\sum_{k=1}^{n}
m_k(\lambda)\Big(\frac{k}{n}\Big)^{x+1}=\sum_{\lambda \in {\mathcal{P}}_{n}}
q_n(\lambda) \sum_{i\geq 1}\Big(\frac{\lambda_i}{n}\Big)^{x+1}\, .$$ Hence, $1-F_n(x)= {\overline}{q}_n(f)$, where $f({\mathbf{s}})=1-\sum_{i\geq 1}s_i^{x+1}$, and by <span>**(H')**</span>, $$a_n(1-F_n(x))\underset{n\to\infty}{\longrightarrow}
\int_{{\mathcal{S}^{\downarrow}}}\Big(1-\sum_{i\geq 1} s_i^{x+1}\Big) \nu({\mathrm{d}}{\mathbf{s}})\, .$$ This is exactly what we need to use @HaMi09 [Theorem 1], stating that $(n^{-1}X_n(\lfloor a_n t\rfloor), t\geq 0)$ converges in distribution to the self-similar Markov process $\exp(-\xi_{\tau(\cdot)})$, as defined around Proposition \[sec:self-simil-fragm-3\]. Moreover, this convergence holds jointly with the convergence of absorption times at $1$, so $a_n^{-1}D_{1}^n$ converges to the absorption time at $0$ of $\exp(-\xi_{\tau(\cdot)})$. By Proposition \[sec:self-simil-fragm-3\], the process $\exp(-\xi_{\tau(\cdot)})$ has same distribution as $(|\Pi_{(1)}(t)|,t\geq 0)$, which reaches $0$ for the first time at time $D_1$. Hence the result.

Finally, the combination of the last two lemmas gives the last of our preliminary ingredients.

\[sec:prel-conv-lemm-4\] The following joint convergence in distribution holds: $$\left(\frac{D_k^n}{a_n},[k]\cap\Pi^n(D_k^n),
\left(\frac{\#\Pi^n_{(i)}(D_k^n)}{n},i\in
    [k]\right)\right)\underset{n\to\infty}{\overset{(d)}\longrightarrow}
    \Big(D_k,[k]\cap \Pi(D_k),(|\Pi_{(i)}(D_k)|,i\in
        [k])\Big)\, .$$

<span>**Proof.** </span>Let $\pi'\in {\mathcal{P}}_k$ have $b\geq 2$ blocks, and $f,g:(0,\infty)\to{\mathbb{R}},h:(0,\infty)^b\to{\mathbb{R}}$ be continuous functions with compact support. Then by Lemma \[sec:prel-conv-lemm-2\], $$\begin{aligned}
\lefteqn{\mathbb E\Big[f\Big(\frac{
      D_k^n}{a_n}\Big)g\Big(\frac{X_n(D_k^n-1)}{n}\Big)
    h\Big(\frac{\#\Pi^n_i(D_k^n)}{X_n(D_k^n-1)},1\leq i\leq
    b\Big){\mathbf{1}}_{\{[k]\cap\Pi^n(D_k^n)=\pi'\}}\Big]}\\ &=&\sum_{r'>0}f\Big(\frac{r'}{a_n}\Big)
\mathbb E\bigg[\frac{(X_n(r'-1)-1)_{k-1}}{(n-1)_{k-1}}g\Big(\frac{X_n(r'-1)}{n}\Big)
  p_{X_n(r'-1)}\Big(h\Big(\frac{\#\pi_i}{X_n(r'-1)},1\leq i\leq
  b\Big){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}\Big)\bigg]\\ &=&\frac{1}{a_n}
\sum_{r'>0}f\Big(\frac{r'}{a_n}\Big) \mathbb E\bigg[\Phi(n,X_n(r'-1))
  g\Big(\frac{X_n(r'-1)}{n}\Big)\Psi(X_n(r'-1))\bigg]\\ &=&\int_{1/a_n}^\infty
f\Big(\frac{\lfloor a_nu\rfloor}{a_n} \Big){\mathrm{d}}u\,
\mathbb E\bigg[\Phi(n,X_n(\lfloor a_nu\rfloor-1)) g\Big( \frac{X_n(\lfloor a_n
    u\rfloor-1)}{n}\Big) \Psi(X_n(\lfloor a_n u \rfloor-1))\bigg]\end{aligned}$$ where $$\Phi(n,x)=\frac{(x-1)_{k-1}}{(n-1)_{k-1}}\frac{a_n}{a_{x}}
\underset{(n,x/n)\to(\infty,c)}{\longrightarrow} c^{k-1-\gamma}\, ,$$ and $$\Psi(m)=a_m p_m\Big(h\Big(\frac{\#\pi_i}{m},1\leq i\leq
b\Big){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}\Big)\, .$$ Note that the Potter's bounds for regularly varying functions @BGT [Th.1.5.6.] imply that $\Phi(n,x) \leq C\left( \frac{x}{n}\right)^{k-1-\gamma-1}$ for all $n \geq x \geq A$ for some finite positive constants $C,A$. In particular there exists some $n_0$ such that $\sup_{n \geq n_0, 0<x
  \leq n}\Phi(n,x) g(x/n)<\infty$ (since $g$ is null in a neighborhood of 0). The joint use of Lemmas \[sec:prel-conv-lemm-1\] and \[sec:prel-conv-lemm-3\] entails by dominated convergence that the expectation term in the integral converges to (note that the quantities $|\pi_i|,1\leq i\leq b$ are all a.e. positive on $\{\pi|_{[k]}=\pi'\}$ under $\kappa_\nu$) $$\mathbb E\bigg[|\Pi_{(1)}(u)|^{k-1-\gamma}g(|\Pi_{(1)}(u)|)
\int_{{\mathcal{P}}_{\mathbb{N}}}\kappa_\nu({\mathrm{d}}\pi)h(|\pi_i|,1\leq i\leq
b){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}\bigg]\, ,$$ and since $f,g,h$ are compactly supported, the whole integral converges to $$\int_0^\infty f(u){\mathrm{d}}u
\mathbb E\bigg[|\Pi_{(1)}(u)|^{k-1-\gamma}g(|\Pi_{(1)}(u)|)
  \int_{{\mathcal{P}}_{\mathbb{N}}}\kappa_\nu({\mathrm{d}}\pi)h(|\pi_i|,1\leq i\leq
  b){\mathbf{1}}_{\{\pi|_{[k]}=\pi'\}}\bigg],$$ which, by Proposition \[sec:poiss-constr-homog-1\], equals $$\mathbb E\bigg[f(D_k)g(|\Pi_{(1)}(D_k-)|)h\Big(\frac{|\Pi_i(D_k)|}{
    |\Pi_{(1)}(D_k-)|},1\leq i\leq b\Big){\mathbf{1}}_{\{[k] \cap
    \Pi(D_k)=\pi'\}}\bigg]\, .$$ It is now easy to conclude, since $|\Pi_i(D_k)|>0$ almost-surely.

Convergence of finite-dimensional marginals {#sec:conv-finite-dimens}
-------------------------------------------

The first step in the proof of Theorem \[sec:main-result-1\] is the following result on reduced trees $T_C^B$ of Section \[sec:discrete-model\].

\[sec:conv-finite-dimens-1\] Let $B\subset {\mathbb{N}}$ be finite. Under assumption <span>**(H')**</span>, we have the following convergence in distribution in ${\mathscr{T}_{{\rm w}}}$: $$\frac{1}{a_n}T_{[n]}^B
\underset{n\to\infty}{\overset{(d)}{\longrightarrow}}
\mathcal{R}({\mathcal{T}}_{\gamma,\nu},B)\, .$$

<span>**Proof.** </span>We use an induction argument on the cardinality of $B$. For $B=\{i\}$, one can assume by exchangeability (as soon as $n\geq i$) that $B=\{1\}$, and in this case, the reduced tree is $T_{[n]}^B=(\varnothing,D_1^n)$, while $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},\{1\})=(\varnothing,D_1)$ by Proposition \[sec:cont-fragm-trees-2\]. By the second part of Lemma \[sec:prel-conv-lemm-3\], under <span>**(H')**</span>, it holds that $$\frac{D^n_1}{a_n}\underset{n\to\infty}
    {\overset{(d)}{\longrightarrow}}D_1\, .$$ This initializes the induction. Now, assume that Proposition \[sec:conv-finite-dimens-1\] has been proved for every set $B$ with cardinality at most $k-1$, for some $k\geq 2$. We want to show that the same is true of any set of cardinality $[k]$, and by exchangeability, we may assume that $B=[k]$.

We now recall, using Proposition \[sec:discrete-model-1\], that conditionally on $D_k^n=\ell$, $[k]\cap\Pi^n(D_k^n)=\pi'$ having $b\geq 2$ blocks and on $\Pi^n_i(D_k^n)=\pi_i,1\leq i\leq
b$ with respective cardinality $\#\pi_i = n_i$, the tree $T_{[n]}^{[k]}$ has same distribution as $$\langle\theta^{(i)},1\leq i\leq b\rangle_{\ell}\, ,$$ where $\theta^{(i)}$ has same distribution as $T^{\pi'_i}_{\pi_i}$, and these trees are independent.

The joint distribution of $D_k^n,[k]\cap
\Pi^n(D_k^n),(\#\Pi^n_{(i)}(D_k^n),1\leq i\leq k)$ is specified by Lemma \[sec:prel-conv-lemm-2\], and its scaling limit by Lemma \[sec:prel-conv-lemm-4\]. We obtain by the induction hypothesis that jointly with the above convergence, conditionally on $
[k]\cap \Pi^n(D_k^n)=\pi'$, $$\begin{aligned}
\frac{1}{a_n}\theta^{(i)}&=&
\frac{a_{n_i}}{a_n}
\frac{1}{a_{n_i}}
\theta^{(i)}\\ &\underset{n\to\infty}
     {\overset{(d)}{\longrightarrow}}& |\Pi_i(D_k)|^\gamma{\mathcal{T}}^{(i)}\,
     ,\qquad 1\leq i\leq b\, ,\end{aligned}$$ where the ${\mathcal{T}}^{(i)}$ are independent with same laws as $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},\pi'_i)$ respectively. Finally, $a_n^{-1}T^{[k]}_{[n]}$ converges to $$\langle |\Pi_{i}(D_k)|^{\gamma}{\mathcal{T}}^{(i)},1\leq i\leq
b\rangle_{D_k}\, ,$$ and the ${\mathbb{R}}$-tree associated with this tree has same distribution as $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},[k])$ by Proposition \[sec:cont-fragm-trees-2\].

Tightness in the Gromov-Hausdorff topology {#sec:tightness}
------------------------------------------

We now want to improve the convergence of Proposition \[sec:conv-finite-dimens-1\] into a convergence of non-reduced trees for the Gromov-Hausdorff topology. Namely

\[sec:tightn-grom-hausd-1\] Under hypothesis <span>**(H')**</span>, we have the convergence in distribution $$\frac{1}{a_n}T_n\overset{(d)}{\underset{n\to\infty}{\longrightarrow}}
{\mathcal{T}}_{\gamma,\nu}$$ in ${\mathscr{T}}$, for the Gromov-Hausdorff topology.

This will be proved by first showing a couple of intermediate lemmas.

\[sec:tightness-2\] Under assumption <span>**(H')**</span>, we have the convergence in distribution: $$(\Pi^n(\lfloor a_nt\rfloor),t\geq 0)
\overset{(d)}{\underset{n\to\infty}{\longrightarrow}} (\Pi(t),t\geq
0)$$ jointly with $$\Big(\frac{\#\Pi^n_{(i)}(\lfloor a_nt\rfloor)}{n},t\geq
0\Big)\overset{(d)}{\underset{n\to\infty}{\longrightarrow}}
(|\Pi_{(i)}(t )|,t\geq 0)$$ for every $i\geq 1$, all these convergences holding jointly.

<span>**Proof.** </span>The fact that $([k]\cap \Pi^n(\lfloor a_n
t\rfloor),t\geq 0)$ converges in the Skorokhod space to $([k]\cap
\Pi(t),t\geq 0)$ for every $k\geq 1$ is obtained by using an inductive argument similar to that used in the proof of Proposition \[sec:conv-finite-dimens-1\]. We only sketch the argument. The statement is trivial for $k=1$, so we can assume that $k\geq 2$. The process $[k]\cap \Pi^n(\lfloor a_n\cdot\rfloor)$ remains constant equal to $[k]$ up to time $a_n^{-1}D^n_k$, and jumps to the state $\pi'=[k]\cap \pi$, $\pi=\Pi^n(D^n_k)$. By Lemma \[sec:prel-conv-lemm-4\], $a_n^{-1}D^n_k\to D_k$ as $n\to\infty$, and the latter has a diffuse law by Proposition \[sec:poiss-constr-homog-1\].

After time $a_n^{-1}D^n_k$, given $\pi$, the restrictions $\pi'_i\cap
\Pi^n(\lfloor a_n\cdot\rfloor+D^n_k)$ have same distribution as $\pi'_i\cap \Pi^{\pi_i}(\lfloor a_n\cdot\rfloor)$, and are independent. By the induction hypothesis and exchangeability, still conditionally on $\pi$, this converges to $\pi'_i\cap
\Pi^{(i)}(\cdot)$, where $\Pi^{(i)},i\geq 1$ are i.i.d. copies of $\Pi$. Moreover, since the jump times have diffuse laws, two such copies never jump at the same time, from which one concludes that given $\pi$, the process $(\pi'_i\cap \Pi^n(\lfloor
a_nt\rfloor+D^n_k),1\leq i\leq b(\pi'),t\geq 0)$ converges in the Skorokhod space to $(\pi'_i\cap \Pi^{(i)}(t),1\leq i\leq b(\pi'),t\geq
0)$. This concludes the inductive step by plugging the initial constancy interval of the process, with length $a_n^{-1}D^n_k$.

The convergence of $\Pi^n(\lfloor a_n\cdot\rfloor)$ in the Skorokhod space follows, because $d_{\mathcal{P}}([k]\cap \pi,\pi)\leq e^{-k}$ for every $\pi\in {\mathcal{P}}_{\mathbb{N}}$. This shows that $[k]\cap \Pi^n(\lfloor
a_n\cdot\rfloor)$ remains uniformly close to $\Pi^n(\lfloor
a_n\cdot\rfloor)$.

Next, by Lemma \[sec:tightness-1\], it follows that, jointly with this convergence, for every $i\geq 1$, the finite-dimensional marginals of $(n^{-1}\#\Pi^n_{(i)}(\lfloor a_n t\rfloor),t\geq 0)$ converge in distribution to those of $(|\Pi_{(i)}(t)|,t\geq 0)$, at least for times which are not fixed discontinuity times of the limiting process — the set of such points is always countable, and it turns out that there are none in the present case. Since we also know that the laws of the processes $(n^{-1}\#\Pi^n_{(i)}(\lfloor a_n
t\rfloor),t\geq 0)$ are tight when $n$ varies, by Lemma \[sec:prel-conv-lemm-3\] (these processes all have same distribution as $(n^{-1}X_n(\lfloor a_n t\rfloor),t\geq 0)$ by exchangeability), this allows to conclude.

For $k+1\leq
i\leq n$, let $$S_i^n=\inf\{r\geq 0:[k]\cap \Pi^n_{(i)}(r)=\varnothing\}\, ,$$ the first time when the ball indexed $i$ is separated from the $k$ first balls. The random variables $S^n_i,k+1\leq i\leq n$ have same distribution by exchangeability. The strong Markov property at the stopping time $S_i^n$ also shows that conditionally on $\Pi^n_{(i)}(S_i^n)=B$, the process $(B\cap \Pi^n(S_i^n+r),r\geq 0)$ has same distribution as $\Pi^B$. The tree ${\mathsf{t}}_{B\cap
  \Pi^n(S_i^n+\cdot)}$ has thus same distribution as $T_B$, and can be seen as a subtree of $T_{[n]}$, characterized by the fact that this subtree contains the leaf labeled $i$, does not contain any of the leaves labeled by an element of $[k]$, and is the maximal subtree of $T_{[n]}$ with this property. In particular, the Gromov-Hausdorff distance between $T_{[n]}^{[k]}$ and $T_{[n]}$ is at most $$d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\leq \max_{k+1\leq i\leq
  n}\mathrm{ht} \left({\mathsf{t}}_{\Pi^n_{(i)}(S^n_i)\cap \Pi^n(S_i^n+\cdot)}
\right)\, ,$$ where $\mathrm{ht}({\mathsf{t}})$, called the height of ${\mathsf{t}}$, is the maximal height of a vertex in ${\mathsf{t}}$.

Note that if $j\in \Pi^n_{(i)}(S^n_i)$, then $S^n_j=S^n_i$. Therefore, the blocks $\Pi^n_{(i)}(S^n_i), k+1\leq i\leq n$ are either disjoint or equal. Moreover, the partition $\pi$ of $[n]\setminus[k]$ with these blocks is clearly exchangeable. By putting the previous observations together, we obtain by first conditioning on $\pi$, and for every $\eta>0$, $$\label{eq:13}
\mathbb P \left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\geq \eta a_n \right) \leq
\mathbb E\bigg[\sum_{i\geq 1}{\mathsf{P}}^q_{\#\pi_i}(\mathrm{ht}\geq \eta a_n)\bigg]\,
,\qquad \eta>0\, .$$ At this point, we need the following uniform estimate for the height of a ${\mathsf{P}}_n$-distributed tree, which is the key lemma of this section.

\[sec:tightn-grom-hausd\] Assume <span>**(H')**</span>. Then for all $p>0$, there exists a finite constant $C_p$ such that: $${\mathsf{P}}_n^q\Big(\mathrm{ht} \geq x a_n \Big) \leq
\frac{C_p}{x^p}, \quad \forall x>0, \forall n \geq 1.$$

Before giving the proof of this statement, we end the proof of Proposition \[sec:tightn-grom-hausd-1\]. Using Lemma \[sec:tightn-grom-hausd\] for $p=2/\gamma$ and (\[eq:13\]), we obtain $$\mathbb P \left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\geq \eta
a_n\right) \leq C_{2/\gamma} \eta^{-2/\gamma} \mathbb
E\bigg[\sum_{i\geq 1} \frac{a_{\#\pi_i}^{2/\gamma}}{a_n^{2/\gamma}}\bigg]\, .$$ By the exchangeability of the partition $\pi$ of $[n]\setminus[k]$, note that for every measurable function $f$, $$\mathbb E[f(\#\pi_{(k+1)})]=\frac{1}{n-k}\mathbb
E\bigg[\sum_{i=k+1}^nf(\#\pi_{(i)})\bigg]= \mathbb E\bigg[\sum_{i\geq
    1}\frac{\#\pi_i}{n-k}f(\#\pi_i)\bigg]\, .$$ This finally yields $$\mathbb P\left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]} )\geq \eta
a_n\right) \leq C_{2/\gamma} \eta^{-2/\gamma}\mathbb
E\bigg[\frac{a_{\#\pi_{(k+1)}}^{2/\gamma}(\#\pi_{(k+1)})^{-1}}{a_n^{2/\gamma}n^{-1}}\bigg]\, .$$ Since the sequence $(a_n
^{2/\gamma}n^{-1},n\geq 1)$ is strictly positive and regularly varying at $\infty$ with index 1, we get from the Potter's bounds (@BGT [Th.1.5.6.]) the existence of a finite constant $C$ such that $(a_k^{2/\gamma}k^{-1}) / (a_n
^{2/\gamma}n^{-1}) \leq C \sqrt{k/n}$ for all $1 \leq k \leq n$. Hence, $$\mathbb P\left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]} )\geq \eta
a_n\right) \leq C C_{2/\gamma} \eta^{-2/\gamma}\mathbb
E\bigg[\sqrt{\frac{\#\pi_{(k+1)} }{n}}\bigg]\, .$$ Note that the quantity in the expectation is bounded by 1. By Proposition \[sec:tightness-2\], it holds that $S^n_{k+1}/a_n \to
S_{k+1}$ in distribution as $n\to\infty$, where $S_{k+1}=\inf\{t\geq
0:[k]\cap \Pi_{(k+1)}(t)=\varnothing\}\, .$ This convergence holds jointly with that of $(n^{-1}\#\Pi^n_{(k+1)}(\lfloor a_nt\rfloor),$ $t\geq 0)$ to $(|\Pi_{(k+1)}(t)|,t\geq 0)$ in the Skorokhod space, whence we deduce that $$\limsup_{n\to\infty} \mathbb
P\left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\geq \eta a_n\right) \leq C C_{2/\gamma} \eta^{-2/\gamma} \mathbb E\left[
  \sqrt{|\Pi_{(k+1)}(S_{k+1}-)}|\right]\, .$$ Let $S'_{k+1}=\inf\{t\geq 0:\{2,3,\ldots,k+1\}\cap
\Pi_{(1)}(t)=\varnothing\}$, then by exchangeability, $$\limsup_{n\to\infty} \mathbb
P\left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\geq \eta a_n\right) \leq C C_{2/\gamma} \eta^{-2/\gamma} \mathbb
E\left[\sqrt{|\Pi_{(1)}(S'_{k+1}-)}|\right].$$ Since the quantity in the expectation goes to $0$ a.s. as $k\to\infty$ and is bounded (indeed $S'_k\uparrow D_{\{1\}}$ a.s. and $\Pi_{(1)}(D_{\{1\}}-)=0$ by (\[eq:1\]) and Proposition \[sec:self-simil-fragm-3\]), we conclude that for every $\eta>0$, $$\label{eq:25}
\lim_{k\to\infty}\limsup_{n\to\infty} \mathbb
P\left(d_{\mathrm{GH}}(T_{[n]}^{[k]},T_{[n]})\geq \eta a_n\right)=0\, .$$ It is now easy to conclude from this, Proposition \[sec:conv-finite-dimens\] and the fact that ${\cal
  R}({\mathcal{T}}_{\gamma,\nu},[k])$ converges is distribution in $({\mathscr{T}},d_{\mathrm{GH}})$ to ${\mathcal{T}}_{\gamma,\nu}$ as $k\to\infty$ (@HM04), using @billingsley99 [Theorem 4.2]:

Let $X_n,X,X_n^k,X^k$ be random variables in a metric space $(M,d)$. We assume that for every $k$, we have $X_n^k\to X^k$ in distribution as $n\to\infty$, and $X^k\to X$ in distribution as $k \to
\infty$. Finally, we assume that for every $\eta>0$, $$\lim_{k\to\infty}\limsup_{n\to\infty}\mathbb P(d(X_n^k,X_n)>\eta)=0\, .$$ Then $X_n\to X$ in distribution as $n\to\infty$.

**Proof of Lemma \[sec:tightn-grom-hausd\].** Note that if the statement holds for some $p>0$, it then holds for all $q
\in (0,p)$. We can therefore assume in the following that $p>1/\gamma$ and we let $\varepsilon >0$ be so that $p(\gamma-\varepsilon)>1$. The main idea of the proof is to proceed by induction on $n$, using the Markov branching property. We start with some technical preliminaries.

$\bullet$ First note that $\mathsf
          {E}_n^q[\mathrm{ht}^r]<\infty$ for all $r>0$ and all $n \geq
          1$. This can easily be proved by induction on $n$ ($r$ being fixed) using the Markov branching property, and the facts that $q_n((n))<1$ and that $H_1=1$ almost-surely.

$\bullet$ Second, we replace the sequence $(a_n,n\geq 1)$ by a 'nicer' sequence $(\tilde a_n, n\geq 1)$ such that $\tilde a_n \sim
\ a_n$, i.e. $a_n/\tilde a_n \rightarrow 1$ as $n \rightarrow \infty$ (this step is trivial when $a_n=n^{\gamma}$; we then take $\tilde a_n
=a_n$). Since $(a_n, n\geq 1)$ is regularly varying at $\infty$, it is well-known (see @BGT [Theorem 1.3.1]) that it can be written in the form $$a_n=c(n)\exp\left(\int_1^n \varepsilon(u) \mathrm du /u
\right), \quad n\geq 1,$$ where $c(n) \rightarrow c>0$ as $n \rightarrow \infty$ and $\varepsilon$ is a measurable function that converges to $0$ as $\infty$. Define $$\tilde a_n=c\exp\left(\int_1^n \varepsilon(u) \mathrm du /u
\right), \quad n\geq 1.$$ We claim that there exists an integer $n_{\varepsilon} \geq 1$ such that for $n
\geq n_{\varepsilon}$, $$\label{bonnemajo}
\frac{\tilde{a}_k}{ \tilde{a}_n}\leq \left( \frac{k}{n}
\right)^{\gamma-\varepsilon} \quad \forall 1 \leq k \leq n.$$ Indeed, let $u_{\varepsilon}$ be such that $| \varepsilon(u) | \leq
\varepsilon$ for all $u \geq u_{\varepsilon}$. For $n \geq k \geq u_
           {\varepsilon}$, we have $$\bigg |\int_k^n -\varepsilon(u) \mathrm du /u \bigg | \leq
\varepsilon \int_k^n \mathrm du /u \leq \varepsilon \ln(n/k)$$ hence $$\frac{\tilde{a}_k
}{\tilde{a}_n
} =\left(
\frac{k}{n} \right)^{\gamma} \exp\left(-\int_k^n \varepsilon(u)
\mathrm du /u \right) \leq \left( \frac{k}{n}
\right)^{\gamma-\varepsilon}.$$ Besides $\sup_{k \in \{1,..., \lfloor u_{\varepsilon}  \rfloor \}} \tilde a_k k^{\varepsilon-\gamma}
/(\tilde a_n n^{\varepsilon-\gamma}) \leq 1$ for all $n$ large enough (say $n \geq n'_{\varepsilon}$). Hence $
\tilde{a}_k/\tilde{a}_n \leq \left( k/n \right)^{\gamma-\varepsilon} $ for all $n \geq n_{\varepsilon}=\max(n'_{\varepsilon},
u_{\varepsilon})$ and all $1 \leq k \leq n$.

$\bullet$ Since $\tilde a_n >0$ for all $n \geq 1$ and $\tilde a_n \sim a_n$, there exists some $c>0$ such that $
a_n \geq c \tilde a_n$ for all $n \geq
1$. It is therefore sufficient to prove the existence of a finite $C_p$ (a priori different from the one in the statement of the lemma) such that $$\label{eqtilde}
{\mathsf{P}}^q_n\left(\mathrm{ht} \geq x \tilde{a}_n
\right) \leq
\frac{C_p}{x^p}, \quad \forall x>0 \text{ and } n \geq 1,$$ to finish the proof of the lemma. In order to prove (\[eqtilde\]), we will use the integer $n_{\varepsilon}$ introduced around (\[bonnemajo\]) and we will further assume, taking $n_{\varepsilon}$ larger if necessary, that $\tilde{a}_n \geq 1$ for every $ n \geq
n_{\varepsilon}$. Introduce now $0<C^1_p<1$ such that $$(1-u)^{-p} \leq 1+2pu, \quad \forall 0 \leq u \leq C^1_p.$$ Using **(H')** and the fact that $q_n((n))<1$ for all $n \geq 1$, there exists also $C^2_p>0$ such that $$\label{C2}
\tilde{a}_n
\sum_{\lambda \in \mathcal P_{n}}
q_n(\lambda) \left( 1-\sum_{i=1}^{p(\lambda)} \left( \frac
{\lambda_i}{n}\right)^{(\gamma-\varepsilon) p} \right) \geq C^2_p,
\quad \forall n \geq 1$$ (recall that $(\gamma-\varepsilon)p>1$ and $\tilde a_n>0$ for all $n \geq 1$). Last we let $$C_p(n_{\varepsilon}):=\max_{1 \leq n \leq
  n_{\varepsilon}}
\left(\mathsf{E}_n^q[\mathrm{ht}^p]/\tilde{a}_n^p\right)<\infty$$ and we set $$C_p:=\max
\left(C_p(n_{\varepsilon}),\left(1/C^1_p,2p/C^2_p\right)^p
\right)<\infty.$$ Our goal is to prove by induction on $n \geq 1$ that $$\tag{$\mathrm{A}_n$} {\mathsf{P}}_n^q(\mathrm{ht} < x \tilde{a}_n) \geq
1-\frac{C_p}{x^p}, \qquad \mbox{ for every } x>0,$$ Clearly, $({\mathrm A_n})$ holds for all $n \leq n_{\varepsilon}$ since $C_p \geq C_p(n_{\varepsilon})$ and ${\mathsf{P}}_n^q (\mathrm{ht} \geq x
\tilde{a}_n ) \leq \mathsf{E}_n^q[\mathrm{ht}^p]/(x\tilde{a}_n )^p$. Now assume that $(\mathrm A_k)$ is satisfied for all $k \leq n-1$ for some $n \geq n_{\varepsilon}$. For all $0 < x \leq C_p^{1/p}$, the expected inequalities in $({\mathrm A_n})$ are obvious, so it remains to prove them for $x> C_p^{1/p}$. To get $({\mathrm A_n})$, we will prove by induction on $i \in \mathbb N$ that $$\tag{$\mathrm{A}_{n,i}$} {\mathsf{P}}_n^q(\mathrm{ht} < x \tilde{a}_n ) \geq
1-\frac{C_p}{x^p}\, , \qquad \mbox{ for every } x \in
\left(0,\frac{i}{\tilde{a}_n } \right)\, ,$$ which will obviously lead to $(\mathrm A_n)$. Note first that $(\mathrm A_{n,1})$ holds since $1/\tilde{a}_n \leq 1 \leq
 C_p^{1/p}$. Assume next that $(\mathrm A_{n,i})$ is true, and fix $x
 \in (0,(i+1)/\tilde{a}_n )$. Using the Markov branching property and the fact that $(\mathrm A_k)$, holds for every $k \leq n-1$, as well as $(\mathrm A_{n,i})$, we get $$\begin{aligned}
{\mathsf{P}}_n^q(\mathrm{ht} < x \tilde{a}_n )&=& \sum_{\lambda \in \mathcal
  P_n} q_n(\lambda) \prod_ {i=1}^{p(\lambda)}
{\mathsf{P}}_{\lambda_i}^q(\mathrm{ht} < x \tilde{a}_n -1) \\ &\geq &
\sum_{\lambda \in \mathcal P_n} q_n(\lambda) \prod_{i=1}^{p(\lambda)}
\left( 1-\frac{C_p \tilde{a}_{\lambda_i}^p}{(x\tilde{a}_n
  -1)^p}\right)^+ \\ &\geq& \sum_{\lambda \in \mathcal P_n}
q_n(\lambda) \left( 1- \sum_{i=1}^{p(\lambda)}\frac{C_p
 \tilde{a}_{\lambda_i}^p}{(x\tilde{a}_n-1)^p} \right),\end{aligned}$$ using the notation $r^+=\max(r,0)$ and that for all sequences of non-negative terms $b_i, i \geq 1$, $\prod_{i=1}^m (1-b_i)^+ \geq 1-
\sum_{i=1}^m b_i$, for every $m \geq 1$. We can assume that $x >
C_p^{1/p}$ since $(\mathrm{A}_n)$ holds otherwise. In particular, $x\tilde{a}_n \geq x >
1/C^1_p>1$. Therefore, $$\frac{1}{(x\tilde{a}_n-1)^p}=\frac{1}{(x\tilde{a}_n)^p
  (1-1/(x\tilde{a}_n))^p} \leq \frac{1+2p/
  (x\tilde{a}_n)}{(x\tilde{a}_n)^p},$$ and then $$\begin{aligned}
&& {\mathsf{P}}_n^q(\mathrm{ht} < x \tilde{a}_n) \\ & \geq & \sum_{\lambda \in
    \mathcal P_n} q_n(\lambda) - \frac{C_p}{x^{p}}\sum_{\lambda \in
    \mathcal P_n} q_n(\lambda) \sum_{i=1} ^{p(\lambda)}
  \Big(\frac{\tilde{a}_{\lambda_i}}{\tilde{a}_n}\Big)^p
  -\frac{2pC_p}{x^{p+1}\tilde{a}_n}\sum_ {\lambda \in
    \mathcal P_n} q_n(\lambda)
  \sum_{i=1}^{p(\lambda)}\Big(\frac{\tilde{a}_{\lambda_i}}{\tilde{a}_n}\Big)^p
  \\ &\underset{\text{by }(\ref{bonnemajo})}\geq& 1 -
  \frac{C_p}{x^{p}}\sum_{\lambda \in \mathcal P_n} q_n(\lambda)
  \sum_{i=1} ^{p(\lambda)} \Big(\frac{\lambda_i
        }{n}\Big)^{(\gamma-\varepsilon) p}
        -\frac{2pC_p}{x^{p+1}\tilde{a}_n}\sum_ {\lambda
          \in \mathcal P_n} q_n(\lambda) \sum_{i=1}^{p(\lambda)}
        \Big(\frac{\lambda_i}{n}\Big)^{(\gamma-\varepsilon) p}
          \\&\geq& 1-\frac{C_p}{x^p} + \frac{C_p}{x^{p}}\sum_{\lambda
            \in \mathcal P_n} q_n(\lambda) \left( 1-
          \sum_{i=1}^{p(\lambda)}
         \Big(\frac{\lambda_i
        }{n}\Big)^{(\gamma-\varepsilon) p}
\right)
          -\frac{2pC_p}{x^{p+1}\tilde{a}_n}
\sum_{\lambda \in \mathcal P_n} q_n(\lambda)
          \sum_{i=1}^{p(\lambda)}\Big(\frac{\lambda_i
        }{n}\Big)^{(\gamma-\varepsilon) p}\, .\end{aligned}$$ We then use (\[C2\]) and the fact that $\sum_{i=1}^{p(\lambda)}(\lambda_i/n)^{(\gamma-\varepsilon) p} \leq 1$ (since $(\gamma-\varepsilon) p>1$) to get $${\mathsf{P}}_n^q(\mathrm{ht} < x \tilde a_n  ) \geq
1-\frac{C_p}{x^p} + \frac{C_p}{x^{p}\tilde{a}_n} \left(
C^2_p-\frac{2p}x \right).$$ By assumption, $x >C_p^{1/p} \geq 2p/C^2_p$, hence $${\mathsf{P}}_n^q(\mathrm{ht} < x \tilde{a}_n) \geq 1-\frac{C_p}{x^p} \qquad
\mbox{ for every } x \in \left(0,\frac{i+1}{\tilde{a}_n} \right)\, ,$$ as wanted.

Incorporating the measure {#sec:incorp-meas}
-------------------------

We now finish the proof of Theorem \[sec:main-result-1\], by improving the Gromov-Hausdorff convergence of Proposition \[sec:tightn-grom-hausd-1\] to a Gromov-Hausdorff-Prokhorov convergence, when the uniform measure $\mu_n=\mu_{\partial T_n}$ on leaves is added to $T_n$ in order to view it as an element of ${\mathscr{T}_{{\rm w}}}$ rather than ${\mathscr{T}}$.

We will use the fact @EW [Lemma 2.3] that the convergence in distribution of $a_n^{-1}T_n$ as $n\to\infty$ in ${\mathscr{T}}$ entails that the laws of the random variables $a_n^{-1}T_n$, form a tight sequence of probability measures on ${\mathscr{T}_{{\rm w}}}$. Therefore, it suffices to identify the limit as ${\mathcal{T}}_{\gamma,\nu}$.

So let us assume that $a_n^{-1}T_n$ converges to $({\mathcal{T}}',d',\rho',\mu')\in {\mathscr{T}_{{\rm w}}}$ in distribution, when $n\to\infty$ along some subsequence. Let $L_1^n,L_2^n,\ldots,L_k^n$ be $k$ i.i.d. uniform leaves of $T_n$. Conditionally given the event that these leaves are pairwise distinct, which occurs with probability going to $1$ as $n\to\infty$ with $k$ fixed, these leaves are just a uniform sample of $k$ distinct leaves of $T_n$, so by Lemma \[sec:mark-branch-trees-2\] and exchangeability, the subtree of $T_n$ spanned by the root and the leaves $L_1^n,\ldots,L_k^n$ has same distribution as $T_{[n]}^{[k]}$. By Proposition \[sec:conv-finite-dimens-1\], we know that $a_n^{-1}T_{[n]}^{[k]}$ converges in distribution to $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},[k])$ in ${\mathscr{T}}$.

A $k$-pointed compact metric space is an object of the form $((X,d),x_1,\ldots,x_k)$ where $(X,d)$ is a compact metric space and $x_1,\ldots,x_k\in X$. The set of $k$-pointed metric spaces can be endowed with the $k$-pointed Gromov-Hausdorff distance $$d_{\mathrm{GH}}^{(k)}\Big(\big((X,d),x_1,\ldots,x_k\big),
\big((X',d'),x'_1,\ldots,x'_k\big)\Big) =\inf_{\phi,\phi'}\max_{1\leq
  i\leq k}{\mathrm{dist}}(\phi(x_i),\phi'(x'_i))\vee
{\mathrm{dist}}_{\mathrm{H}}(\phi(X),\phi'(X'))\, ,$$ where, as in the definition of the Gromov-Hausdorff distance, the infimum is over isometric embeddings $\phi,\phi'$ of $X,X'$ into some common space $(M,{\mathrm{dist}})$. Note in particular that $d_{\mathrm{GH}}^{(1)}=d_{\mathrm{GH}}$. Now, the fact that $a_n^{-1}T_n$ converges to $({\mathcal{T}}',d',\rho',\mu')$ in ${\mathscr{T}_{{\rm w}}}$ implies that the $k+1$-pointed space $(a_n^{-1}T_n,\rho,L_1^n,\ldots,L_k^n)$ converges in distribution to $({\mathcal{T}}',\rho',L_1,\ldots,L_k)$, where $L_1,\ldots,L_k$ are i.i.d. with law $\mu'$ conditionally on the latter. See @miermont09 [Proposition 10] for a proof and further properties of the $k$-pointed Gromov-Hausdorff distance, which in particular is Polish.

If $(T,d,\rho)$ is a rooted ${\mathbb{R}}$-tree and $x_1,\ldots,x_k\in T$, the union of geodesics from $\rho$ to the $x_i$'s $$R(T,x_1,\ldots,x_k)=\bigcup_{i=1}^k[[\rho,x_i]]$$ is in turn an ${\mathbb{R}}$-tree rooted at $\rho$ with at most $k$ leaves, called the subtree of $T$ spanned by $x_1,\ldots,x_k$ (the role of the root being implicit).

\[sec:incorp-meas-1\] Let $({\cal A}_n,d_n,\rho_n),n\geq 1$ be a sequence of rooted ${\mathbb{R}}$-trees and $x^n_1,\ldots,x^n_k$ be $k$ points in ${\cal A}_n$, such that $(({\cal A}_n,d_n),\rho_n,x^n_1,\ldots,x_n^k)$ converges for the $k+1$-pointed Gromov-Hausdorff distance to a limit $(({\cal A},d),\rho,x_1,\ldots,x_k)$. Then the subtree $R({\cal A}_n,x_1^n,\ldots,x_k^n)$ converges in $\mathscr{T}$ to the subtree $R({\cal A},x_1,\ldots,x_k)$.

We will prove this lemma at the end of the section. By using the Skorokhod representation theorem, we may assume that the convergence of $(a_n^{-1}T_n,\rho,L_1^n,\ldots,L_k^n)$ to $({\mathcal{T}}',\rho',L_1,\ldots,L_k)$ holds almost-surely. This, together with Lemma \[sec:incorp-meas-1\] and the discussion at the beginning of this section, implies the joint convergence in distribution in ${\mathscr{T}}$ of $a_n^{-1}T_{[n]},a_n^{-1}T_{[n]}^{[k]}$ to ${\mathcal{T}}',{\mathcal{T}}'_k$, still along the appropriate subsequence, where ${\mathcal{T}}'_k$ is the subtree of ${\mathcal{T}}'$ spanned by $L_1,\ldots,L_k$. In particular, this identifies the law of ${\mathcal{T}}'_k$ as that of $\mathcal{R}({\mathcal{T}}_{\gamma,\nu},[k])$. When $k\to\infty$, we already stressed that the latter trees converge (in distribution in ${\mathscr{T}_{{\rm w}}}$, with the uniform measure $\mu_k$ on the set of its $k$ leaves) to ${\mathcal{T}}_{\gamma,\nu}$. On the other hand, ${\mathcal{T}}'_k$ converges a.s. to $({\mathcal{T}}'',d',\rho',\mu')$ in ${\mathscr{T}_{{\rm w}}}$ as $k\to\infty$, where ${\mathcal{T}}''$ is the closure in ${\mathcal{T}}'$ of $$\bigcup_{i=1}^\infty[[\rho',L_i]]\, .$$ But the joint convergence of $T_{[n]},T_{[n]}^{[k]}$ in ${\mathscr{T}}$ along some subsequence and (\[eq:25\]) imply that for every $\eta>0$, $\lim_{k\to\infty}\mathbb{P}(d_{\mathrm{GH}}({\mathcal{T}}'_k,{\mathcal{T}}')>\eta)=0$. So ${\mathcal{T}}''={\mathcal{T}}'$ a.s., entailing that $({\mathcal{T}}',d',\rho',\mu')$ has same law as ${\mathcal{T}}_{\gamma,\nu}$. This identifies the limit of $a_n^{-1}T_n$ in ${\mathscr{T}_{{\rm w}}}$ as ${\mathcal{T}}_{\gamma,\nu}$, ending the proof of Theorem \[sec:main-result-1\].

It remains to prove Lemma \[sec:incorp-meas-1\]. We only sketch the argument, leaving the details to the reader. We use induction on $k$. For $k=1$, the subtree $R({\cal A}_n,x^n_1)$ is isometric to a real segment $[0,d_n(\rho_n,x^n_1)]$ rooted at $0$. The $2$-pointed convergence of $(({\cal A}_n,d_n),\rho_n,x^n_1)$ to $(({\cal A},d),\rho,x_1)$ entails that $d_n(\rho_n,x^n_1)$ converges to $d(\rho,x_1)$, hence that $R({\cal A}_n,x^n_1)$ converges to $[0,d(\rho,x_1)]$ rooted at $0$, which is isometric to $R({\cal A},x_1)$.

For the induction step, we use the general fact that if ${\cal A}$ is a rooted ${\mathbb{R}}$-tree and $x_1,\ldots,x_k,x_{k+1}\in {\cal A}$, then the distance between $x_{k+1}$ and the subtree of ${\cal A}$ spanned by $x_1,\ldots,x_k$ is equal to $$\delta_{k+1}=\min_{1\leq i\leq
  k}\Big(\frac{d(x_{k+1},x_i)+d(x_{k+1},\rho)-d(x_i,\rho)}{2}\Big)\,
.$$ Moreover, if $i\in \{1,2,\ldots,k\}$ is an index that realizes this minimum, then the branchpoint $x_{k+1}\wedge x_i$ is at distance $\delta_{k+1}$ from $x_{k+1}$ and is the ancestor of $x_i$ at height (i.e. distance from $\rho$) $$h_{k+1}=d(\rho,x_{k+1})-\delta_{k+1}\, .$$ Roughly speaking, we get that $R({\cal A},x_1,\ldots,x_{k+1})$ is obtained from $R({\cal A},x_1,\ldots,x_k)$ by grafting a segment with length $\delta_{k+1}$ at the ancestor of $x_i$ with height $h_{k+1}$.

In our particular situation, and with obvious notations, we get that $R({\cal A}_n,x^n_1,\ldots,x^n_{k+1})$ is obtained by grafting a segment with length $\delta_{k+1}^n$ to the ancestor of $x^n_{i_n}$ with height $h_{k+1}^n$, where $i_n$ is some index in $\{1,\ldots,k\}$ that can depend on $n$. Up to extracting, we may assume that $i_n=i$ is constant. The $k+2$-pointed convergence of $(({\cal A}_n,d_n),\rho_n,x^n_1,\ldots,x^n_{k+1})$ to $(({cal A},d),\rho,x_1,\ldots,x_{k+1})$ entails that the $d_n$-distances between elements of $\{\rho_n,x^n_1,\ldots,x^n_{k+1}\}$ converge to the corresponding $d$-distances of elements in $\{\rho,x_1,\ldots,x_k\}$. Consequently, it holds that $\delta_{k+1}^n,h_{k+1}^n$ converge to $\delta_{k+1},h_{k+1}$, defined as above. Together with the induction hypothesis stating that $R({\cal A}_n,x^n_1,\ldots,x^n_k)$ converges in $\mathscr{T}$ to $R({\cal A},x_1,\ldots,x_k)$, this entails easily that $R({\cal A}_n,x^n_1,\ldots,x^n_{k+1})$ converges in $\mathscr{T}$ to the ${\mathbb{R}}$-tree obtained by grafting a segment with length $\delta_{k+1}$ to the ancestor of $x_i$ with height $h_{k+1}$ in $R({\cal A},x_1,\ldots,x_k)$, and this tree is $R({\cal A},x_1,\ldots,x_{k+1})$. The result being independent of the particular value of $i$ (selected by the choice of an extraction), the convergence holds without taking extractions, which concludes the proof.

Proof of Theorem \[sec:main-result-2\] {#proof-theor2}
--------------------------------------

To pass from trees with $n$ vertices (with law ${\mathsf{Q}}_n^q$) to trees with laws of the form ${\mathsf{P}}_n^{q'}$, with $n$ leaves, we introduce a transformation on trees, in which every vertex which is not a leaf is attached to an extra "ghost" neighbor, which is a leaf.

Precisely, if ${\mathbbm{t}}$ is a plane tree, then the modification ${\mathbbm{t}}^\circ$ is defined as $${\mathbbm{t}}^\circ={\mathbbm{t}}\cup \bigcup_{u=(u_1,\ldots,u_k)\in {\mathbbm{t}}\setminus
  \partial{\mathbbm{t}}}\{(u_1,\ldots,u_k,c_u({\mathbbm{t}})+1)\}\, .$$ If we are given a tree rather than a plane tree, then this construction performed on any plane representative a the tree ${\mathsf{t}}$ will yield plane trees in the same equivalence class, which we call ${\mathsf{t}}^\circ$. Note that $$\#\partial{\mathsf{t}}^\circ=\#{\mathsf{t}}\, .$$

We see ${\mathsf{t}}^\circ$ as an element of ${\mathscr{M}_{{\rm w}}}$ (endowed with graph distance and uniform distribution on $\partial{\mathsf{t}}^\circ$), and view ${\mathsf{t}}$ as an element of ${\mathscr{M}_{{\rm w}}}$, by endowing it also with the graph distance, but this time, with the uniform distribution $\mu_{\mathsf{t}}$ on ${\mathsf{t}}$. It is easy to see, using the natural isometric embedding of ${\mathsf{t}}$ into ${\mathsf{t}}^\circ$, that for every $a>0$, $$\label{eq:19}
d_{\mathrm{GHP}}(a{\mathsf{t}},a{\mathsf{t}}^\circ)\leq a\, .$$ Let $(q_n,n\geq 1)$ be, as in Section \[sec:mark-branch-trees-1\], a family of probability distributions respectively on ${\mathcal{P}}_n$, such that $q_1((1))=1$. We introduce the family $q^\circ_n,n\geq 1$ of probability measures respectively on ${\mathcal{P}}_n$ by $q^\circ_1(\emptyset)=1$, and $$q^\circ_{n+1}((\lambda,1))=q_n(\lambda)\, ,\qquad n\geq 1,\lambda\in
{\mathcal{P}}_{n}\, ,$$ where $(\lambda,1)=(\lambda_1,\ldots,\lambda_{p(\lambda)},1)\in {\mathcal{P}}_{n+1}$.

It is then immediate to show by induction that if $T_n$ has law ${\mathsf{Q}}^q_n$, then $T^\circ_n$ has law ${\mathsf{P}}^{q^\circ}_n$, with the notation of Section \[sec:mark-branch-trees\]. We leave this verification to the reader. In view of this and (\[eq:19\]), we see that Theorem \[sec:main-result-2\] is a straightforward consequence of the following statement.

\[sec:proof-theorem-xxx\] If $(q_n,n\geq 1)$ satisfies <span><span>**(H)**</span></span> with either $\gamma\in(0,1)$, or $\gamma=1$ and $\ell(n)\to0$ as $n\to\infty$, then $(q^\circ_n,n\geq 1)$ satisfies ${\rm {\bf (H)}}$, with same fragmentation pair $(-\gamma,\nu)$ and function $\ell$.

<span>**Proof.** </span> Let $f:{{\mathcal{S}^{\downarrow}}}\to {\mathbb{R}}$ be a Lipschitz function with uniform norm and Lipschitz constant bounded by $K$. Let also $g({\mathbf{s}})=(1-s_1)f({\mathbf{s}})$. Then $$\bigg|f\Big(\frac{(\lambda,1)}{n+1}\Big)-f\Big(\frac{\lambda}{n}\Big)\bigg|
\leq K\sum_{i=1}^{p(\lambda)}\frac{\lambda_i}{n(n+1)}+\frac{K}{n+1}
\leq \frac{2K}{n+1}
\, ,$$ so that $$\begin{aligned}
|{\overline}{q}^\circ_{n+1}(g)-{\overline}{q}_n(g)|&\leq& \sum_{\lambda\in
  {\mathcal{P}}_n}q_n(\lambda) \bigg|
\bigg(1-\frac{\lambda_1}{n+1}\bigg)f\Big(\frac{(\lambda,1)}{n+1}\Big)-
\bigg(1-\frac{\lambda_1}{n}\bigg)f\Big(\frac{\lambda}{n}\Big)\bigg|\\ &\leq
&\sum_{\lambda\in
  {\mathcal{P}}_n}q_n(\lambda)\bigg(\frac{K\lambda_1}{n(n+1)}+\frac{2K}{n+1}\bigg)\\ &\leq
& \frac{3K}{n+1}\end{aligned}$$ multiplying both sides by $n^\gamma\ell(n)$, we see that the upper-bound converges to $0$ as $n\to\infty$ under our hypotheses. Since $n^\gamma\ell(n){\overline}{q}_n(g)$ converges to $\nu(g)$ by <span>**(H)**</span>, we obtain the same convergence with ${\overline}{q}^\circ_n$ instead of ${\overline}{q}_n$. This yields the result.

Proof of Proposition \[Propexemple\]
------------------------------------

Recall the notation $\Lambda^{(\mathbf s)}(n)$ for the decreasing sequence of sizes of blocks restricted to $\{1,\ldots, n \}$ of a random variable with painbox distribution $\rho_{\mathbf s}(\mathrm d
\pi)$, with $\mathbf s \in \mathcal S^{\downarrow}$, $\sum_{i \geq
  1}s_i=1$. Recall also that $\Lambda^{(\mathbf s)}(n)/n \rightarrow
\mathbf s$ in $\mathcal S^{\downarrow}$ almost-surely. Now set for $\lambda \in \mathcal P_n$, $$\begin{aligned}
 \tilde q_n(\lambda)&=&n^{-\gamma} \int_{\mathcal S^{\downarrow}} \mathbb P (\Lambda^
{(\mathbf s)}(n)=\lambda ) \mathbf 1_{\{ n^{-\gamma/2} \leq 1- s_1\}} \nu(\mathrm d \mathbf s), \quad 
\lambda \neq (n), \\
 \tilde q_n((n))&=& 1-\sum_{\lambda \in \mathcal P_n, \lambda \neq (n)} \tilde q_n(\lambda).\end{aligned}$$ For $n$ large enough, say $n\geq n_0$, $$0<\sum_{\lambda \in \mathcal
  P_n, \lambda \neq (n)} \tilde q_n(\lambda) \leq n^{-\gamma/2}
\int_{\mathcal S^{\downarrow}} (1-s_1)\nu(\mathrm d \mathbf s)\leq
1,$$ hence $\tilde q_n$ defines a probability distribution on $\mathcal P_n$ such that $\tilde q_n((n))<1$. Then set $q_n=\tilde
q_n$ for $n \geq n_0$ and for $n < n_0$ let $q_n$ be any distribution on $\mathcal P_n$ such that $q_n((n))<1$. Next, consider a continuous function $f : \mathcal
S^{\downarrow} \rightarrow \mathbb R_+$. For $n \geq n_0$, we have $$n^{\gamma}\sum_{\lambda \in \mathcal P_n} q_n(\lambda)
\left(1-\frac {\lambda_1}{n}\right)f\left( \frac{\lambda}{n}\right) =
\int_{\mathcal S^{\downarrow}} \mathbb E\left [\left
  (1-\frac{\Lambda^{(\mathbf s)}_1(n)}{n} \right) f\left(\frac{\Lambda^
    {(\mathbf s)}(n)}{n} \right) \right] \mathbf 1_{\{ n^{- \gamma/2}
  \leq 1- s_1\}} \nu(\mathrm d \mathbf s),$$ which converges to $\int_{\mathcal S^{\downarrow}} f(\mathbf s)
(1-s_1) \nu(\mathrm d \mathbf s) $ as $n \rightarrow \infty$ by dominated convergence. This concludes the proof.

Scaling limits of conditioned Galton-Watson trees {#sec:cond-galt-wats}
=================================================

Recall the notations of Section \[sec:appl-galt-wats\]. While the probability distribution ${\rm GW}_\xi$ enjoys the so-called branching property, it holds that the conditioned versions ${\mathrm{GW}_\xi}^{(n)}$ are Markov branching trees.

\[sec:main-results-3\] <span>(i)</span> One has ${\mathrm{GW}_\xi}^{(n)}={\mathsf{Q}}_n^q$ for every $n\geq 1$, where the splitting probabilities $q=(q_n,n\geq 1)$ are defined by $q_1((1))=1$ and for every $n\geq 2$ and $\lambda=(\lambda_1,\ldots,\lambda_p)\in
{\mathcal{P}}_n$, $$\label{eq:11}
q_n(\lambda) = \frac {p!}{\prod_{j\geq
    1}m_j(\lambda)!}\xi(p)\frac{\prod_{i=1}^p{\rm
    GW}_\xi(\#{\mathbbm{t}}=\lambda_i)}{{\rm GW}_\xi(\#{\mathbbm{t}}= n+1)}\, .$$ <span>(ii)</span> On some probability space $(\Omega,{\mathcal{F}},{\mathbb{P}})$, let $X_1,X_2,\ldots$ be i.i.d. with distribution ${\mathbb{P}}(X_1=k)={\mathrm{GW}_\xi}(\#{\mathbbm{t}}=k)$, and set $\tau_p=X_1+X_2+\ldots+X_p$. Then $$q_n(p(\lambda)=p)=\xi(p)\frac{{\mathbb{P}}(\tau_p = n)}{{\mathbb{P}}(\tau_1 = n+1)}\, ,$$ and $q_n(\cdot\, |\, \{p(\lambda)=p\})$ is the law of the non-increasing rearrangement of $(X_1,\ldots,X_p)$ conditionally on $X_1+\ldots+X_p = n$.

<span>**Proof.** </span>(i) Under ${\mathrm{GW}_\xi}$ (viewed as a law on plane trees), conditionally on $c_\varnothing=p$, the $p$ (plane) subtrees born from $\varnothing$ are independent with law ${\mathrm{GW}_\xi}$. For integers $a_1,\ldots,a_p$ with sum $n$, the probability that these trees have sizes equal to $a_1,\ldots,a_p$ is thus $\prod_{i=1}^p{\mathrm{GW}_\xi}(\#{\mathbbm{t}}=a_i)$. Hence, $$\label{eq:21}
{\mathrm{GW}_\xi}^{(n+1)}(c_\varnothing=p,\#{\mathbbm{t}}_i=a_i,1\leq i\leq p)=
\xi(p)\frac{\prod_{i=1}^p{\mathrm{GW}_\xi}(\#{\mathbbm{t}}=a_i)}{{\mathrm{GW}_\xi}(\#{\mathbbm{t}}= n+1)}\, ,$$ and conditionally on the event on the left-hand side, the subtrees born from the root are independent with respective laws ${\mathrm{GW}_\xi}^{(a_i)},1\leq i\leq
p$. Letting $\lambda$ be the non-increasing rearrangement of $(a_1,\ldots,a_p)$ and re-ordering the subtrees by non-increasing order of size (with some convention for ties, e.g. taking them in order of appearance according to the plane structure), we see that these subtrees are independent with laws ${\mathrm{GW}_\xi}^{(\lambda_i)},1\leq
i\leq p$. Using the fact that there are $p!/\prod_{j\geq
  1}m_j(\lambda)!$ compositions $(a_1,\ldots,a_p)$ of the integer $n$ corresponding to a partition $\lambda\in {\mathcal{P}}_n$, and viewing ${\mathrm{GW}_\xi}$ as a law on ${\mathsf{T}}$ instead of plane trees, the conclusion easily follows.

\(ii) We have $q_n(p(\lambda)=p)={\mathrm{GW}_\xi}^{(n+1)}(c_\varnothing=p)$, and the wanted result is just an interpretation of (\[eq:21\]).

On the same probability space $(\Omega,{\mathcal{F}},{\mathbb{P}})$ as in the previous statement, we will also assume that $(S_r,r\geq 0)$ is a random walk with i.i.d. steps, each having distribution $\xi(i+1),i\geq -1$. Then the well-known Otter-Dwass formula (or *cyclic lemma*) @PitmanStFl [Chapter 6] allows to rewrite $$\label{eq:14}q_n(p(\lambda)=p)=
\xi(p)\frac{\frac{p}{n}{\mathbb{P}}(S_{n}=-p)}{\frac{1}{n+1}{\mathbb{P}}(S_{n+1}=-1)}=
\frac{n+1}{n}\hat{\xi}(p)\frac{{\mathbb{P}}(S_{n}=-p)}{{\mathbb{P}}(S_{n+1}=-1)}\, ,$$ where $\hat{\xi}(p)=p\xi(p)$ is the size-biased distribution associated with $\xi$.

It is often convenient to work with size-biased orderings of the sequence $(X_1,\ldots,X_p)$ rather than with its non-increasing rearrangement. Recall that if $(x_1,x_2,\ldots)$ is a non-negative sequence with $\sum_ix_i<\infty$, we define its size-biased ordering in the following way. If all terms are zero then we let $x^*_1=0$, otherwise we let $i^*$ be a random variable with $${\mathbb{P}}(i^*=i)=\frac{x_i}{\sum_{j\geq 1}x_j}\, ,$$ and set $x^*_1=x_{i^*}$. We then remove the $i^*$-th term from the sequence $(x_i,i\geq 1)$ and resume the procedure, defining a random re-ordering $(x^*_1,x^*_2,\ldots)$ of the sequence $(x_1,x_2,\ldots)$. The size-biased ordering $(X_1^*,X_2^*,\ldots)$ of a random sequence $(X_1,X_2,\ldots)$ is defined similarly, by first conditioning on $(X_1,X_2,\ldots)$. If $\mu$ is the law of $(X_1,X_2,\ldots)$, we let $\mu^*$ be the law of $(X_1^*,X_2^*,\ldots)$.

If $\mu$ is a probability distribution on ${{\mathcal{S}^{\downarrow}}}$, then $\mu^*$ is a probability distribution on the set $\mathcal{S}_1=\{{\mathbf{x}}=(x_1,x_2\ldots)\in [0,1]^{\mathbb{N}}:\sum_{i\geq 1}x_i\leq
1\}$ which is endowed with any metric inducing the product topology — in particular, $\mathcal{S}_1$ is compact. Similarly, if $\mu$ is a non-negative measure on ${{\mathcal{S}^{\downarrow}}}$, we let $\mu^*(f)=\int_{{\mathcal{S}^{\downarrow}}}\mu({\mathrm{d}}{\mathbf{s}})\mathbb{E}[f({\mathbf{s}}^*)]$, for every non-negative measurable $f:\mathcal{S}_1\to {\mathbb{R}}_+$, where ${\mathbf{s}}^*$ is the size-biased reordering of ${\mathbf{s}}$. The following statement is a simple variation of @BertoinBook [Proposition 2.3], replacing probability distributions with finite measures.

\[sec:cond-galt-wats-1\] Let $\mu_n,n\geq 1$ and $\mu$ be finite measures on ${{\mathcal{S}^{\downarrow}}}$, and assume that $\mu$ is supported on $\{{\mathbf{s}}\in {{\mathcal{S}^{\downarrow}}}:\sum_is_i=1\}$. Then $\mu_n$ converges weakly to $\mu$ if and only if $\mu_n^*$ converges weakly to $\mu^*$.

Finite variance case {#sec:finite-variance-case}
--------------------

Here we assume that $\xi$ has finite variance $\sum_{p\geq
  1}p(p-1)\xi(p)=\sigma^2<\infty$. In the proofs to come, $C$ will denote a positive, finite constant with values that can differ from line to line.

Our goal is to check hypothesis <span>**(H)**</span> for the sequence $q$ of (\[eq:11\]), and for the measure $\nu=(\sigma/2)\nu_2$. Due to Lemma \[sec:cond-galt-wats-1\], it suffices to show that $$\label{eq:27}
n^{1/2}((1-s_1){\overline}{q}_n({\mathrm{d}}{\mathbf{s}}))^*\underset{n\to\infty}{\overset{(w)}{
    \longrightarrow}}(\sigma/2)((1-s_1)\nu_2({\mathrm{d}}{\mathbf{s}}))^*\, .$$ Now, for any non-negative measure $\mu$ on ${{\mathcal{S}^{\downarrow}}}$ and any non-negative continuous function $f$ on $\mathcal{S}_1$, one can check that $$\label{eq:26}
((1-s_1)\mu({\mathrm{d}}{\mathbf{s}}))^*(f)=
\int_{\mathcal{S}_1}\mu^*({\mathrm{d}}{\mathbf{x}})(1-\max{\mathbf{x}})f({\mathbf{x}})\,
,$$ where $\max{\mathbf{x}}=\max_{i\geq 1}x_i$. Applying (\[eq:26\]) to $\mu={\overline}{q}_n$ and $\nu_2$, we conclude that (\[eq:27\]) is a consequence of the following statement.

\[sec:proof-theor-refs-2\] Let $f: \mathcal{S}_1\to{\mathbb{R}}$ be a continuous function and let $g({\mathbf{x}})=(1-\max{\mathbf{x}})f({\mathbf{x}})$. Then $$\label{eq:17}
\sqrt{n}{\overline}{q}_n^*(g)\underset{n\to\infty}{\longrightarrow}
\frac{\sigma}{\sqrt{2\pi}}\int_0^1\frac{{\mathrm{d}}x}{x^{1/2}(1-x)^{3/2}}g(x,1-x,0,\ldots)\, .$$

In summary, Theorem \[sec:main-results-1\] in <span>**Case 1.**</span> is a consequence of this statement and Theorem \[sec:main-result-2\].

Proposition \[sec:proof-theor-refs-2\] will be proved in a couple of steps. A difficulty that we will have to be careful about is that ${\mathbf{x}}\mapsto \max {\mathbf{x}}$ is not continuous on $\mathcal{S}_1$. Fix $f$, as in the statement. Note that $0\leq 1-\max{\mathbf{x}}\leq 1-x_1$ for every ${\mathbf{x}}\in \mathcal{S}_1$, so that $g({\mathbf{x}})\leq C(1-x_1)$ for every ${\mathbf{x}}\in \mathcal{S}_1$ for some finite $C>0$, a fact that will be useful.

First, note that combining (ii) in Proposition \[sec:main-results-3\] with a size-biased ordering, it holds that $$\label{eq:22}
{\overline}{q}^*_n(g)=\sum_{p\geq 1}q_n(p(\lambda)=p)
{\mathbb{E}}\left[g\left(\frac{(X^*_1,\ldots,X^*_p,0,\ldots)}{n}\right)\,
  \Big|\, \tau_p = n\right]\, .$$

\[sec:proof-theor-refs-1\] For every ${\varepsilon}>0$, $$\sqrt{n}q_n(p(\lambda)>{\varepsilon}\sqrt{n})\underset{n\to\infty}{\longrightarrow}0\, .$$

<span>**Proof.** </span> From (\[eq:14\]), the local limit theorem in the finite-variance case $$\label{eq:16}
\sup_{p\in {\mathbb{Z}}}\left|\sqrt{n}{\mathbb{P}}(S_n=-p)-\frac{1}{\sqrt{2\pi\sigma^2}}
\exp\left(-\frac{p^2}{2n\sigma^2}\right)\right|\underset{n\to\infty}{
  \longrightarrow}0\, ,$$ shows that $q_n(p(\lambda)=p)\leq C \hat{\xi}(p)$ for every $n,p$. Now $$\sum_{k\geq 0}\hat{\xi}((k,\infty))<\infty\, ,$$ because $\hat{\xi}$ has finite mean. Since $\hat{\xi}((k,\infty))$ is non-increasing, this entails that $\hat{\xi}((k,\infty))=o(k^{-1})$. Hence the result.

\[sec:proof-theor-refs-3\] One has $$\lim_{\eta\downarrow
  0}\limsup_{n\to\infty}\sqrt{n}{\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1>1-\eta\}})=0\,
,\qquad \mbox{and} \qquad
\lim_{n\to\infty}\sqrt{n}{\overline}{q}_n^*({\mathbf{1}}_{\{x_1<n^{-7/8}\}})=0\, .$$

<span>**Proof.** </span> Let ${\varepsilon},\eta>0$. Since $|f({\mathbf{x}})|\leq
(1-x_1)$, we get using (\[eq:22\]), that $\sqrt{n}{\overline}{q}_n^*(|f|{\mathbf{1}}_{\{x_1>1-\eta\}})$ is bounded from above by $$n^{1/2}\sum_{1\leq p\leq {\varepsilon}n^{1/2}}q_n(p(\lambda)=p)\sum_{m_1\geq
  (1-\eta)n}\left(1-\frac{m_1}{n}\right)
\frac{pm_1}{n}\frac{{\mathbb{P}}(X_1=m_1){\mathbb{P}}(\tau_{p-1} = n-m_1)}{{\mathbb{P}}(\tau_p = n)}\,
+o(1)\, ,$$ because $${\mathbb{P}}(X_1^*=m\, |\, X_1+\ldots+X_p = n)=\frac{pm}{n}
\frac{{\mathbb{P}}(X_1=m){\mathbb{P}}(X_2+\ldots+X_p = n-m)}{{\mathbb{P}}(X_1+\ldots+X_p = n)}\, .$$ The $o(1)$ term accounts for the fact that we restricted the sum to $1\leq p\leq {\varepsilon}n^{1/2}$, which costs at most $o(n^{-1/2})$ by Lemma \[sec:proof-theor-refs-1\]. We now use the cyclic lemma again, entailing that ${\mathbb{P}}(\tau_p = n)=(p/n){\mathbb{P}}(S_n=-p)$. Using this for $p=1$, and with the help of (\[eq:16\]), we obtain that ${\mathbb{P}}(\tau_1 = n)\sim
(\sigma\sqrt{2\pi})^{-1}n^{-3/2}$ as $n\to\infty$. This yields the upper-bound $$\sqrt{n}{\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1>1-\eta\}})\leq C\sum_{1\leq p\leq
  {\varepsilon}n^{1/2}}p^2\xi(p)\frac{1}{n}\sum_{(1-\eta)n\leq m_1\leq
  n}\frac{\sqrt{n}}{\sqrt{m_1}}\frac{{\mathbb{P}}(S_{n-m_1}=-p+1)}{{\mathbb{P}}(S_n=-p)}+o(1)\,
,$$ and since $1\leq p\leq {\varepsilon}n^{1/2}$, (\[eq:16\]) implies that $\sqrt{n}{\mathbb{P}}(S_n=-p)$ and $\sqrt{n-m_1}{\mathbb{P}}(S_{n-m_1}=-p+1)$ are respectively bounded from below and above, by constants that are independent on $n,m_1,p$ (but might depend on ${\varepsilon}$). Consequently, the bound is $$C_{\varepsilon}\sum_{p\geq 1}p^2\xi(p)\frac{1}{n}\sum_{(1-\eta)n< m_1\leq
  n}\frac{1}{\sqrt{\frac{m_1}{n}\left(1-\frac{m_1}{n}\right)}}+o(1)\,
,$$ and this converges to $C_{\varepsilon}\int_{1-\eta}^1(x(1-x))^{-1/2}{\mathrm{d}}x$. In turn, this goes to $0$ as $\eta\to 0$, for fixed ${\varepsilon}$. The second limit is obtained in a similar way, writing $\sqrt{n}{\overline}{q}_n^*({\mathbf{1}}_{\{x_1<n^{-7/8}\}})$ as $$\begin{aligned}
\lefteqn{n^{1/2}\sum_{1\leq p\leq {\varepsilon}n^{1/2}} q_n(p(\lambda)=p)\sum_{1\leq
  m_1\leq
  n^{1/8}}\frac{pm_1}{n}\frac{{\mathbb{P}}(X_1=m_1){\mathbb{P}}(\tau_{p-1} = n-m_1)}{
  {\mathbb{P}}(\tau_p = n)}+o(1)}\\ &\leq& n^{-3/8}\sum_{1\leq p\leq {\varepsilon}n^{1/2}}p(p-1)\xi(p)\sum_{1\leq m_1\leq
  n^{1/8}}\frac{{\mathbb{P}}(S_{n-m_1}=-p+1)}{{\mathbb{P}}(S_{n+1}=-1)}+o(1)
\\&\leq& C_{{\varepsilon}}n^{-1/4}\sum_{p\geq 1}p(p-1)\xi(p)+o(1)\, ,\end{aligned}$$ for some constant $C_{\varepsilon}$, where we used the local limit theorem at the last step.

\[sec:proof-theor-refs-4\] For every $\eta>0$, it holds that $$\lim_{n\to\infty}\sqrt{n}{\overline}{q}^*_n({\mathbf{1}}_{\{x_1+x_2<1-\eta\}})=0\,
.$$

<span>**Proof.** </span>Fix ${\varepsilon}>0$. An upper-bound for the quantity appearing in the statement is given by (up to an additional $o(1)$ quantity depending on ${\varepsilon}$) $$\sqrt{n}\sum_{1\leq p\leq {\varepsilon}n^{1/2}}p\xi(p)\sum_{m_1+m_2\leq
  (1-\eta)n}\frac{pm_1}{n}\frac{(p-1)m_2}{n-m_1}\frac{{\mathbb{P}}(X_1=m_1){\mathbb{P}}(X_2=m_2)
{\mathbb{P}}(\tau_{p-2} = n-m_1-m_2)}{{\mathbb{P}}(\tau_p = n)}\,
.$$ If $m_1+m_2< n(1-\eta)$ then $n-m_1-m_2\geq \eta n$. In this case, we obtain, using the cyclic lemma and (\[eq:16\]), $$\frac{{\mathbb{P}}(\tau_{p-2} = n-m_1-m_2)}{{\mathbb{P}}(\tau_p = n)}=
\frac{\frac{p-2}{n-m_1-m_2}{\mathbb{P}}(S_{n-m_1-m_2}=-p+2)}{\frac{p}{n}{\mathbb{P}}(S_n=-p)}\leq
\frac{C}{\eta^{3/2}}\, .$$ Note that the constant $C$ here does not depend on $p,{\varepsilon}$. Consequently, we obtain the bound $$\begin{aligned}
\sqrt{n}{\overline}{q}^*_n({\mathbf{1}}_{\{x_1+x_2<(1-\eta)n\}}) &\leq&
\frac{C}{\eta^{3/2}\sqrt{n}}\sum_{1\leq p\leq {\varepsilon}n^{1/2}}p^3\xi(p)\frac{1}{n^2}\sum_{m_1+m_2<(1-\eta)n}
\sqrt{\frac{n}{m_1}\frac{n}{m_2}} +o(1)\\ &\leq&
\frac{C{\varepsilon}}{\eta^{3/2}}\sum_{p\geq 1}p^2\xi(p)\int_{x_1+x_2\leq
  1}\frac{{\mathrm{d}}x_1{\mathrm{d}}x_2}{\sqrt{x_1x_2}}+o(1)\, ,\end{aligned}$$ where $C$ is still independent of $p,{\varepsilon}$. The first term on the right-hand side does not depend on $n$ anymore and goes to $0$ as ${\varepsilon}\to 0$, entailing the result.

\[sec:proof-theor-refs-5\] There exists a function $\beta_\eta=o(\eta)$ as $\eta\downarrow 0$, so that $$\begin{aligned}
\lim_{\eta\downarrow 0}\liminf_{n\to\infty}\sqrt{n}
{\overline}{q}^*_n(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\beta_\eta\}}) &=&\lim_{
  \eta\downarrow 0}\limsup_{n\to\infty}\sqrt{n}
{\overline}{q}^*_n(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\beta_\eta\}})\\ &=&
\frac{\sigma}{\sqrt{2\pi}}
\int_0^1\frac{g((x,1-x,0,\ldots))}{x^{1/2}(1-x)^{3/2}}{\mathrm{d}}x\, ,\end{aligned}$$

<span>**Proof.** </span> The proof is similar to the previous ones, but technically more tedious, so we will only sketch the details. Fix $\eta>0$, and consider $\eta'\in(0,\eta)$ and ${\varepsilon}>0$. Then, by decomposing with respect to the events $\{p(\lambda)>{\varepsilon}\sqrt{n}\}$ and $\{{\mathbf{x}}:x_1\leq n^{-7/8}\}$, we obtain, using Lemma \[sec:proof-theor-refs-1\] and the second limit of Lemma \[sec:proof-theor-refs-3\], $$\begin{aligned}
\lefteqn{\sqrt{n}{\overline}{q}^*_n(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\eta'\}})=o(1)+
  \sqrt{n}\sum_{1\leq p\leq {\varepsilon}n^{1/2}}q_n(p(\lambda)=p)}\\ &\times
&\sum_{\substack{n^{1/8}\leq m_1\leq (1-\eta)n\\ (1-\eta')n\leq
    m_1+m_2\leq n}}{\mathbb{E}}[g((m_1,m_2,X_3^*,\ldots,X^*_p)/n)\, |\,\tau_p =
  n,X_1^*=m_1,X^*_2=m_2]\\ &\times&
\frac{pm_1}{n}\frac{(p-1)m_2/n}{1-m_1/n}{\mathbb{P}}(X_1=m_1){\mathbb{P}}(X_2=m_2)
\frac{{\mathbb{P}}(\tau_{p-2} = n-m_1-m_2)}{{\mathbb{P}}(\tau_p = n)}\, .\end{aligned}$$ We now give a lower bound of the $\liminf$ of this as $n\to\infty$. Showing that the same quantity is an upper-bound of the $\limsup$ being similar and easier.

Note that if $x_1+x_2\geq 1-\eta'$ and $x_1\leq 1-\eta$, we have that $(1-x_1-x_2)/(1-x_1) \leq \eta'/\eta$ and then $x_2/(1-x_1) \geq
1-\eta'/\eta$. Next, by the local limit theorem, we can always choose $\eta'$ small enough so that ${\mathbb{P}}(X_1=m_2)/{\mathbb{P}}(X_1 = n-m_1)\geq
1-\eta$ for every $n$ large enough.

Also, still by the local limit theorem, we can choose ${\varepsilon}$ small enough so that for every $1\leq p\leq {\varepsilon}n^{1/2}$ and every $n$ large, we have $$q_n(p(\lambda)=p)/\hat{\xi}(p)\geq (1-\eta)\qquad \mbox{and}\qquad
p^{-1}n^{3/2}{\mathbb{P}}(\tau_p = n)\geq (1-\eta)\sigma\sqrt{2\pi}\, .$$ A third use of the local limit theorem entails that for every $n$ large, we have $$m_1^{3/2}{\mathbb{P}}(X_1=m_1)\wedge m_2^{3/2}{\mathbb{P}}(X_2=m_2)\geq
(1-\eta)\sigma\sqrt{2\pi}\, ,$$ for every $n$ large and $m_1\geq
n^{1/8}$, $m_2\geq (\eta-\eta')n$.

Finally, we use the fact that $f$ is uniformly continuous on $\mathcal{S}_1$, while $\max{\mathbf{x}}= x_1\vee x_2$ on the set $\{{\mathbf{x}}\in
\mathcal{S}_1:x_1+x_2>3/4\}$. Consequently, the function $g({\mathbf{x}})=(1-\max {\mathbf{x}})f({\mathbf{x}})$ is uniformly continuous on the latter set. Therefore, we can choose $\eta'<1/4$ small enough so that $$|g((m_1,m_2,m_3,\ldots)/n)- g((m_1,n-m_1,0,\ldots)/n)|\leq \eta$$ for every $(m_1,m_2,\ldots)$ with sum $n$, such that $m_1+m_2\geq
(1-\eta')n$. Putting things together, for every $\eta>0$, we can choose $\eta'=:\beta_\eta ,{\varepsilon}$ small so that for every $n$ large enough, $\sqrt{n}{\overline}{q}^*_n(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\eta'\}})$ is greater than or equal to $$\begin{aligned}
\lefteqn{(1-\eta)^5(1-\eta'/\eta)\sum_{1\leq p\leq {\varepsilon}n^{1/2}}(p-1)\hat{\xi}(p)\frac{1}{n}\sum_{n^{1/8}\leq m_1\leq
    (1-\eta)n} (g((m_1,n-m_1,0,\ldots)/n)-\eta)\frac{m_1}{n}}\\ &
\times & \frac{1}{\sigma\sqrt{2\pi}((m_1/n)(1-m_1/n))^{3/2}}
\sum_{(1-\eta')n-m_1\leq m_2\leq n-m_1}{\mathbb{P}}(\tau_{p-2} = n-m_1-m_2).\end{aligned}$$ Finally, the last sum is $\sum_{m=0}^{\eta' n}{\mathbb{P}}(\tau_{p-2}=m)$, and this can be made arbitrarily close to $1$, uniformly in $1\leq p\leq
{\varepsilon}n^{1/2}$, as soon as $n$ is large enough, by our usual use of the local limit theorem. Taking the $\liminf$ in $n$ and using a convergence of Riemann sums, yields $$\begin{aligned}
\lefteqn{\liminf_{n\to\infty}\sqrt{n}{\overline}{q}^*_n(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\eta'\}})}\\
 & &\geq (1-\eta)^5(1-\eta'/\eta)\sum_{p\geq
  1}(p-1)\hat{\xi}(p)\int_0^{1-\eta}
\frac{{\mathrm{d}}x}{\sigma\sqrt{2\pi}x^{1/2}(1-x)^{3/2}}(g(x,1-x,0,\ldots)-\eta).\end{aligned}$$ One concludes using the fact that $\sum_{ p\geq
  1}(p-1)\hat{\xi}(p)=\sigma^2$.

We can now finish the proof of Proposition \[sec:proof-theor-refs-2\]. Simply write $$|{\overline}{q}_n^*(g)-{\overline}{q}_n^*(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\eta'\}})|\leq
{\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1\geq
  1-\eta\}}))+{\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1+x_2\leq 1-\eta'\}})\, .$$ Now fix ${\varepsilon}>0$, and using Lemmas \[sec:proof-theor-refs-3\] and \[sec:proof-theor-refs-5\], choose $\eta,\eta'$ in such a way that $\sqrt{n}{\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1\geq 1-\eta\}})\leq {\varepsilon}/2$ and $$\left|\sqrt{n}{\overline}{q}_n^*(g{\mathbf{1}}_{\{x_1<1-\eta,x_1+x_2>1-\eta'\}})-
\frac{\sigma}{\sqrt{2\pi}}
\int_0^1\frac{g((x,1-x,0,\ldots))}{x^{1/2}(1-x)^{3/2}}{\mathrm{d}}x\right|\leq
{\varepsilon}/2$$ for every $n$ large. For this choice of $\eta,\eta'$, we then have for every $n$ large enough, $$\left|{\overline}{q}_n^*(g)-\frac{\sigma}{\sqrt{2\pi}}
\int_0^1\frac{g((x,1-x,0,\ldots))}{x^{1/2}(1-x)^{3/2}}{\mathrm{d}}x\right|\leq
{\varepsilon}+ {\overline}{q}_n^*(|g|{\mathbf{1}}_{\{x_1+x_2\leq 1-\eta'\}})\, ,$$ and the upper-bound converges to ${\varepsilon}$ as $n\to\infty$ by Lemma \[sec:proof-theor-refs-4\]. Since ${\varepsilon}$ was arbitrary, this proves Proposition \[sec:proof-theor-refs-2\], hence implying Theorem \[sec:main-results-1\] in <span>**Case 1**</span>.

Stable case {#sec:stable-case}
-----------

Assume that $\xi(p)\sim cp^{-\alpha-1}$ for some $\alpha\in (1,2)$ and $c>0$. Theorem \[sec:main-results-1\] in <span>**Case 2.**</span> will follow if we can show that hypothesis <span>**(H)**</span> holds for $\gamma=1-1/\alpha$, $\ell\equiv \left(\alpha(\alpha-1)/(c
\Gamma(2-\alpha)) \right)^{1/\alpha}$, and the dislocation measure $\nu_\alpha$. A similar reasoning as in the beginning of the previous section shows that it suffices to prove the following statement.

\[sec:proof-theor-refs-7\] If $f:\mathcal{S}_1\to {\mathbb{R}}$ is a continuous function and $g({\mathbf{x}})= (1-\max {\mathbf{x}})f({\mathbf{x}})$, then $$n^{1-1/\alpha}{\overline}{q}_n^*(g)\underset{n\to\infty}{\longrightarrow}
\Big(c\frac{\Gamma(2-\alpha)}{\alpha(\alpha-1)}\Big)^{1/\alpha}
\nu_\alpha^*(g)\, .$$

One will note that the function $g$ of the statement is continuous $\nu_\alpha^*$-a.e., since ${\mathbf{x}}\mapsto \max{\mathbf{x}}$ is continuous at every point ${\mathbf{x}}$ with sum $1$. Now, $$\begin{aligned}
{\overline}{q}_n^*(g)&=&\sum_{p\geq
  1}q_n(p(\lambda)=p){\mathbb{E}}\left[g\left(\frac{(X_1^*,\ldots,X_p^*,0,\ldots)}{n}\right)\,
  \Big|\, \tau_p = n\right]\nonumber\\ &=&n^{1/\alpha}\int_0^\infty{\mathrm{d}}x \, q_n(p(\lambda)=\lceil n^{1/\alpha}x \rceil)\,
{\mathbb{E}}\left[g\left(\frac{(X_1^*,\ldots,X_{\lceil n^{1/\alpha}
      x\rceil}^*,0,\ldots)}{n}\right)\, \Big|\, \tau_{\lceil
    n^{1/\alpha} x\rceil} = n\right] \label{eq:15}\end{aligned}$$ Recall the notation around (\[eq:14\]). The random walk $S_n$ is now such that $(S_{\lfloor nt\rfloor}/n^{1/\alpha},t\geq 0)$ converges in distribution in the Skorokhod space to a spectrally positive stable Lévy process $(Y_t,t\geq 0)$ with index $\alpha$ and Lévy measure $c{\mathrm{d}}x/x^{1+\alpha}{\mathbf{1}}_{\{x>0\}}$. Its Laplace transform is given by ${\mathbb{E}}[\exp(-\lambda Y_t)]=\exp(tc'\lambda^\alpha)$, where $c'=c\frac{\Gamma(2-\alpha)}{\alpha(\alpha-1)}$. The Gnedenko-Kolmogorov local limit theorem also yields $$n^{1/\alpha}{\mathbb{P}}(S_n=k)=p_1(k/n^{1/\alpha})+{\varepsilon}(n,k)$$ where $\sup_k|{\varepsilon}(n,k)|\to 0$ as $n\to\infty$, and $p_t$ is the density of $Y_t$. This, together with (\[eq:14\]) and our hypothesis on the asymptotic behavior of $\xi$, entail that $$q_n(p(\lambda)=\lceil n^{1/\alpha}x\rceil)\sim
cn^{-1}x^{-\alpha}\frac{p_1(-x)}{p_1(0)}\, .$$ Let us now focus on the random variables $X_1,X_2,\ldots$ and $\tau_p=X_1+\ldots+X_p$. We have ${\mathbb{P}}(X_1 = n) = n^{-1}{\mathbb{P}}(S_n=-1)\sim
n^{-1-1/\alpha}p_1(0)$, which gives that $X_1$ is in the domain of attraction of a stable random variable with index $1/\alpha$. More specifically, one has that $(\tau_{\lfloor n
  x\rfloor}/n^{\alpha},x\geq 0)$ converges in the Skorokhod space to a stable subordinator $(T_y,y\geq 0)$ with index $1/\alpha$, and Lévy measure $$\label{eq:28}
p_1(0)\frac{{\mathrm{d}}x}{x^{1+1/\alpha}}{\mathbf{1}}_{\{x>0\}}\, .$$ Its Laplace transform is given by $${\mathbb{E}}[\exp(-\lambda T_x)]=\exp(-xp_1(0)\alpha
\Gamma(1-1/\alpha)\lambda^{1/\alpha})\, .$$ On the other hand, $T_x$ has same distribution as the first hitting time of $-x$ by $(Y_t,t\geq
0)$ (because a similar statement is true of $\tau_p$ and $S_n$), which identifies the Laplace exponent of $T_1$ as $(\lambda/c')^{1/\alpha}$, see @BertoinLevy [Chapter VII]. This yields $$\label{eq:29}
p_1(0)=\frac{1}{ \alpha\Gamma(1-1/\alpha)(c')^{1/\alpha}}=
\frac{1}{\alpha\Gamma(1-1/\alpha)}
\Big(\frac{\alpha(\alpha-1))}{c\Gamma(2-\alpha)}\Big)^{1/\alpha}.$$ Let $Q_y$ be the probability density function of $T_y$. The cyclic lemma @BertoinLevy [Corollary VII.3] gives $tQ_x(t)=xp_t(-x)$, while the Gnedenko-Kolmogorov local limit theorem states that $$p^{\alpha}{\mathbb{P}}(\tau_p = n)=Q_1(n/p^\alpha)+{\varepsilon}'(p,n)\, ,$$ where $\sup_n|{\varepsilon}'(p,n)|\to 0$ as $p\to\infty$.

\[sec:proof-theor-refs-6\] The sequence $(X_1^*,\ldots,X^*_{\lceil n^{1/\alpha}x\rceil})/n$ conditioned on $\tau_{\lceil n^{1/\alpha}x\rceil} = n$ converges in distribution to a random sequence $(\Delta_1^*,\Delta_2^*,\ldots)$, defined inductively by $${\mathbb{P}}\Big(\Delta_{i+1}^*\in {\mathrm{d}}z\, \Big|\,
\Delta^*_1,\ldots,\Delta^*_i,\sum_{j=1}^i\Delta_j^*=y\Big)=\frac{p_1(0)x}{
  z^{1/\alpha}}\frac{Q_x(1-y-z)}{Q_x(1-y)}{\mathrm{d}}z\, ,\qquad 0\leq z\leq
1-y\, .$$

<span>**Proof.** </span> The case $i=1$ is obtained by using the local limit theorem in $$n{\mathbb{P}}(X_1^*=\lfloor nz\rfloor\, |\, \tau_{\lceil
  n^{1/\alpha}x\rceil} = n)=\lceil n^{1/\alpha}x\rceil\, \lfloor
nz\rfloor {\mathbb{P}}(X_1=\lfloor nz\rfloor)\frac{{\mathbb{P}}(\tau_{\lceil
    n^{1/\alpha}x\rceil-1} = n-\lfloor nz\rfloor)}{{\mathbb{P}}(\tau_{\lceil
    n^{1/\alpha}x\rceil} = n)}\, .$$ One then reasons inductively, in an elementary way. Details are left to the reader.

The limiting sequence $(\Delta^*_i,i\geq 1)$ has same distribution as the sequence of jumps of the subordinator $(T_y,0\leq y\leq x)$, conditionally given $T_x=1$, and arranged in size-biased order, see @PitmanStFl [Chapter 4] or @BertoinBook. We will denote by $\Delta T_{[0,x]}^*$ this randomly ordered sequence of jumps. Hence, provided we have the right to apply dominated convergence in (\[eq:15\]), we obtain, using $xp_1(-x)=Q_x(1)$, $$\label{eq:30}
n^{1-1/\alpha}{\overline}{q}^*_n(g)\underset{n\to\infty}{\longrightarrow}
\frac{c}{p_1(0)}\int_0^\infty\frac{{\mathrm{d}}x}{x^{\alpha+1}}Q_x(1){\mathbb{E}}[g(\Delta
  T_{[0,x]}^*)\, |\, T_x=1]\, .$$ Using scaling for the subordinator $(T_y,y\geq 0)$, the previous integral can be rewritten as $$\frac{c}{p_1(0)}\int_0^\infty\frac{{\mathrm{d}}x}{x^{2\alpha+1}}Q_1(x^{-\alpha}){\mathbb{E}}[g(x^\alpha\Delta T_{[0,1]}^*)\, |\,
  T_1=x^{-\alpha}]\, ,$$ and changing variables $u=x^{-\alpha}$ shows that this is equal to $$\frac{c}{\alpha p_1(0)}\int_0^\infty Q_1(u){\mathrm{d}}u\, {\mathbb{E}}[ug(\Delta
  T_{[0,1]}^*/u)\, |\, T_1=u]=\frac{c}{\alpha p_1(0)}{\mathbb{E}}[T_1g(\Delta
  T_{[0,1]}^*/T_1)]\, .$$ Finally, the sequence $\Delta T_{[0,1]}$ of jumps of $T$ before time $1$ is the sequence of atoms of a Poisson measure with intensity given by (\[eq:28\]). Using (\[eq:29\]), it thus has same distribution as $\alpha(\alpha-1)c^{-1}\Gamma(2-\alpha)^{-1}(\Delta_1,\Delta_2,\ldots)$, as defined in Section \[sec:appl-galt-wats\]. Using the notations therein and (\[eq:29\]), we get after rearrangements $$\begin{aligned}
\frac{c}{\alpha p_1(0)}{\mathbb{E}}[T_1g(\Delta T^*_{[0,1]}/T_1)]&=&
\Big(c\frac{\Gamma(2-\alpha)}{ \alpha(\alpha-1)}\Big)^{1/\alpha}
\frac{\alpha^2\Gamma(2-1/\alpha)}{ \Gamma(2-\alpha)}{\mathbb{E}}\bigg[
  Tg\Big(\frac{\Delta_i^*}{T},i\geq
  1\Big)\bigg]\\ &=&\Big(c\frac{\Gamma(2-\alpha)}{
  \alpha(\alpha-1)}\Big)^{1/\alpha}\nu_\alpha^*(g)\, ,\end{aligned}$$ as wanted. It remains to justify that the convergence (\[eq:30\]) is indeed dominated. To this end, using (\[eq:15\]) and the fact that $q_n(p(\lambda)=\lceil n^{1/\alpha}x\rceil)\leq C\lceil
n^{1/\alpha}x\rceil^{-\alpha}$, it suffices to show that the expectation term in this equation is bounded by $C\lceil
n^{1/\alpha}x\rceil/n^{1/\alpha}$ for some $C$ independent of $n$, and for $x\in [0,1]$. In turn, since $g({\mathbf{x}})\leq C(1-x_1)$ for some finite $C>0$, it suffices to substitute this upper-bound to $g$. Now, we have ${\mathbb{P}}(X_1=m)\leq Cm^{-1-1/\alpha}$ for every $m$, so that $$\begin{aligned}
\lefteqn{{\mathbb{E}}\left[\left(1-\frac{X_1^*}{n}\right) \, \Big|\, \tau_{\lceil
      n^{1/\alpha}x\rceil} = n\right]}\\ &=&\sum_{m=1}^n\left(1-\frac{m}{n}\right)\lceil
n^{1/\alpha}x\rceil \frac{m}{n}{\mathbb{P}}(X_1=m)\frac{{\mathbb{P}}(\tau_{\lceil
    n^{1/\alpha}x\rceil-1} = n-m)}{{\mathbb{P}}(\tau_{\lceil
    n^{1/\alpha}x\rceil} = n)}\\ &\leq
&\sum_{m=1}^n\left(1-\frac{m}{n}\right)\lceil n^{1/\alpha}x\rceil
\frac{m}{n}{\mathbb{P}}(X_1=m)\frac{\frac{\lceil
    n^{1/\alpha}x\rceil-1}{n-m}{\mathbb{P}}(S_{n-m}=-\lceil
  n^{1/\alpha}x\rceil+1) }{\frac{\lceil
    n^{1/\alpha}x\rceil}{n}{\mathbb{P}}(S_{n}=-\lceil
  n^{1/\alpha}x\rceil)}\\ &\leq & C\frac{\lceil
  n^{1/\alpha}x\rceil}{n^{1/\alpha}}
\frac{1}{n}\sum_{m=1}^n\frac{1}{\left(\frac{m}{n}\right)^{1/\alpha}
  \left(1-\frac{m}{n}\right)^{1/\alpha}} \\ &\leq & C\frac{\lceil
  n^{1/\alpha}x\rceil}{n^{1/\alpha}}\, ,\end{aligned}$$ where we have used that $(n-m)^{1/\alpha}{\mathbb{P}}(S_{n-m}=-\lceil
n^{1/\alpha}x\rceil+1)$ is uniformly bounded (in $n,m,x$) and that $n^{1/\alpha}{\mathbb{P}}(S_{n}=-\lceil n^{1/\alpha}x\rceil)$ is uniformly bounded away from $0$ for $x\in [0,1]$. This is the wanted bound, concluding the proof of Proposition \[sec:proof-theor-refs-7\], hence of Theorem \[sec:main-results-1\].

Scaling limits of uniform unordered trees {#SectionPolya}
=========================================

In this section, we fix once and for all an integer $m \in
\{2,\ldots,\infty\}$ and consider trees in which every vertex has at most $m$ children. We use the notations of Section \[sec:appl-polya-trees\] and let $T_n$ be uniformly distributed in ${\mathsf{T}}^{(m)}_{n}$, for $n \geq 1$.

The first difficulty we have to overcome is that the sequence $(T_n,n
\geq 1)$ *is not* Markov branching as defined in Section \[sec:mark-branch-trees-1\]. We will therefore start in Section \[Polyacoupling\] by coupling this sequence with a family of Markov branching trees that are asymptotically close to $T_n,n\geq 1$, and then check in Section \[PolyaH2\] that the coupled trees satisfy **(H)**.

Let us fix some notation. For ${\mathsf{t}}\in {\mathsf{T}}_n^{(m)}$, we can write ${\mathsf{t}}=\langle{\mathsf{t}}^{(1)},\ldots,{\mathsf{t}}^{(k)}\rangle$ with $\sum_{i=1}^k\#{\mathsf{t}}^{(i)} = n-1$, and we let $\lambda({\mathsf{t}})\in {\mathcal{P}}_{n-1}$ be the partition obtained by arranging in decreasing order the sequence $(\#{\mathsf{t}}^{(1)},\ldots,\#{\mathsf{t}}^{(k)})$ (of course, this does not depend on the labeling of the trees ${\mathsf{t}}^{(1)},\ldots,{\mathsf{t}}^{(k)}$). Let ${\mathsf{F}}_j(k)$ be the set of of multisets[^6] with $k$ elements in ${\mathsf{T}}^{(m)}_j$. By convention, we set ${\mathsf{F}}_j(0)=\{\varnothing\}$. Then, for $\lambda\in {\mathcal{P}}_{n-1}$ with $p(\lambda)\leq m$, we have a bijection $$\label{eq:31}
\{{\mathsf{t}}\in
{\mathsf{T}}_n^{(m)}:\lambda({\mathsf{t}})=\lambda\}\equiv\prod_{j=1}^{n-1}{\mathsf{F}}_j(m_j(\lambda))\,
,$$ obtained by grouping the subtrees of ${\mathsf{t}}$ born from the root with size $j$ into a multiset, denoted by ${\mathsf{f}}_j({\mathsf{t}})$, of $m_j(\lambda)$ trees. From this, we deduce that ${\mathsf{f}}_j(T_n),1\leq
j\leq n-1$ are independent uniform random elements in ${\mathsf{F}}_j(m_j(\lambda))$ conditionally given $\lambda(T_n)$. However, the uniform random element in ${\mathsf{F}}_j(k)$ has a different distribution from the multiset induced by $k$ i.i.d. uniform element in ${\mathsf{T}}^{(m)}_j$, as soon as $k\geq 2$. This is what prevents $T_n$ from enjoying the Markov branching property, i.e. from having law ${\mathsf{Q}}^q_n$, where for $n\geq 1$, $q_n$ is the law of $\lambda(T_{n+1})$.

Letting ${\mathbf{F}}_j(k)=\#{\mathsf{F}}_j(k)$, the previous bijection yields $$\mathbf S_n^{(\lambda)}:=\#\{{\mathsf{t}}\in
{\mathsf{T}}^{(m)}_n:\lambda({\mathsf{t}})=\lambda\} = \prod_{j=1}^{n-1}
{\mathbf{F}}_j(m_j(\lambda))\, .$$ When $p(\lambda) \geq m$, we set $\mathbf
S_n^{(\lambda)}=0$. Of course, letting ${\mathbf{T}}^{(m)}_n=\#{\mathsf{T}}^{(m)}_n$, we also have $${\mathbf{T}}^{(m)}_n = \sum_{\lambda \in \mathcal P_{n-1}}
\mathbf S_n^{(\lambda)}\, .$$ Using the obvious fact that ${\mathbf{F}}_j(k)\leq {\mathbf{T}}^{(m)}_j {\mathbf{F}}_j(k-1)$, we obtain the rough but useful bound $$\label{bound1}
\mathbf S_{n}^{(\lambda)} \leq {\mathbf{T}}^{(m)}_{\lambda_1}
\mathbf S_{n-\lambda_1}^{(\lambda_2,\lambda_3,\ldots,\lambda_{p(\lambda)})}.$$

We recall the key result (\[eq:18\]) of Otter @otter48, which is used throughout the proofs below: $$\mathbf T_n^{(m)} \underset{n \rightarrow \infty}\sim \kappa_m
\frac{\rho^n}{n^{3/2}}.$$ Setting ${\mathbf{T}}^{(m)}_0=1$ by convention, we obtain that for $\rho=\rho_m>1$, and two constants $K\geq 1\geq \mathrm{k}>0$, $$\label{eq:20}
{\mathbf{T}}^{(m)}_n \leq K \frac{\rho^n}{n^{3/2}}\, ,\quad n\geq 0\, \qquad
{\mathbf{T}}^{(m)}_n \geq \mathrm{k} \frac{\rho^n}{n^{3/2}} , \quad n \geq 1\, .$$ Note that we also have ${\mathbf{T}}^{(m)}_n \leq K \rho^n$ for all $n \geq
0$. Last, we let $\kappa=\kappa_m$.

Coupling {#Polyacoupling}
--------

Let $\mu_n$ be the uniform probability distribution over ${\mathsf{T}}^{(m)}_n$, and let $q_n=\lambda_*\mu_{n+1}$ be the law of the partition of $n$ induced by the subtrees born from the root of a $\mu_{n+1}$-distributed tree. For every $n\geq 1$, we want to construct a pair of random variables $(T_n,T'_n)$ on some probability space $(\Omega,{\mathcal{F}},{\mathbb{P}})$, such that

-   $T_n$ has law $\mu_n$

-   $T'_n$ has law ${\mathsf{Q}}^q_n$

-   for every ${\varepsilon}>0$, $\lim_{n\to\infty}\mathbb E\left
    [d_{\mathrm{GHP}}(n^{-\varepsilon}T_n,n^{-\varepsilon}T'_n ) \right]=0$.

Recall that if $T_n$ has distribution $\mu_n$, and conditionally on $\lambda(T_n)=\lambda$, then ${\mathsf{f}}_j(T_n),1\leq j\leq n-1$ are independent, respectively uniform in ${\mathsf{F}}_j(m_j(\lambda))$. We are going to need the following fact.

\[sec:coupling-1\] For every $j,k\geq 1$, let $F_j$ be uniform in ${\mathsf{F}}_j(k)$ and $\overline F_j$ be the multiset induced by an i.i.d. sequence of $k$ random variables with law $\mu_j$. Let $A_j$ be the set of elements in ${\mathsf{F}}_j(k)$ with components that are pairwise distinct. Then

<span>(i)</span> One has ${\mathbb{P}}(F_j\in A_j)\leq {\mathbb{P}}(\overline F_j\in A_j)$.

<span>(ii)</span> The conditional distributions of $F_j$ and $ \overline F_j$ given $A_j$ are equal.

<span>**Proof.** </span>For a finite set $A$, the number of multisets with $k$ elements is $\#(A^k/\mathfrak{S}_k)\geq \#A^k/k!$. Then $$\begin{aligned}
{\mathbb{P}}(F_j\in
A_j)&=&\frac{\#{\mathsf{T}}^{(m)}_j(\#{\mathsf{T}}^{(m)}_j-1)\ldots(\#{\mathsf{T}}^{(m)}_j-k+1)}{k!\#{\mathsf{F}}_j(k)}\\ &\leq&
\frac{\#{\mathsf{T}}^{(m)}_j(\#{\mathsf{T}}_j^{(m)}-1)\ldots(\#{\mathsf{T}}^{(m)}_j-k+1)}{(\#{\mathsf{T}}^{(m)}_j)^k}\\ &=&{\mathbb{P}}( \overline F_j\in
A_j)\, .\end{aligned}$$ This gives (i). Property (ii) is also obtained by counting: on the event $A_j$. The probability that $F_j$ equals some given (multi)set $S\in {\mathsf{F}}_j(k)$ with all distinct elements is $\#{\mathsf{F}}_j(k)^{-1}$, while the probability that $F_j'$ equals the same set $S$ is $k!(\#{\mathsf{T}}^{(m)}_j)^{-k}$. Dividing by ${\mathbb{P}}(F_j\in A_j)$ and ${\mathbb{P}}(F'_j\in A_j)$ respectively gives the same result.

The previous statement allows to construct a coupling between $F_j$ and $ \overline F_j$, in the following way. Let ${\mathsf{f}}\in {\mathsf{F}}_j(k)$. Consider three independent random variables ${\mathsf{f}}'',{\mathsf{f}}''' ,B$, such that the law of ${\mathsf{f}}''$ is the law of $ \overline F_j$ conditionally given $A_j$, the law of ${\mathsf{f}}'''$ is the law of $ \overline F_j$ conditionally given $A^c_j$ and $B$ is an independent Bernoulli random variable with ${\mathbb{P}}(B=1)={\mathbb{P}}( \overline F_j\in
A_j^c)/{\mathbb{P}}(F_j\in A_j^c)$, which is indeed in $[0,1]$ by (i) in Lemma \[sec:coupling-1\]. Set $${\mathsf{f}}'=\left\{\begin{array}{cl} {\mathsf{f}}& \mbox{ if
}{\mathsf{f}}\in A_j 
\\ {\mathsf{f}}'' & \mbox{ if }{\mathsf{f}}\notin A_j\mbox{ and }B=0
\\ {\mathsf{f}}''' & \mbox{ if }{\mathsf{f}}\notin A_j \mbox{ and }B=1.
\end{array}
\right.$$ We let $K_j({\mathsf{f}},\cdot)$ be the law of the multiset ${\mathsf{f}}'$ thus obtained, hence defining a Markov kernel on ${\mathsf{F}}_j(k)$. We say that the random variables $F,F'$ are <span>*naturally coupled*</span> if $(F,F')$ has law $\mu({\mathrm{d}}{\mathsf{f}})K_j({\mathsf{f}},{\mathrm{d}}{\mathsf{f}}')$, where $\mu$ is the law of $F$ on ${\mathsf{F}}_j(k)$. Using (ii) in Lemma \[sec:coupling-1\], it is then easy to obtain the next result.

\[sec:coupling-2\] If $F_j$ is uniform in ${\mathsf{F}}_j(k)$ and $(F_j,F'_j)$ are naturally coupled, then the law of $F'_j$ is that of the multiset induced by $k$ i.i.d. uniform elements in ${\mathsf{T}}_j$.

Next, we define a Markov kernel $K({\mathsf{t}},\cdot)$ on ${\mathsf{T}}^{(m)}$, in an inductive way. Let $K(\bullet,\{\bullet\})=1$. Assume that the measure $K({\mathsf{t}},\cdot)$ on ${\mathsf{T}}_{\#{\mathsf{t}}}^{(m)}$ has been defined for every ${\mathsf{t}}\in{\mathsf{T}}^{(m)}$ with $\#{\mathsf{t}}\leq n-1$. Take ${\mathsf{t}}\in {\mathsf{T}}^{(m)}_n$, and let $\lambda=\lambda({\mathsf{t}}),p=p(\lambda)$. Let ${\mathsf{f}}_j({\mathsf{t}})\in
{\mathsf{F}}_j(m_j(\lambda)),1\leq j\leq n-1$ be the multisets of trees born from the root of ${\mathsf{t}}$, respectively with size $j$. Let ${\mathsf{f}}_j'({\mathsf{t}})$ be independent random multisets, respectively with law $K_j({\mathsf{f}}_j({\mathsf{t}}),\cdot)$. We relabel the $p$ elements of the multisets ${\mathsf{f}}'_j({\mathsf{t}}),1\leq j\leq n-1$ as ${\mathsf{t}}_{(1)},\ldots,{\mathsf{t}}_{(p)}$, in non-increasing order of size, so that $\#{\mathsf{t}}_{(i)}=\lambda_i$ — if there is some $j$ with $m_j(\lambda)\geq 2$, we arrange the trees with same size in exchangeable random order. All these trees are in ${\mathsf{T}}^{(m)}$ and have at most $n-1$ vertices. By the induction hypothesis, conditionally on this family, we can consider another family ${\mathsf{t}}_{(1)}',\ldots,{\mathsf{t}}_{(p)}'$ of independent trees with respective laws $K({\mathsf{t}}_{(i)},\cdot)$. Let $K({\mathsf{t}},\cdot)$ be the law of the tree $\langle {\mathsf{t}}'_{(i)},1\leq i\leq p \rangle$. This procedure allows to define the Markov kernel $K({\mathsf{t}},\cdot)$ for every tree in ${\mathsf{T}}^{(m)}$.

We say that the random trees $(T,T')$, defined on a common probability space, are <span>*naturally coupled*</span> if the law of $(T,T')$ is $\mu({\mathrm{d}}{\mathsf{t}})K({\mathsf{t}},{\mathrm{d}}{\mathsf{t}}')$, where $\mu$ is the law of $T$. Is is easy to see that for every random variable $T$ on ${\mathsf{T}}^{(m)}$ with law $\mu$, then, possibly to the cost of enlarging the probability space supporting $T$, one can construct a random variable $T'$ so that $(T,T')$ is naturally coupled.

\[Lemmapetito\] Let $T_n$ have law $\mu_n$ and $(T_n,T'_n)$ be naturally coupled. Endow these trees respectively with the measures $\mu_{T_n}$ and $\mu_{T'_n}$. Then,

<span>(i)</span> the tree $T'_n$ has distribution ${\mathsf{Q}}^q_n$, for every $n\geq 1$,

<span>(ii)</span> for all $a>0$, the Gromov-Hausdorff-Prokhorov distance between $aT_n$ and $aT_n'$ is at most $2aj^*$ where $j^*$ is the supremum integer $j\geq 1$ so that there exist two subtrees of $T_n$ with size $j$, born from the same vertex and which are equal (with the convention $\sup\varnothing=0$),

<span>(iii)</span> for all $\varepsilon>0$, $\mathbb E\left
[d_{\mathrm{GHP}}(n^{-\varepsilon}T_n,n^{-\varepsilon}T'_n ) \right]
\rightarrow 0$ as $n \rightarrow \infty$.

<span>**Proof.** </span> We prove <span>(i)</span> by induction. For $n=1$ the property is obvious. Assume the property holds for every index up to $n-1$, and condition on $\lambda(T_n)=\lambda$, which by definition has probability $q_{n-1}(\lambda)$. As noticed before Lemma \[sec:coupling-1\], the multisets $F_j={\mathsf{f}}_j(T_n),1\leq j\leq n-1$ are independent, respectively uniform in ${\mathsf{F}}_j(m_j(\lambda))$. Conditionally on $F_j,1\leq j\leq n-1$, let $F'_j,1\leq j\leq n-1$ be independent with respective laws $K_j(F_j,\cdot)$. By Lemma \[sec:coupling-2\], we obtain that $F'_j$ is the multiset induced by a sequence of $m_j(\lambda)$ i.i.d. random variables, with law $\mu_j$. Consequently, if we relabel the elements of $F'_j,1\leq j\leq n-1$ as $T_{(1)},\ldots,T_{(p)}$ in non-increasing order of size (and exchangeable random order for trees with same size), then we obtain that these trees are independent, respectively with distribution $\mu_{\lambda_j}$. Since, by definition of $K$, the natural coupling $(T_n,T'_n)$ is obtained by letting $T'_n=\langle T'_{(i)},1\leq i\leq p\rangle$ where $(T_{(i)},T'_{(i)})$ are naturally coupled, we readily obtain the Markov branching property, with branching laws $(q_n,n\geq 1)$.

For (ii), we again apply an induction argument. The statement is trivial for $n=1$. Now, in the first step of the natural coupling, the action of the Markov kernel $K_j$ on ${\mathsf{f}}_j(T_n)$ leaves it unchanged if ${\mathsf{f}}_j(T_n)\in A_j$, i.e. if there are no ties in the multiset ${\mathsf{f}}_j(T_n)$. Consequently, with same notations as in the previous paragraph, a subtree of $T_n$ born from the root that appears with multiplicity $1$ will also appear among $T_{(1)},\ldots,T_{(p)}$.

Moreover, subtrees that are replaced are always replaced by trees with the same number of vertices and a tree with $j$ vertices and edge-lengths $a$ has height at most $aj$. So the Gromov-Hausdorff-Prokhorov distance between two trees with edge-lengths $a$ that both decompose above the root in subtrees of same size $j$ is at most $2aj$ (it is implicit in this proof that all trees are endowed with the uniform measure on their vertices). We now appeal to the following elementary

<span>**Fact.** </span>Let ${\mathsf{t}},{\mathsf{t}}'$ be such that $k=p(\lambda({\mathsf{t}}))=p(\lambda({\mathsf{t}}'))$, and let ${\mathsf{t}}=\langle
{\mathsf{t}}_{(1)},\ldots,{\mathsf{t}}_{(k)}\rangle$ and ${\mathsf{t}}'=\langle
{\mathsf{t}}'_{(1)},\ldots,{\mathsf{t}}'_{(k)}\rangle$ with $\# {\mathsf{t}}_{(i)}=\# {\mathsf{t}}'_{(i)}$ for $1 \leq i \leq k$. Then for every $a>0$, $$d_{\mathrm{GHP}}(a{\mathsf{t}},a{\mathsf{t}}')\leq \max_{1\leq i\leq
  k}d_{\mathrm{GHP}}(a{\mathsf{t}}_{(i)},a{\mathsf{t}}_{(i)}')\, .$$

From this we deduce that the Gromov-Hausdorff-Prokhorov distance between $aT_n$ and $aT'_n$ is at most $$\big(2a\sup\{1\leq j \leq
n-1:F_j\in A_j^c\} \big)\vee \sup_{\substack{1\leq j\leq n-1\\F_j\in
    A_j}}\sup_{i:\#T_{(i)}=j}d_{\mathrm{GHP}}(aT_{(i)},aT'_{(i)})\,
,$$ where $(T_{(i)},T'_{(i)})$ is the natural coupling. The induction hypothesis allows to conclude.

Last, for (iii), fix $\varepsilon \in (0,1)$. The Gromov-Hausdorff-Prokhorov distance between $n^{-\varepsilon}T_n$ and $n^{-\varepsilon}T'_n$ is bounded from above by $2n^{1-\varepsilon}$ for all $n \geq 1$. Next, for $\gamma \in (0,1)$, let $A_n^{\gamma}$ be the subset of trees of ${\mathsf{T}}^{(m)}_{n}$ that have at least two subtrees born from the same vertex that are identical, and with size larger than $n^{\gamma}$. By (ii), when $T_n \notin A_n^{\gamma}$, $d_{\mathrm{GHP}}(n^{-\varepsilon}T_n ,n^{-\varepsilon}T'_n) \leq
2n^{\gamma-\varepsilon}$. Hence, $$\begin{aligned}
\mathbb E\left
        [d_{\mathrm{GHP}}(n^{-\varepsilon}T_n,n^{-\varepsilon}T'_n )
          \right] &=&\mathbb E\big
        [d_{\mathrm{GHP}}(n^{-\varepsilon}T_n,n^{-\varepsilon}T'_n )
          \mathbf 1_{\{T_n \in A^{\gamma}_n\}}\big]+ \mathbb
        E\big
        [d_{\mathrm{GHP}}(n^{-\varepsilon}T_n,n^{-\varepsilon}T'_n )
          \mathbf 1_{\{ T_n \notin A^{\gamma}_n \}}\big] \\ &\leq
        & 2n^{1-\varepsilon}\mathbb P(T_n \in A_n^{\gamma})+ 2n^{\gamma-\varepsilon}.\end{aligned}$$ Taking $\gamma<\varepsilon$ and using Lemma \[negligible\] following right below, we get the result.

\[negligible\] For $\gamma \in (0,1)$, let $A_n^{\gamma}$ be the subset of ${\mathsf{T}}^{(m)}_{n}$ of trees $\mathsf t$ that have at least one vertex $v$ such that at least two subtrees born from $v$ are equal and have at least $n^{\gamma}$ vertices. Then, $$\mathbb P(T_n \in A_n^{\gamma})=O(\rho^{-n^{\gamma}}n^{5/2}) \text{ as } n
\rightarrow \infty.$$

This lemma will be an easy consequence of the following result. For every tree ${\mathsf{t}}$ and any vertex $v$ of ${\mathsf{t}}$, we let $\mathsf t^{(v)}$ denote the subtree of $\mathsf t$ rooted at $v$. When $v^*$ is taken uniformly at random among the vertices of $\mathsf t$, we set $\mathsf t^{(*)}:=\mathsf t^{(v^*)}$.

\[lemmuniform\] The distribution of $T_n^{(*)}$ conditionally on $\# T_n^{(*)}=k$ is uniform on ${\mathsf{T}}^{(m)}_k$, for every $1 \leq k \leq n$.

Note that the event $\{\# T_n^{(*)}=k\}$ has a strictly positive probability for all $1 \leq k
\leq n$.

<span>**Proof.**</span> Let $k \in \{1,\ldots,n\}$. For all ${\mathsf{t}}_0
\in {\mathsf{T}}^{(m)}_k$, using that $\mathbb P(T_n =\mathsf t)=1/\mathbf
T_n^{(m)}$ for ${\mathsf{t}}\in {\mathsf{T}}_n^{(m)}$, $$\begin{aligned}
\mathbb P\big (T_n^{(*)} = {\mathsf{t}}_0 \big)&=&
\sum_{\mathsf t \in {\mathsf{T}}^{(m)}_n} \mathbb
P\big(T_n^{(*)} = \mathsf t_0 | T_n =\mathsf t\big)
\mathbb P(T_n =\mathsf t) \\ &=& \frac{1}{\mathbf T^{(m)}_n}\sum_{\mathsf t \in
  {\mathsf{T}}^{(m)}_n} \mathbb P({\mathsf{t}}^{(*)}={\mathsf{t}}_0)\\
  &=&\frac{1}{n{\mathbf{T}}^{(m)}_n}\sum_{{\mathsf{t}}\in {\mathsf{T}}^{(m)}_n,v\in {\mathsf{t}}}{\mathbf{1}}_{\{{\mathsf{t}}^{(v)}={\mathsf{t}}_0\}}.\end{aligned}$$ This quantity is independent of ${\mathsf{t}}_0 \in {\mathsf{T}}^{(m)}_k$, because there is an obvious bijection between the sets $\{({\mathsf{t}},v):{\mathsf{t}}\in {\mathsf{T}}^{(m)}_n,v\in {\mathsf{t}},{\mathsf{t}}^{(v)}={\mathsf{t}}_0\}$ and $\{({\mathsf{t}},v):{\mathsf{t}}\in {\mathsf{T}}^{(m)}_n,v\in {\mathsf{t}},{\mathsf{t}}^{(v)}={\mathsf{t}}_1\}$ for ${\mathsf{t}}_1\in {\mathsf{T}}^{(m)}_k$. Hence the result. $\hfill \square$

<span>**Proof of Lemma \[negligible\].**</span> Let $A_{n}^{\gamma}(k)$ be the subset of trees of $ {\mathsf{T}}^{(m)}_k$ whose decomposition above the root gives birth to at least two identical subtrees with size greater than $ n^{\gamma}$, $k \leq n$. We first give an upper bound for the probability $\mathbb P(T_k \in A_n^{\gamma}(k))$. To do so, we bound from above the number of trees of $ {\mathsf{T}}^{(m)}_k$ that decompose in at least two identical subtrees of size $i $ ($i \leq (k-1)/2$): there are $
\mathbf T^{(m)}_i $ choices for the tree with size $i$ appearing twice. Then, there are $\mathbf T^{(m)}_{k-2i} $ forests with $k-1-2i$ vertices. Gluing the twins trees and a forest with $k-1-2i$ vertices to a common root gives a tree with $k$ vertices (and a root branching in possibly more than $m$ subtrees) and all trees in ${\mathsf{T}}^{(m)}_{k}$ with at least two subtrees with size $i$ can be obtained like this. From this we deduce that the cardinal of $A_{n}^{\gamma}(k)$ is at most $\sum_{i = n^{\gamma}}^{(k-1)/2} \mathbf T^{(m)}_i 
\mathbf T^{(m)}_{k-2i} $. In particular, using (\[eq:20\]) and the fact that $\rho>1$, $$\begin{aligned}
\mathbb P\left(T_k \in A_{n}^{\gamma}(k) \right) \leq \frac{1}{
  \mathbf T^{(m)}_k }\sum_{i = n^{\gamma}}^{(k-1)/2} \mathbf T^{(m)}_i 
\mathbf T^{(m)}_{k-2i}  \leq C \frac{k^{3/2}}{\rho^k} \sum_{i =
  n^{\gamma}}^{(k-1)/2}\frac{\rho^{i}\rho^{k-2i}}{i^{3/2}} \leq C
n^{3/2}\rho^{-n^{\gamma}},\end{aligned}$$ where $C$ is a generic constant independent of $n$ and $k \leq
n$. Now, in the following lines, given $T_n$, we let $v_1,v_2,\ldots,v_n$ denote its vertices labeled uniformly at random, $$\begin{aligned}
\mathbb P\left(T_n \in A_n^{\gamma} \right) &\leq& \mathbb E\left[
  \sum_{v \in T_n}\mathbf 1_{\{T_n^{(v)} \in A^{\gamma}_{n}(\#
      T_n^{(v)} )\}}\right] =\mathbb E\left[ \sum_{i=1}^n\mathbf
  1_{\{T_n^{(v_i)} \in A_{n}^{\gamma}(\# T_n^{(v_i)} )\}}\right] \\ &=& n
\mathbb P\left( T_n^{(*)} \in A_{n}^{\gamma}(\#
  T_n^{(*)} )\right) \\
&\underset{\text{by Lemma \ref{lemmuniform}}}=& n \sum_{k=1}^n \mathbb
P\left( T_k \in A_{n}^{\gamma}(k) \right) \mathbb P\big(\#
T_n^{(*)}=k\big) \\ &\leq & C 
n^{5/2}\rho^{-n^{\gamma}} \sum_{k=1}^n \mathbb P\big(\#
T_n^{(*)}=k \big) = C n^{5/2}\rho^{-n^{\gamma}}.\end{aligned}$$ $\hfill$ $\square$

Hypothesis **(H)** and conclusion {#PolyaH2}
---------------------------------

It remains to check that the family of probability distributions on $\mathcal P_{n}, n \geq 1$ defined by $$q_n(\lambda)=\mathbb P\left(\lambda(T_{n+1})=\lambda\right)=\mathbb
P\left(\lambda(T'_{n+1})=\lambda\right)=\frac{\mathbf S_{n+1}^{(\lambda)}}{\mathbf T^{(m)}_{n+1}},
\quad \forall \lambda \in \mathcal P_{n},$$ satisfies the assumption **(H)** with $\gamma=1/2$, $\ell \equiv 1$ and $\nu$ proportional to the Brownian dislocation measure $\nu_2$. For this we recall and fix some more notations:

1.  ${\widetilde}{\mathsf{T}}^{(m)} _{n} $ is the subset of ${\mathsf{T}}^{(m)}_{n}$ of trees with root degree less or equal to $m-2$

2.  ${\widetilde}{\mathbf{T}}^{(m)} _{n} $ is the cardinal of ${\widetilde}{{\mathsf{T}}}^{(m)} _{n} $, and $\psi^{(m)}(x)=\sum_{n\geq
      1}{\mathbf{T}}^{(m)}_nx^n$, ${\widetilde}{\psi}^{(m)}(x)=\sum_{n\geq
      1}{\widetilde}{{\mathbf{T}}}^{(m)}_nx^n$

3.  for $\lambda=(\lambda_1,\lambda_2,\ldots) \in \mathcal
      P_n$, set $\lambda_{\mathrm r}:=\sum _{i=3}^{\infty}\lambda_i = n
      -\lambda_1-\lambda_2$

The main result of this section then reads

\[PropH2\] For all $2 \leq m \leq \infty$, and all continuous functions $f :
\mathcal S^{\downarrow} \rightarrow \mathbb R$ such that $|f(\mathbf
s)| \leq 1-s_1$ for $\mathbf s \in \mathcal S^{\downarrow}$, $$\sqrt n \sum_{\lambda \in \mathcal P_n}
f\left(\frac{\lambda}{n}\right) \frac{\mathbf
  S^{(\lambda)}_{n+1}}{\mathbf T_{n+1}^{(m)}} \underset{n \rightarrow
  \infty}\longrightarrow \kappa {\widetilde}{\psi}^{(m)}(1/\rho)
\int_{1/2}^1 \frac{f(x,1-x,0,\ldots)
}{x^{3/2}(1-x)^{3/2}} \mathrm dx.$$

Note that the sum in the limit above is finite, since ${\widetilde}{\mathbf{T}}^{(m)} _{k}  \leq \mathbf T^{(m)}_{k} \leq K \rho^{k}/k^{3/2}$. This sum is explicit in terms of $\kappa$ and $\rho$ when $m=2$ or $m=\infty$. See Section \[sec:appl-polya-trees\] for details.

With this proposition, it is easy to conclude the proof of Theorem \[sec:main-results-2\]. Indeed, together with Theorem \[sec:main-result-2\] and Proposition \[Lemmapetito\] (i), it leads to the convergence $$\frac{1}{\sqrt n} T'_n\overset{(\mathrm d)} {\underset{n
    \rightarrow \infty}\longrightarrow } c_m\mathcal T_{1/2,\nu_{2} }$$ for the Gromov-Hausdorff-Prokhorov topology, where $c_m=\sqrt
2/(\sqrt \pi \kappa {\widetilde}{\psi}(1/\rho))$. Then, by Proposition \[Lemmapetito\] (iii) and since $(\mathcal M_{\mathrm w},
d_{\mathrm{GH}})$ is a complete separable space, we can apply a Slutsky-type theorem to get $$\frac{1}{\sqrt n} T_n \overset{(\mathrm d)} {\underset{n \rightarrow
    \infty}\longrightarrow } c_m \mathcal T_{1/2,\nu_{2} }.$$

The rest of this section is devoted to the proof of Proposition \[PropH2\].

### Negligible terms {#prelim}

We show in this section that the set of partitions $\lambda \in \mathcal P_n$ where either $\lambda_1\geq n(1-\varepsilon)$ or $\lambda_{\mathrm r} \geq n\varepsilon$ plays a negligible role in the limit of Proposition \[PropH2\] when we first let $n \rightarrow \infty$ and then $\varepsilon \rightarrow 0$.

\[lem5\] There exists $C \in (0,\infty)$ such that, for all $0<\varepsilon<1$, $$\limsup_{n \rightarrow \infty} \frac{\sqrt n}{\mathbf T_{n+1}^{(m)}} \sum_{\lambda \in \mathcal P_n} \mathbf 1_{\{\lambda_1 \geq n(1-\varepsilon)\}}\left(1-\frac{\lambda_1}{n}\right) \mathbf S^{(\lambda)}_{n+1}\leq \frac{C\sqrt \varepsilon}{(1-\varepsilon)^{3/2}}.$$

**Proof.** Using (\[bound1\]) and then (\[eq:20\]), we get $$\begin{aligned}
\sum_{\lambda \in \mathcal P_n, \lambda_1 \geq n(1-\varepsilon)}
  \left(1-\frac{\lambda_1}{n}\right) \mathbf S^{(\lambda)}_{n+1}  & \leq &
  \sum_{\lambda_1 = \lceil n(1-\varepsilon) \rceil}^n
  \left(1-\frac{\lambda_1}{n}\right) \mathbf T_{\lambda_1}^{(m)}
  \sum_{\mu \in \mathcal P_{n-\lambda_1}}
  \mathbf S_{n+1-\lambda_1}^{(\mu)} \\ &\leq& \sum_{\lambda_1= \lceil
    n(1-\varepsilon) \rceil}^n \left(1-\frac{\lambda_1}{n}\right) \mathbf T^{(m)}_{\lambda_1}  \mathbf T^{(m)}_{n+1-\lambda_1} \\ & \leq & K^2
  \rho ^{n+1} \sum_{\lambda_1= \lceil n(1 -\varepsilon) \rceil }^{n-1}
  \frac{1-\frac{\lambda_1}{n}}{\lambda_1^{3/2}(n+1-\lambda_1)^{3/2}}
  \\ &\leq& \frac{K^2 \rho ^{n+1}}{(n(1-\varepsilon))^{3/2}}\times
  \frac{1}{n^{3/2}} \times \sum_{\lambda_1= \lceil n(1 -\varepsilon)
    \rceil }^{n-1} \frac{1}{(1-\lambda_1/n)^{1/2}}.
 \end{aligned}$$ We conclude with the fact that the sum $ \sum_{\lambda_1= \lceil n(1 -\varepsilon)
    \rceil }^{n-1} (1-\lambda_1/n)^{-1/2}$ is smaller than the integral $ \int_{n(1-\varepsilon)}^n (1-x/n)^{-1/2} \mathrm dx = 2n \sqrt \varepsilon$, and then use the lower bound of (\[eq:20\]) for $\mathbf T_{n+1}^{(m)}$. $\hfill \square$

To deal with the partitions where $\lambda_{\mathrm r} \geq
n\varepsilon$, we need the following lemma when $m=\infty$. We denote by $\mathbf T^{(\infty,a-)}_{n}$ the number of trees of ${\mathsf{T}}^{(\infty)}_{n}$ whose subtrees born from the root have sizes at most $a$, $a \geq 1$.

\[lemmadeg\] Let $m=\infty$. There exists $A,B>0$ such that $$\mathbf T^{(\infty,a-)}_{k+1} \leq
A\rho^{k}\exp(-B k/a ), \quad \forall k \in \mathbb N  \text{\ \ and } a \geq 1.$$

**Proof.** Recall that ${\mathsf{T}}$ denotes the set of all (rooted, unordered) trees and rewrite the power series $\psi=\psi^{(\infty)}$ as $ \psi(x)=\sum_{\mathsf t \in {\mathsf{T}}} x^{\#
  \mathsf t}$. According to @FlSe09 [Section VII.5] its radius of convergence is $1/\rho<1$ and $\psi(1/\rho)=1$. Note also that $\psi(0)=0$. Now, we consider a random tree $T$ in ${\mathsf{T}}$ with distribution defined by $$\mathbb P(T=\mathsf t)=\rho^{-\# \mathsf t}.$$ If $c_{\varnothing}(\mathsf t)$ denotes the degree of the root of $\mathsf t$, we just have to show that $$\label{eqdeg}
\mathbb P(c_\varnothing(T)=r) \leq A' \exp(-B'r), \text{ for
  some } A',B'>0 \text{ and all }r \geq 1.$$ Indeed, each tree with $k+1$ vertices and a decomposition in subtrees with sizes at most $a$ has a root degree larger or equal to $k/a$. So, if the above inequality holds, we will have $$\mathbf T^{(\infty,a-)}_{k+1} \leq \rho^{k+1} \mathbb
P\big(c_\varnothing (T)\geq k/a , T \in {\mathsf{T}}^{(\infty)}_{k+1} \big)
\leq \rho^{k+1} A' B'^{-1} \exp(-B'(k/a-1)),$$ as required. To get (\[eqdeg\]), note that $$\mathbb P(c_\varnothing(T)=r)=\sum_{\mathsf t \in {\mathsf{T}},
  c_\varnothing(\mathsf t)=r} \rho^{-\# \mathsf t} = \sum_{k=1}^r
\frac{1}{ k !} \sum_{ \substack{{\mathsf{t}}_1,\ldots,{\mathsf{t}}_k \in {\mathsf{T}}\\ \text{
      pairwise distinct} }} \sum_{\substack{m_1+\ldots+m_k=r \\ m_i
    \geq 1}} \rho^{-1-\sum_{ 1 \leq i\leq k} m_i \# t_i}$$ which is obtained by considering the multiset of $r$ subtrees of a tree $\mathsf t$, made of $k$ distinct trees with multiplicities $m_1,\ldots,m_k$. Hence, $$\begin{aligned}
\mathbb P(c_\varnothing(T)=r) &\leq& \rho^{-1} \sum_{k=1}^r
\frac{1}{ k !} \sum_{\substack{m_1+\ldots+m_k=r \\ m_i \geq 1}}
\prod_{i=1}^k\psi( \rho^{-m_i}) \\ & =& \rho^{-1} \sum_{k=1}^{\lfloor
  cr \rfloor} \frac{1}{ k !} \sum_{\substack{m_1+\ldots+m_k=r \\ m_i \geq
    1}} \prod_{i=1}^k\psi( \rho^{-m_i}) + \rho^{-1} \sum_{k={\lfloor
    cr \rfloor +1}}^r \frac{1}{ k !} \sum_{\substack{m_1+\ldots+m_k=r
    \\ m_i \geq 1}} \prod_{i=1}^k\psi( \rho^{-m_i})\end{aligned}$$ where the $c \in ]0,1[$ chosen for this split will be specified below.

We first bound from above the second term. Using that $\psi(\rho^{-m_i}) \leq \psi(\rho^{-1})=1$ for $m_i \geq 1$ and that $\sum_{m_1+\ldots+m_k=r , m_i \geq 1} =\binom{r-1}{k-1}$, we obtain $$\sum_{k={\lfloor cr \rfloor +1}}^r \frac{1}{ k !}
  \sum_{\substack{m_1+\ldots+m_k=r \\ m_i \geq 1}} \prod_{i=1}^k\psi(
  \rho^{-m_i}) \leq \frac{1}{\lfloor cr \rfloor !} \sum_{k=1}^r
\binom{r-1}{k-1}
\leq
    \frac{2^{r-1}}{\lfloor cr \rfloor !},$$ which decays exponentially fast as $r \rightarrow \infty$, for every $ c \in ]0,1[$.

Now we will check that the sum $ \sum_{k=1}^{\lfloor cr \rfloor}
\frac{1}{ k !} \sum_{m_1+\ldots+m_k=r , m_i \geq 1} \prod_{i=1}^k\psi(
\rho^{-m_i}) $ also decays exponentially in $r$, provided that $c \in
        ]0,1[$ is chosen sufficiently small. Since $\psi(0)=0$, we have that $\psi(x) \leq Cx$ for some $C<\infty$ and all $x
          \in [0,\rho^{-1}]$. Hence $$\begin{aligned}
\sum_{k=1}^{\lfloor cr \rfloor} \frac{1}{ k !}
\sum_{\substack{m_1+\ldots+m_k=r \\ m_i \geq 1}} \prod_{i=1}^k\psi(
\rho^{-m_i}) &\leq &\sum_{k=1}^{\lfloor cr \rfloor} \frac{C^k}{ k !}
\sum_{\substack{m_1+\ldots+m_k=r \\ m_i \geq 1}} \prod_{i=1}^k
\rho^{-m_i} \\ &\leq & \exp(C) \sum_{k=1}^{\lfloor cr \rfloor}
\rho^{-r} \binom{r-1}{k-1} \\ &\underset{ \text{ for all } \lambda
  >0}\leq& \exp(C) \rho^{-r} \sum_{k=r-\lfloor cr \rfloor}^{r-1}
\binom{r-1}{k} \exp\left(\lambda k- \lambda (r-\lfloor cr
\rfloor)\right) \\ & \leq & \exp(C) \left(\rho^{-1} \exp(-\lambda
(1-c)) (\exp(\lambda )+1)\right)^r.\end{aligned}$$ When $c \rightarrow 0$, $\rho^{-1} \exp(-\lambda (1-c)) (\exp(\lambda
)+1) \rightarrow \rho^{-1} (1+\exp(-\lambda ))$, which is strictly smaller than $1$ for $\lambda$ large enough. Hence, fix such a large $\lambda$ and then take $c>0$ sufficiently small so that $\rho^{-1}
\exp(-\lambda (1-c)) (\exp(\lambda )+1)<1$. This ends the proof. $\hfill \square$

\[lem6\] For all $\varepsilon>0$, $$\frac{\sqrt n}{\mathbf T_{n+1}^{(m)}} \sum_{\lambda \in \mathcal P_n}
\mathbf 1_{\{\lambda_{\mathrm r}  \geq n \varepsilon \}}
\mathbf S^{(\lambda)}_{n+1} \underset{n
  \rightarrow \infty}\longrightarrow 0.$$

<span>**Proof.**</span> $\bullet$ If $m=2$, $\lambda_{\mathrm r} =0$ for all $\lambda \in \mathcal P_n$ and the assertion is obvious.

$\bullet$ Assume now that $3 \leq m<\infty$ and note that when $\lambda \in \mathcal P_n$ with $p(\lambda) \leq m$, one has that $\lambda_{\mathrm r}  \geq
n\varepsilon$ implies $(m-2) \lambda_3 \geq n \varepsilon$, in particular $\lambda_1 \geq \lambda_2 \geq n\varepsilon/(m-2)$. Hence, $$\sum_{\lambda \in \mathcal P_n} \mathbf 1_{\{\lambda_{\mathrm r}  \geq n
    \varepsilon \}}   \mathbf S^{(\lambda)}_{n+1}  
      \leq  \sum_{\lambda_{\mathrm r} = \lceil n\varepsilon \rceil }^{n-2}
  \sum_{\lambda_1=\lceil
    n\varepsilon/(m-2 \rceil)}^{\lfloor n-\lambda_{\mathrm r} -n\varepsilon/(m-2) \rfloor^+} \mathbf T^{(m)}_{\lambda_1} \mathbf T^{(m)}_{n-\lambda_{\mathrm r} -\lambda_1}
   \mathbf T^{(m)}_{\lambda_{\mathrm r} +1}.$$ Then for $C$ a generic constant, using (\[eq:20\]), the latter term multiplied by $\sqrt n / \mathbf T_{n+1}^{(m)}$ is bounded from above by $$\begin{aligned}
  &&   Cn^{1/2} (n+1)^{3/2} \sum_{\lambda_{\mathrm r} =\lceil
    n\varepsilon \rceil}^{n-2} \sum_{\lambda_1= \lceil
    n\varepsilon/(m-2)\rceil}^{\lfloor n-\lambda_{\mathrm r} -n\varepsilon/(m-2) \rfloor ^+} \frac{1}{
    \lambda_1^{3/2}(n-\lambda_{\mathrm r} -\lambda_1)^{3/2}(\lambda_{\mathrm r} +1)^{3/2}}
  \\ &\leq& C
  \frac{n^2(n-2)(\lfloor n-n\varepsilon/(m-2)\rfloor ^+)}{n^{3*3/2}}
  =O\left( \frac{1}{\sqrt n}\right).\end{aligned}$$

$\bullet$ Next we turn to the case where $m=\infty$. Let $\gamma \in (5/6,1)$. On the one hand, by the same token as for the $m<\infty$ cases, $$\begin{aligned}
\frac{\sqrt n}{\mathbf T^{(\infty)}_{n+1}}\sum_{\lambda \in \mathcal P_n} \mathbf 1_{\{\lambda_{\mathrm r}  \geq n
    \varepsilon \}} \mathbf 1_{\{\lambda_2 \geq n^{\gamma} \}}
   \mathbf S^{(\lambda)}_{n+1}  &\leq& C n^2 \sum_{\lambda_{\mathrm r} = \lceil
    n\varepsilon \rceil}^{n-2} \sum_{\lambda_1= \lceil n^{\gamma}
    \rceil}^{\lfloor n-\lambda_{\mathrm r} -n^{\gamma} \rfloor ^+} \frac{1}{
    \lambda_1^{3/2}(n-\lambda_{\mathrm r} -\lambda_1)^{3/2}(\lambda_{\mathrm r} +1)^{3/2}}
  \\ &\leq& C
  \frac{n^4}{n^{3\gamma + 3/2}} =O\left(
  n^{5/2-3\gamma}\right)=o(1),\end{aligned}$$ since $5/2-3\gamma<0$ when $\gamma>5/6$. On the other hand, we use Lemma \[lemmadeg\] to get $$\begin{aligned}
\frac{\sqrt n}{\mathbf T^{(\infty)}_{n+1}}\sum_{\lambda \in \mathcal P_n} \mathbf 1_{\{\lambda_{\mathrm r}  \geq n
  \varepsilon \}} \mathbf 1_{\{\lambda_2< n^{\gamma} \}}
\mathbf S^{(\lambda)}_{n+1} &\leq &\frac{\sqrt n}{\mathbf T^{(\infty)}_{n+1}} \sum_{\lambda_{\mathrm r} = \lceil n\varepsilon \rceil}^{n-2}
\sum_{\lambda_1= 1}^{n-\lambda_{\mathrm r} -1} \mathbf T_{\lambda_1}^{(\infty)} \mathbf T^{(\infty)}_{n-\lambda_{\mathrm r} -\lambda_1} \mathbf T^{(\infty,n^{\gamma}-)}_{\lambda_{\mathrm r} +1} 
\\ &\leq & Cn^4
\exp(-Bn^{1-\gamma}\varepsilon)= o\big( 1 \big).\end{aligned}$$ $\hfill$ $\square$

### Proof of Proposition \[PropH2\] {#preuveProp}

We rely on the following lemma. Let $\mathcal P_n^{\mathrm{bin}}$ be the subset of $\mathcal P_n$ of partitions of $n$ with exactly two parts.

\[lem4\] Let $f:\mathcal S^{\downarrow} \rightarrow \mathbb R$ be continuous. <span>(i)</span> For all $a \in \mathbb Z_+$ and all $\varepsilon \in
(0,1)$, as $n \rightarrow \infty$, $$\frac{\sqrt n}{ \mathbf T_{n+1}^{(m)}} \sum_{\substack{\lambda \in \mathcal
  P^{\mathrm{bin}}_{n-a} \\ \lambda_1 \leq n(1-\varepsilon)}}
f\left(\frac{\lambda_1}{n},\frac{\lambda_2+a}{n},0,\ldots \right)
\mathbf S_{n+1-a}^{(\lambda)} \longrightarrow \frac{\kappa}{\rho^{1+a}}
\int_{1/2}^{1-\varepsilon} \frac{ f(x,1-x,0,\ldots)}{x^{3/2}(1-x)^{3/2}}
\mathrm dx.$$

<span>(ii)</span> Moreover, there exists $C_{\varepsilon} \in
(0,\infty)$ such that, for all $n \geq 1$, all $0 \leq a \leq
n\varepsilon/2$ and all non-increasing non-negative sequences $(a_i,i\geq 1)$ with $\sum_{i \geq 1} a_i \leq a/n $, $$\left |\frac{\sqrt n}{\mathbf T_{n+1}^{(m)}}\sum_{\substack{\lambda
    \in \mathcal P^{\mathrm{bin}}_{n-a} \\ \lambda_1 \leq
    n(1-\varepsilon)}}
f\left(\frac{\lambda_1}{n},\frac{\lambda_2}{n}+a_1,a_2,a_3,\ldots
\right)\mathbf S_{n+1-a}^{(\lambda)} \mathbf T^{(m)}_{a+1} \right
|\leq \frac{C_{\varepsilon}}{(a+1)^{3/2}}.$$

<span>**Proof.**</span> (i) For large enough $n$, $$\begin{aligned}
\sum_{\substack{\lambda \in \mathcal P^{\mathrm{bin}}_{n-a}
    \\ \lambda_1 \leq n(1-\varepsilon)}}
f\left(\frac{\lambda_1}{n},\frac{\lambda_2+a}{n},0,\ldots \right)
\mathbf S_{n+1-a}^{(\lambda)}&=&
f\left(\frac{1}{2}-\frac{a}{2n},\frac{1}{2}+\frac{a}{2n},0,\ldots
\right){\mathbf{F}}_{(n-a)/2}(2) \mathbf 1_{\{ n-a \text{ is
    even}\}}\\ &+&\sum_{\lambda_1=\lfloor (n-a)/2 \rfloor+1}^{\lfloor
  n(1-\varepsilon) \rfloor}
f\left(\frac{\lambda_1}{n},1-\frac{\lambda_1}{n},0,\ldots \right)
\mathbf T^{(m)}_{\lambda_1} \mathbf T^{(m)}_{n-a-\lambda_1}.\end{aligned}$$ On the one hand, by Otter's approximation result for $\mathbf T_{(n-a)/2}^{(m)}$ $${\mathbf{F}}_{(n-a)/2}(2) = \mathbf T_{(n-a)/2}^{(m)}\big(\mathbf T_{(n-a)/2}^{(m)}+1\big) /2 \sim \kappa^2 \rho^{n-a}((n-a)/2)^{-3}/2 =o
(\mathbf T_{n+1}^{(m)} /\sqrt n ).$$ On the other hand, still using Otter's result, we get that for all $\eta>0$, provided that $n$ is large enough, $$\begin{aligned}
&&\frac{\sqrt n}{ \mathbf T_{n+1}^{(m)}} \sum_{\lambda_1=\lfloor (n-a)/2
    \rfloor+1}^{\lfloor n(1-\varepsilon) \rfloor}
  f\left(\frac{\lambda_1}{n},1-\frac{\lambda_1}{n},0,\ldots \right) \mathbf T^{(m)}_{\lambda_1} \mathbf T^{(m)}_{n-a-\lambda_1} \\ &\leq&
  \frac{(\kappa+\eta)^2
    }{(\kappa-\eta)\rho^{1+a}}\frac{1}{n}\sum_{\lambda_1=\lfloor(n-a)/2
    \rfloor+1}^{\lfloor n(1-{\varepsilon}) \rfloor}
  f\left(\frac{\lambda_1}{n},1-\frac{\lambda_1}{n},0,\ldots \right)
  \frac{(n+1)^{3/2}}{\lambda_1^{3/2}}\times\frac{n^{3/2}}
       {(n-a-\lambda_1)^{3/2}} \\ &\underset{n \rightarrow
         \infty}\longrightarrow& \frac{(\kappa+\eta)^2
         }{(\kappa-\eta)\rho^{1+a}} \int_{1/2}^{1-\varepsilon}
       \frac{f(x,1-x,0,\ldots) }{x^{3/2}(1-x)^{3/2}} \mathrm dx.\end{aligned}$$ Letting $\eta \rightarrow 0$, this gives $$\begin{aligned}
 \limsup_{n \rightarrow \infty}\frac{\sqrt n}{ \mathbf T_{n+1}^{(m)}}
 \sum_{\lambda_1=\lfloor (n-a)/2 \rfloor+1}^{\lfloor n(1-\varepsilon)
   \rfloor}
 f\left(\frac{\lambda_1}{n},1-\frac{\lambda_1}{n},0,\ldots \right) \mathbf T^{(m)}_{\lambda_1} \mathbf T^{(m)}_{n-a-\lambda_1} \leq \frac{\kappa}{
 \rho^{1+a}}\int_{1/2}^{1-\varepsilon}\frac{ f(x,1-x,0,\ldots)
 }{x^{3/2}(1-x)^{3/2}} \mathrm dx.\end{aligned}$$ We obtain the liminf similarly, hence (i).

\(ii) We will use that $\mathbf S_{n+1-a}^{(\lambda)}\leq \mathbf T_{\lambda_1}^{(m)} \mathbf T_{n-a-\lambda_1}^{(m)}$ for all $\lambda \in \mathcal P^{\mathrm{bin}}_{n-a}$. Recall that $f$ is bounded on $\mathcal S^{\downarrow}$. There exits then a generic constant $C$ independent of $n$ and $a \leq n \varepsilon/2$ such that $$\begin{aligned}
&& \Bigg |\frac{\sqrt n}{\mathbf T_{n+1}^{(m)}}\sum_{\lambda \in \mathcal
    P^{\mathrm{bin}}_{n-a}, \lambda_1 \leq n(1-\varepsilon)}
  f\left(\frac{\lambda_1}{n},\frac{\lambda_2}{n}+a_1,a_2,a_3,\ldots \right)\mathbf S_{n+1-a}^{(\lambda)}
  \mathbf T^{(m)}_{a+1} \Bigg | \\ &\leq&\frac{C\sqrt n}{ \mathbf T^{(m)}_{n+1}}
  \sum_{\lambda_1=\lceil (n-a)/2 \rceil}^{\lfloor n(1-\varepsilon)
    \rfloor} \mathbf
  T^{(m)}_{\lambda_1} \mathbf T^{(m)}_{n-a-\lambda_1} \mathbf T^{(m)}_{a+1}
 \\  &\leq &  \frac{C}{ (a+1)^{3/2}
  }\frac{1}{n}\sum_{\lambda_1=\lceil (n-a)/2 \rceil}^{\lfloor
    n(1-\varepsilon) \rfloor}   \frac{(n+1)^{3/2}}{\lambda_1^{3/2}}\times
  \frac{n^{3/2}}{(n-a-\lambda_1)^{3/2}} \\ &\leq& \frac{C}{ (a+1)^{3/2}
  }\frac{1}{n}\sum_{\lambda_1 = \lceil n(1-\varepsilon/2)/2
    \rceil}^{\lfloor n(1-\varepsilon) \rfloor}
  \frac{n^{3/2}}{\lambda_1^{3/2}} \times
  \frac{n^{3/2}}{(n-\lambda_1)^{3/2}}\end{aligned}$$ where we have used for the last inequality that $n-a \geq
n(1-\varepsilon/2)$ since $a \leq n \varepsilon/2$ and that $n-a-\lambda_1
\geq (n-\lambda_1)/2$ since $a \leq n \varepsilon/2$ and $\lambda_1 \leq
n(1-\varepsilon)$. This upper bound is of the form $Cu_n/(a+1)^{3/2}$ where $(u_n,n \geq 1)$ is a sequence independent of $a$ converging to a finite limit as $n \rightarrow \infty$. Hence the result. $\hfill
\square$

**Proof of Proposition \[PropH2\].** By Lemmas \[lem5\] and \[lem6\], the set of partitions where either $\lambda_1\geq n(1-\varepsilon)$ or $\lambda_{\mathrm r} \geq n\varepsilon/3$ will play a negligible role in the limit when we first let $n \rightarrow \infty$ and then $\varepsilon \rightarrow 0$. Hence we concentrate first on the following sums (for $\varepsilon \in (0,1)$), where we use that for all $\lambda \in \mathcal P_n$, $\lambda_1 \leq
n(1-\varepsilon)$ and $\lambda_{\mathrm r}  \leq n \varepsilon/3$ implies $\lambda_2>\lambda_3$: $$\begin{aligned}
\label{eq1}
 \sum_{\substack{\lambda \in \mathcal P_n\\ \lambda_1 \leq
  n(1-\varepsilon), \lambda_{\mathrm r}  \leq n\varepsilon /3}}
f\left(\frac{\lambda}{n}\right)
\mathbf S^{(\lambda)}_{n+1} = \sum_{k=0}^{\lfloor n\varepsilon /3 \rfloor}
\sum _{\substack{\mu \in \mathcal P_{k}\\ p(\mu) \leq m-2}}\sum_{\substack{\lambda \in \mathcal
  P^{\mathrm{bin}}_{n-k} \\ \lambda_1 \leq n(1-\varepsilon)}}
f\left(\frac{\lambda_1}{n},\frac{\lambda_2+k}{n},0,\ldots \right)
\mathbf S^{(\lambda)}_{n-k+1}  \mathbf{ S}^{(\mu)}_{k+1}&& \\ \nonumber + \sum_{k=0}^{\lfloor n\varepsilon/3
  \rfloor} \sum _{\substack{\mu \in \mathcal P_{k} \\ p(\mu) \leq m-2}}\sum_{\substack{\lambda \in \mathcal
  P^{\mathrm{bin}}_{n-k} \\ \lambda_1 \leq n(1-\varepsilon)}} \left(
f\left(\frac{\lambda_1}{n},\frac{\lambda_2}{n},\frac{\mu_1}{n},\ldots \right)-f
\left(\frac{\lambda_1}{n},\frac{\lambda_2+k}{n},0,\ldots \right)\right)
\mathbf S^{(\lambda)}_{n-k+1}\mathbf{S}^{(\mu)}_{k+1}.&&\end{aligned}$$ The first sum in the right-hand side of (\[eq1\]) is equal to $$\label{eq4}
\sum_{k=0}^{\lfloor n\varepsilon/3 \rfloor} \sum_{\lambda \in \mathcal
  P^{\mathrm{bin}}_{n-k} , \lambda_1 \leq n(1-\varepsilon)}
f\left(\frac{\lambda_1}{n},\frac{\lambda_2+k}{n},0,\ldots \right)
\mathbf S^{(\lambda)}_{n-k+1} \mathbf{\tilde T}^{(m)} _{k+1},$$ which, multiplied by $\sqrt n / \mathbf T_{n+1}^{(m)}$, according to Lemma \[lem4\] (i) and (ii) ((ii) implies dominated convergence), converges to $$\label{eq2}
\sum_{k=0}^{\infty} {\widetilde}{\mathbf{T}}^{(m)} _{k+1}  \frac{\kappa}{\rho^{1+k}} \int_{1/2}^{1-\varepsilon}
\frac{f(x,1-x,0,\ldots)}{x^{3/2}(1-x)^{3/2}} \mathrm dx.$$ Next, let $\delta>0$. Since $f$ is continuous (hence uniformly continuous) on the compact set $\mathcal S^{\downarrow}$, we can choose ${\varepsilon}$ small enough so that the absolute value of the second sum in the right-hand side of (\[eq1\]) is bounded from above by $$\label{eq6}
2 \sum_{k=0}^{\lfloor n\varepsilon/3 \rfloor} \sum_{\lambda \in
   \mathcal P^{\mathrm{bin}}_{n-k}, \lambda_1 \leq n(1-\varepsilon)}
 \left(\delta \wedge \left(1-\frac{\lambda_1}{n}
 \right)\right) \mathbf S^{(\lambda)}_{n-k+1} {\widetilde}{\mathbf{ T}}^{(m)} _{k+1}\, .$$ Similarly as above, when multiplied by $\sqrt n / \mathbf T^{(m)}_{n+1}$, this quantity converges to $$\label{eq3}
2 \sum_{k=0}^{\infty}{\widetilde}{\mathbf{T}}^{(m)} _{k+1} \frac{\kappa}{\rho^{1+k}} \int_{1/2}^{1-\varepsilon}\frac{
\delta \wedge(1-x)}{x^{3/2}(1-x)^{3/2}} \mathrm
dx \leq 2 \sum_{k=0}^{\infty}{\widetilde}{\mathbf{T}}^{(m)} _{k+1} \frac{\kappa}{\rho^{1+k}} \int_{1/2}^{1}\frac{
\delta \wedge(1-x)}{x^{3/2}(1-x)^{3/2}} \mathrm
dx$$ by Lemma \[lem4\] (i) and (ii).

Now let $\eta>0$ be fixed. For $\delta$ and $\varepsilon$ sufficiently small, the terms (\[eq3\]) and the limsup of Lemma \[lem5\] are smaller than $\eta$, and the term (\[eq2\]) is in a neighborhood of radius $\eta$ of the intended limit $$\label{eq7}
\kappa \sum_{k=0}^{\infty}\frac{ {\widetilde}{\mathbf{ T}}^{(m)} _{k+1}  }{ \rho^{k+1}} \int_{1/2}^1
\frac{ f(x,1-x,0,\ldots)}{x^{3/2}(1-x)^{3/2}} \mathrm dx.$$ Next, such small $\delta$ and $\varepsilon$ being fixed, letting $n \rightarrow
\infty$, and using Lemma \[lem6\] and the convergences of (\[eq4\]) to (\[eq2\]) and of (\[eq6\]) to (\[eq3\]), we get that $ \sqrt n \sum_{\lambda \in \mathcal P_n}
f\left(\frac{\lambda}{n} \right)
\mathbf S^{(\lambda)}_{n+1}/\mathbf T_{n+1}^{(m)} $ is indeed in a neighborhood of radius $7\eta$ of (\[eq7\]) for all $n$ large enough. $\hfill \square$

[^1]: Ceremade, Université Paris-Dauphine

[^2]: Département de Mathématiques d'Orsay, Université Paris-Sud

[^3]: This work is partially supported by ANR-08-BLAN-0190 and ANR-08-BLAN-0220-01

[^4]: usually such spaces are rather called <span>*pointed*</span>, but we prefer the term rooted which is more common when dealing with trees

[^5]: There is one subtlety in this statement, which is in the case $C=\{i\}$ for some $i\in {\mathbb{N}}$. Indeed, by construction we have $T_C=\bullet$ a.s., and this is the only place where we have to require that $q_1(\emptyset)=1$.

[^6]: Recall that a multiset with $k$ elements in some set $A$ is an element of the quotient set $A^k/\mathfrak{S}_k$, where $\mathfrak{S}_k$ acts in the natural way by permutation of components.

{'source': 'arXiv_out/1003'}