Aurélien Bellet
email: aurelien.bellet@univ-st-etienne.fr

Amaury Habrard
email: amaury.habrard@lif.univ-mrs.fr

Marc Sebban
email: marc.sebban@univ-st-etienne.fr

Learning Good Edit Similarities with Generalization Guarantees ⋆

Keywords:

Similarity and distance functions are essential to many learning algorithms, thus training them has attracted a lot of interest. When it comes to dealing with structured data (e.g., strings or trees), edit similarities are widely used, and there exists a few methods for learning them. However, these methods offer no theoretical guarantee as to the generalization performance and discriminative power of the resulting similarities. Recently, a theory of learning with (ǫ, γ, τ )-good similarity functions was proposed. This new theory bridges the gap between the properties of a similarity function and its performance in classification. In this paper, we propose a novel edit similarity learning approach (GESL) driven by the idea of (ǫ, γ, τ )-goodness, which allows us to derive generalization guarantees using the notion of uniform stability. We experimentally show that edit similarities learned with our method induce classification models that are both more accurate and sparser than those induced by the edit distance or edit similarities learned with a state-of-the-art method.

Introduction

Similarity and distance functions between objects play an important role in many supervised and unsupervised learning methods, among which the popular k-nearest neighbors, k-means and support vector machines. For this reason, a lot of research has gone into automatically learning similarity or distance functions from data, which is usually referred to as metric learning. When data consists in numerical vectors, a common approach is to learn the parameters (i.e., the transformation matrix) of a Mahalanobis distance [START_REF] Yang | Distance Metric Learning: A Comprehensive Survey[END_REF][START_REF] Davis | Information-theoretic metric learning[END_REF][START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF][START_REF] Jin | Regularized distance metric learning: Theory and algorithm[END_REF].

Because they involve more complex procedures, less work has been devoted to learning such functions from structured data (for example strings or trees). Still, there exists a few methods for learning edit distance-based functions. Roughly speaking, the edit distance between two objects is the cost of the best sequence of ⋆ Preprint submitted to ECML PKDD 2011.

operations (insertion, deletion, substitution) required to transform an object into another, where an edit cost is assigned to each possible operation. Most generalpurpose methods for learning the edit cost matrix maximize the likelihood of the data using EM-based iterative methods [START_REF] Ristad | Learning String-Edit Distance[END_REF][START_REF] Bilenko | Adaptive Duplicate Detection Using Learnable String Similarity Measures[END_REF][START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF][START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF][START_REF] Takasu | Bayesian Similarity Model Estimation for Approximate Recognized Text Search[END_REF], which can imply a costly learning phase. Saigo et al. [START_REF] Saigo | Optimizing amino acid substitution matrices with a local alignment kernel[END_REF] manage to avoid this drawback in the context of remote homologies detection in protein sequences by applying gradient descent to a specific objective function. Some of the above methods do not guarantee to find the optimal parameters and/or are only based on a training set of positive pairs: they do not take advantage of pairs of examples that have different labels. Above all, none of these methods offer theoretical guarantees that the learned edit functions will generalize well to unseen examples (while it is the case for some Mahalanobis distance learning methods [START_REF] Jin | Regularized distance metric learning: Theory and algorithm[END_REF]) and lead to good performance for the classification or clustering task at hand. Recently, Balcan et al. [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF][START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF] introduced a theory of learning with so-called (ǫ, γ, τ )-good similarity functions that gives intuitive, sufficient conditions for a similarity function to allow one to learn well. Essentially, a similarity function K is (ǫ, γ, τ )-good if an ǫ proportion of examples are on average 2γ more similar to reasonable examples of the same class than to reasonable examples of the opposite class, where a τ proportion of examples must be reasonable. K does not have to be a metric nor positive semi-definite (PSD). They show that if K is (ǫ, γ, τ )-good, then it can be used to build a linear separator in an explicit projection space that has margin γ and error arbitrarily close to ǫ. This separator can be learned efficiently using a linear program and is supposedly sparse.

In this article, we propose a novel edit similarity learning procedure driven by the notion of good similarity function. Our approach (GESL, for Good Edit Similarity Learning) is formulated as an efficient convex programming approach allowing us to learn the edit costs so as to optimize the (ǫ, γ, τ )-goodness of the resulting similarity function. We provide a bound based on the notion of uniform stability [START_REF] Bousquet | Stability and generalization[END_REF] that guarantees that our learned similarity will generalize well and induce low-error classifiers. This bound is independent of the size of the alphabet, making GESL suitable for handling problems with large alphabet. To the best of our knowledge, this work is the first attempt to establish a theoretical relationship between a learned edit similarity function and its generalization and discriminative power. We show in a comparative experimental study that GESL has fast convergence and leads to more accurate and sparser classifiers than other edit similarities. This paper is organized as follows. In Section 2, we introduce a few notations, and review the theory of Balcan et al. as well as some prior work on edit similarity learning. In Section 3, which is the core of this paper, we present GESL, our approach to learning good edit similarities. We then propose a theoretical analysis of GESL based on uniform stability, leading to the derivation of a generalization bound. An experimental evaluation of our approach is provided in Section 4. Finally, we conclude this work by outlining promising lines of research on similarity learning.

Notations and Related Work

We consider the following binary classification problem: we are given some labeled examples (x, ℓ) drawn from an unknown distribution P over X × {-1, 1}, where X is the instance space. We want to learn a classifier h : X → {-1, 1} whose error rate is as low as possible using pairwise similarities according to a similarity function K : X × X → [-1, 1]. We say that K is symmetric if for all x, x ′ ∈ X, K(x, x ′ ) = K(x ′ , x). K is a valid (or Mercer) kernel if it is symmetric and PSD.

Learning with Good Similarity Functions

In recent work, Balcan et al. [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF][START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF] introduced a new theory of learning with good similarity functions. Their motivation was to overcome two major limitations of kernel theory. First, a good kernel is essentially a good similarity function, but the theory talks in terms of margin in an implicit, possibly unknown projection space, which can be a problem for intuition and design. Second, the PSD and symmetry requirement often rules out natural similarity functions for the problem at hand. As a consequence, Balcan et al. proposed the following definition of good similarity function.

Definition 1 (Balcan et al. [START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF]). A similarity function K is an (ǫ, γ, τ )good similarity function in hinge loss for a learning problem P if there exists a (random) indicator function R(x) defining a (probabilistic) set of "reasonable points" such that the following conditions hold:

1. E (x,ℓ)∼P [[1 -ℓg(x)/γ] + ] ≤ ǫ, where g(x) = E (x ′ ,ℓ ′ )∼P [ℓ ′ K(x, x ′ )|R(x ′ )] and [1 -c] + = max(0, 1 -c) is the hinge loss, 2. Pr x ′ [R(x ′ )] ≥ τ .
Thinking of this definition in terms of number of margin violations, we can interpret the first condition as an ǫ proportion of examples x are on average 2γ more similar to random reasonable examples of the same class than to random reasonable examples of the opposite class and the second condition as at least a τ proportion of the examples should be reasonable. Note that other definitions are possible, like those proposed in [START_REF] Wang | On Learning with Dissimilarity Functions[END_REF] for unbounded dissimilarity functions. Yet Definition 1 is very interesting in two respects. First, it includes all good kernels as well as some non-PSD similarity functions. In that sense, this is a strict generalization of the notion of good kernel [START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF]. Second, these conditions are sufficient to learn well, i.e., to induce a linear separator α in an explicit space that has low-error relative to L 1 -margin γ. This is formalized in Theorem 1.

Theorem 1 (Balcan et al. [START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF]). Let K be an (ǫ, γ, τ )-good similarity function in hinge loss for a learning problem P . For any ǫ 1 > 0 and 0

≤ δ ≤ γǫ 1 /4, let S = {x ′ 1 , . . . , x ′ d } be a (potentially unlabeled) sample of d = 2 τ log(2/δ) + 16 log(2/δ) (ǫ1γ) 2
landmarks drawn from P . Consider the mapping φ S : X → R d defined as follows:

φ S i (x) = K(x, x ′ i ), i ∈ {1, .
. . , d}. Then, with probability at least 1 -δ over the random sample S, the induced distribution φ S (P ) in R d has a linear separator α of error at most ǫ + ǫ 1 at margin γ.

Therefore, if we are given an (ǫ, γ, τ )-good similarity function for a learning problem P and enough (unlabeled) landmark examples, then with high probability there exists a low-error linear separator α in the explicit "φ-space", which is essentially the space of the similarities to the d landmarks. As Balcan et al. mention, using d u unlabeled examples and d l labeled examples, we can efficiently find this separator α ∈ R du by solving the following linear program (LP):

3 min α d l i=1   1 - du j=1 α j ℓ i K(x i , x ′ j )   + + λ α 1 . (1)
Note that Problem (1) is essentially a 1-norm SVM problem [START_REF] Zhu | 1-norm Support Vector Machines[END_REF] with an empirical similarity map [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF], and can be efficiently solved. The L 1 -regularization induces sparsity in α: it allows us to automatically select useful landmarks (the reasonable points), ignoring the others, whose corresponding coordinates in α will be set to zero during learning. We can also control the sparsity of the solution directly: the larger λ, the sparser α. Therefore, one does not need to know in advance the set of reasonable points R, it is automatically worked out while learning α.

Our objective in this paper is to make use of the theory of Balcan et al. to efficiently learn (ǫ, γ, τ )-good edit similarities from data that will lead to effective classifiers. In the next section, we review some past work on edit cost learning.

String Edit Similarity Learning

The classic edit distance, known as the Levenshtein distance, is defined as follows.

Definition 2. The Levenshtein distance e L (x, x ′ ) between strings x = x 1 . . . x t and x ′ = x ′ 1 . . . x ′ v is the minimum number of edit operations to change x into x ′ . The allowable operations are insertion, deletion and substitution of a symbol. e L can be computed in O(|x| • |x ′ |) time using dynamic programming. Instead of only counting the minimum number of required operations, we can set a cost (or probability) for each edit operation. These parameters are usually represented as a positive cost matrix C of size (A + 1) × (A + 1), where A is the size of A, the alphabet x and x ′ have been generated from (the additional row and column account for insertion and deletion costs respectively). C i,j gives the cost of the operation changing the symbol c i into c j , c i and c j ∈ A ∪ {$}, where $ is the empty symbol. Given C, a generalized edit similarity e C can be defined as being the cost corresponding to the sequence of minimum cost. This sequence is called the optimal edit script.

Using a matrix C that is appropriately tuned to the considered task can lead to significant improvements in performance. For some applications, such matrices may be available, like BLOSUM in the context of protein sequence alignment [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF]. However, in most domains it is not the case, and tuning the costs is difficult. For this reason, methods for learning C from data have attracted a lot of interest. Most general-purpose approaches take the form of probabilistic models. Parameter estimation methods of edit transducers were used to infer generative models [START_REF] Ristad | Learning String-Edit Distance[END_REF][START_REF] Bilenko | Adaptive Duplicate Detection Using Learnable String Similarity Measures[END_REF][START_REF] Takasu | Bayesian Similarity Model Estimation for Approximate Recognized Text Search[END_REF], discriminative models [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF] or tree edit models [START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF].

Note that the above approaches usually use an Expectation-Maximization (EM)-based algorithm to estimate the parameters of probabilistic models. Beyond the fact that EM is not guaranteed to converge to a global optimum, it can also cause two major drawbacks in the context of edit distance learning. First, since EM is iterative, parameter estimation and distance calculations must be performed several times until convergence, which can be expensive to compute, especially when the size of the alphabet and/or the length of the strings are large. Second, by maximizing the likelihood of the data, one only considers pairs of strings of the same class (positive pairs) while it may be interesting to make use of the information brought by pairs of strings that have a different label (negative pairs). As a consequence, the above methods "move closer together" examples of the same class, without trying to also "move away from each other" examples of different class. In [START_REF] Mccallum | A Conditional Random Field for Discriminatively-trained Finite-state String Edit Distance[END_REF], McCallum et al. consider discriminative conditional random fields, dealing with positive and negative pairs in specific states, but still using EM for parameter estimation. To overcome the drawback of iterative approaches for the task of detecting remote homology in protein sequences, Saigo et al. [START_REF] Saigo | Optimizing amino acid substitution matrices with a local alignment kernel[END_REF] optimize by gradient descent an objective function meant to favor the discrimination between positive and negative examples. But this is done by only using positive pairs of distant homologs.

Despite their diversity, a common feature shared by all of the above approaches is that they do not optimize similarity functions to be (ǫ, γ, τ )-good and thus do not take advantage of the theoretical results of Balcan et al.'s framework. In other words, there is no theoretical guarantee that the learned edit functions will work well for the classification or clustering task at hand. In the next section, we propose a novel approach that bridges this gap.

Learning (ǫ, γ, τ )-Good Edit Similarity Functions

What makes the edit costs C hard and expensive to optimize is the fact that the edit distance is based on an optimal script which depends on the edit costs themselves. This is the reason why, as we have seen earlier, iterative approaches are very commonly used to learn C from data. In this section, we take a novel convex programming approach based on the theory of Balcan et al. to learn (ǫ, γ, τ )good edit similarity functions from both positive and negative pairs without requiring a costly iterative procedure. Moreover, this new framework allows us to derive a generalization bound establishing the convergence of our method and a relationship between the learned similarities and their (ǫ, γ, τ )-goodness.

An Exponential-based Edit Similarity Function

Let #(x, x ′ ) be a (A + 1) × (A + 1) matrix whose each component # i,j (x, x ′ ) is the number of times the edit operation (i, j) is used to turn x into x ′ in the optimal Levenshtein script, 0 ≤ i, j ≤ A. We define the following edit function:

e G (x, x ′ ) = 0≤i,j≤A C i,j # i,j (x, x ′ ).
Note that to compute e G , we do not extract the optimal script with respect to C: we use the Levenshtein script 4 and apply custom costs C to it. Therefore, since the edit script defined by #(x, x ′ ) is fixed, e G (x, x ′ ) is nothing more than a linear function of the edit costs and can be optimized directly.

Recall that in the framework of Balcan et al., a similarity function must be in [-1, 1]. To respect this requirement, we define our similarity function to be:

K G (x, x ′ ) = 2e -eG(x,x ′ ) -1.
The motivation for this exponential form is related to the one for using exponential kernels in SVM classifiers: it can be seen as a way to introduce nonlinearity to further separate examples of opposite class while moving closer those of the same class. Note that K G may not be PSD nor symmetric. However, as we have seen earlier, Balcan et al.'s theory does not require these properties, unlike SVM.

Learning the Edit Costs: Problem Formulation

We aim at learning an edit cost matrix C so as to optimize the (ǫ, γ, τ )-goodness of K G . It would be tempting to try to find a way to directly optimize Definition 1. Unfortunately, this is very difficult for two reasons. First, it would result in a nonconvex formulation (summing/subtracting up exponential terms). Second, we do not know the set R of reasonable points in advance (R is inferred when learning the classifier). Instead, we propose to optimize the following criterion:

E (x,ℓ) E (x ′ ,ℓ ′ ) [1 -ℓℓ ′ K G (x, x ′ )/γ] + |R(x ′ ) ≤ ǫ ′ . (2)
Criterion (2) bounds that of Definition 1 due to the convexity of the hinge loss.

It is harder to satisfy since the "goodness" is required with respect to each reasonable point instead of considering the average similarity to these points.

Clearly, if K G satisfies (2), then it is (ǫ, γ, τ )-good with ǫ ≤ ǫ ′ . Let us consider a training sample of N T labeled points T = {z i = (x i , ℓ i )} NT i=1 and a sample of landmark examples S L = {z ′ j = (x ′ j , ℓ ′ j )} NL j=1 .
Note that these examples must be labeled in order to allow us to move closer examples of the same class and to separate points of opposite class. In practice, S L can be a subsample of the training sample T . Recall that the goodness of a similarity only relies on some relevant subset of examples: the reasonable points. Therefore, in the general case, a relevant strategy does not consist in optimizing the similarity with respect to all the landmarks, but rather to some particular ones allowing a high margin with low violation. In order to model this, we suppose the existence of an indicator matching function f land : T × S L → {0, 1} that associates to each element x ∈ T a non empty set of landmark points. We say that x ′ ∈ S L is a landmark point for x ∈ T if and only if f land (x, x ′ ) = 1. We suppose that f land matches exactly N L landmark points to each x ∈ T . We will discuss in Section 3.4 how we can build f land .

Our formulation requires the goodness for each (

x i , x ′ j ) with f land (x i , x ′ j ) = 1. Therefore, we want 1 -ℓ i ℓ ′ j K G (x i , x ′ j )/γ + = 0, hence ℓ i ℓ ′ j K G (x i , x ′ j ) ≥ γ.
A benefit from using this constraint is that it can easily be turned into an equivalent linear one, considering the following two cases.

1. If ℓ i = ℓ ′ j , we get:

-K G (x i , x ′ j ) ≥ γ ⇐⇒ e -eG(xi,x ′ j ) ≤ 1 -γ 2 ⇐⇒ e G (x i , x ′ j ) ≥ -log( 1 -γ 2 ).
We can use a variable B 1 ≥ 0 and write the constraint as e G (x i , x ′ j ) ≥ B 1 , with the interpretation that

B 1 = -log( 1-γ 2 ). In fact, B 1 ≥ -log( 1 2 ). 2. Likewise, if ℓ i = ℓ ′ j , we get e G (x i , x ′ j ) ≤ -log( 1+γ 2
). We can use a variable B 2 ≥ 0 and write the constraint as e G (x i , x ′ j ) ≤ B 2 , with the interpretation that B 2 =log( 1+γ2 ). In fact, B 2 ∈ 0,log( 12 ) .

The optimization problem GESL can then be expressed as follows:

(GESL) min

C,B1,B2 1 NT NL 1≤i≤NL, 1≤j≤NT , f land (xi,x ′ j )=1 V (C, z i , z ′ j ) + β C 2 s.t. V (C, z i , z ′ j ) = [B1 -e G (x i , x ′ j )] + if ℓ i = ℓ ′ j [e G (x i , x ′ j ) -B2] + if ℓ i = ℓ ′ j B 1 ≥ -log( 1 2 ), 0 ≤ B 2 ≤ -log( 1 2 ), B 1 -B 2 = η γ C i,j ≥ 0, 0 ≤ i, j ≤ A,
where β ≥ 0 is a regularization parameter on edit costs, • denotes the Frobenius norm (which corresponds to the classical L 2 -norm when considering a matrix as a n × n vector) and η γ ≥ 0 a parameter corresponding to the desired "margin". The relationship between the margin γ and η γ is given by γ = e ηγ -1 e ηγ +1 . GESL is a convex program, thus we can efficiently find its global optimum. Using slack variables to express the hinge loss, it has O(N T N L + A 2 ) variables and O(N T N L ) constraints. Note that GESL is quite sparse: each constraint involves at most one string pair and a limited number of edit cost variables, making the problem faster to solve. It is also worth noting that our approach is very flexible. First, it is general enough to be used with any definition of e G that is based on an edit script (or even a convex combination of edit scripts). Second, one can incorporate additional convex constraints, which offers the possibility of including background knowledge or desired requirements on C (e.g., symmetry). Lastly, it can be easily adapted to the multi-class case.

In the next section, we derive a generalization bound guaranteeing not only the convergence of our learning method but also the overall goodness of the learned edit similarity function for the task at hand.

Theoretical Guarantees

The outline of this theoretical part is the following: considering that the pairs (z i , z ′ j ) used to learn C in GESL are not i.i.d., the classic results of statistical learning theory do not directly hold. To derive a generalization bound, extending the ideas of [START_REF] Jin | Regularized distance metric learning: Theory and algorithm[END_REF][START_REF] Bousquet | Stability and generalization[END_REF] to string edit similarity, we first prove that our learning method has a uniform stability. This is established in Theorem 2 using Lemma 1 and 2. The stability property allows us to derive our generalization bound (Theorem 4) using the McDiarmid inequality (Theorem 3).

In the following, we suppose every string length bounded by a constant W > 0, which is not a strong restriction. This implies that for any string pair, #(x 1 , x 2 ) ≤ W ,5 since the Levenshtein script contains at most max(|x 1 |, |x 2 |) operations. We denote the objective function of GESL by:

F T (C) = 1 N T NT k=1 1 N L NL j=1 V (C, z k , z ′ kj ) + β C 2 ,
where z ′ kj denotes the j th landmark associated to z k . The first term of F T (C), noted L T (C) in the following, is the empirical loss over the training sample T . Let us also define the loss over the true distribution P , called L(C), and the estimation error D T as follows:

L(C) = E z k ,z ′ j [V (C, z k , z ′ j )] ; D T = L(C T ) -L T (C T ),
where C T denotes the edit cost matrix learned by GESL from sample T . Our objective is to derive an upper bound on the generalization loss L(C T ) with respect to the empirical loss L T (C T ). A learning algorithm is stable [START_REF] Bousquet | Stability and generalization[END_REF] when its output does not change significantly under a small modification of the learning sample. We consider the following definition of uniform stability meaning that the replacement of one example must lead to a variation bounded in O(1/N T ) in terms of infinite norm.

Definition 3 (Jin et al. [4], Bousquet and Elisseeff [13]). A learning algorithm has a uniform stability in κ

NT , where κ is a positive constant, if

∀(T, z), |T | = N T , ∀i, sup z1,z2 |V (C T , z 1 , z 2 ) -V (C T i,z , z 1 , z 2 )| ≤ κ N T ,
where T i,z is the new set obtained by replacing z i ∈ T by a new example z.

To prove that GESL has the property of uniform stability, we need the following two lemmas (proven in Appendices 1 and 2).

Lemma 1. For any edit cost matrices C, C ′ and any examples z, z ′ :

|V (C, z, z ′ ) -V (C ′ , z, z ′ )| ≤ C -C ′ W.
Lemma 2. Let F T and F T i,z be the functions to optimize, C T and C T i,z their corresponding minimizers, and β the regularization parameter. Let ∆C = (C T -C T i,z ). For any t ∈ [0, 1]:

C T 2 -C T -t∆C 2 + C T i,z 2 -C T i,z + t∆C 2 ≤ (2N T + N L )t2W βN T N L ∆C .
Using Lemma 1 and 2, we can now prove the stability of GESL. Proof. Using t = 1/2 on the left-hand side of Lemma 2, we get

C T 2 -C T - 1 2 ∆C 2 + C T i,z 2 -C T i,z + 1 2 ∆C 2 = 1 2 ∆C 2 .
Then, applying Lemma 2, we get

∆C 2 ≤ 2(2N T + N L )W βN T N L ∆C ⇒ ∆C ≤ 2(2N T + N L )W βN T N L .
Now, from Lemma 1, we have for any z, z ′

|V (C T , z, z ′ ) -V (C T i,z , z, z ′ )| ≤ ∆C W ≤ 2(2N T + N L )W 2 βN T N L .
Replacing N L by αN T completes the proof. Now, using the property of stability, we can derive our generalization bound over L(C T ). This is done by using the McDiarmid inequality [START_REF] Mcdiarmid | On the method of bounded differences[END_REF].

Theorem 3 (McDiarmid inequality [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]). Let X 1 , . . . , X n be n independent random variables taking values in X and let

Z = f (X 1 , . . . , X n ). If for each 1 ≤ i ≤ n, there exists a constant c i such that sup x1,...,xn,x ′ i ∈X |f (x 1 , . . . , x n ) -f (x 1 , . . . , x ′ i , . . . , x n )| ≤ c i , ∀1 ≤ i ≤ n, then for any ǫ > 0, Pr[|Z -E[Z]| ≥ ǫ] ≤ 2 exp -2ǫ 2 n i=1 c 2 i .
To derive our bound on L(C T ), we just need to replace Z by D T in Theorem 3 and to bound E T [D T ] and |D T -D T i,z |, which is shown by the following lemmas (proven in Appendices 3 and 5).

Lemma 3. For any learning method of estimation error D T and satisfying a uniform stability in κ NT , we get E T [D T ] ≤ 2κ NT . Lemma 4. For any edit cost matrix learned by GESL using N T training examples and N L landmarks, with B γ = max(η γ , -log(1/2)), we have the following bound:

∀i, 1 ≤ i ≤ N T , ∀z, |D T -D T i,z | ≤ 2κ N T + (2N T + N L )( 2W √ βBγ + 3)B γ N T N L .
We are now able to derive our generalization bound over L(C T ).

L(C T ) ≤ L T (C T ) + 2 κ N T + 2κ + 2 + α α 2W βB γ + 3 B γ ln(2/δ) 2N T with κ = 2(2+α)W 2 αβ and B γ = max(η γ , -log(1/2)). Proof. Recall that D T = L(C T ) -L T (C T ). From Lemma 4, we get |D T -D T i,z | ≤ sup T,z ′ |D T -D T i,z ′ | ≤ 2κ + B N T with B = (2 + α) α 2W βB γ + 3 B γ .
Then by applying the McDiarmid inequality, we have

Pr[|D T -E T [D T ]| ≥ ǫ] ≤ 2 exp   - 2ǫ 2 NT i=1 (2κ+B) 2 N 2 T   ≤ 2 exp - 2ǫ 2 (2κ+B) 2 NT . (3)
By fixing δ = 2 exp -2ǫ 2 (2κ+B) 2 /NT , we get ǫ = (2κ + B) ln(2/δ) 2NT . Finally, from (3), Lemma 3 and the definition of D T , we have with probability at least 1 -δ:

D T < E T [D T ] + ǫ ⇒ L(C T ) < L T (C T ) + 2 κ N T + (2κ + B) ln(2/δ) 2N T .
This bound outlines three important features of our approach. First, it has a convergence in O( 1NT ), which is classical with the notion of uniform stability. Second, this rate of convergence is independent of the alphabet size, which means that our method should scale well to large alphabet problems. Lastly, thanks to the relation between the optimized criterion and Definition 1 that we established earlier, this bound also ensures the goodness in generalization of the learned similarity function. Therefore, by Theorem 1, it guarantees that the similarity will induce low-error classifiers for the classification task at hand.

Discussion on the matching function

The question of how one should define the matching function f land relates to the open question of building the training pairs in many metric or similarity learning problems. In some applications, it may be trivial: e.g., a misspelled word and its correction. Otherwise, popular choices are to pair each example with its nearest neighbor or to consider all possible pairs. In our case, matching each example with every landmark may result in a similarity function that performs very poorly, because requiring the goodness over all landmarks (including irrelevant ones) defines an over-constrained problem and does not capture the essence of Definition 1. Remember that on average, examples should be more similar to reasonable points of the same class than to reasonable points of the opposite class. In that sense, reasonable points "represent" the data well. Since classes have intra-class variability, a given reasonable point can only account for a subset of the data. Therefore, reasonable points must be somewhat complementary.

Keeping this in mind, we propose the following strategy, used in the experiments. Assuming an even distribution of classes in T , we use a positive parameter P ≤ N T /2 to pair each example with its P nearest neighbors of the same class in T and its P farthest neighbors of the opposite class in T , using the Levenshtein distance. Therefore, we have N L = 2P with N L = αN T , 0 < α ≤ 1 (where α is typically closer to 0 than to 1). In other words, we essentially take a few landmarks that are already good representatives of a given example and optimize the edit costs so that they become even better representatives. Note that the choice of the Levenshtein distance to determine the neighbors is consistent with our choice to define e G according to the Levenshtein script.

Experimental Results

In this section, we provide an experimental evaluation of the approach presented in Section 3. Using the learning rule (1) of Balcan et al., we compare three edit similarity functions:6 (i) K G , learned by GESL, 7 (ii) the Levenshtein distance e L , and (iii) an edit similarity function p e learned with the method of Oncina and Sebban [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF]. 8 The task is to learn a model to classify words as either English or French. We use the 2,000 top words lists from Wiktionary. 9First, we assess the convergence rate of the two considered edit cost learning methods (i and iii). We keep aside 600 words as a validation set to tune the parameters, using 5-fold cross-validation and selecting the value offering the best classification accuracy. We build bootstrap samples T from the remaining 2,000 words to learn the edit costs, as well as 600 words to train the separator α and 400 words to test its performance. Figure 1 shows the accuracy and sparsity results of each method with respect to N T , averaged over 5 runs. We see that K G leads to more accurate models than e L and p e for every size N T > 20. The difference is statistically significant: the Student's t-test yields p < 0.01. At the same time, K G requires considerably less reasonable points (thus speeding up classification). This clearly indicates that GESL leads to a better similarity than (ii) and (iii). Moreover, the convergence rate of GESL is very fast, considering that (26+1) 2 = 729 costs must be learned: it needs very few examples to outperform the Levenshtein distance, and about 200 examples to reach convergence. This provides experimental evidence that our method scales well with the size of the alphabet, as suggested by the generalization bound derived in Section 3.3. On the other hand, (iii) seems to suffer from the large number of costs to estimate: it needs a lot more examples to outperform Levenshtein (about 200) and convergence seems to be only reached at 1,000. Now, we assess the performance of the three edit similarities with respect to the number of examples d l used to learn the separator α. For K G and p e , we use the matrix that performed best in the previous experiment. Taking our set of 2,000 words, we keep aside 400 examples to test the models and build bootstrap samples from the remaining 1,600 words to learn α. Figure 2 shows the accuracy and sparsity results of each method with respect to d l , averaged over 5 runs. Again, K G outperforms e L and p e for every size d l (the difference is statistically significant with p < 0.01 using a Student's t-test) while always leading to much sparser models. Moreover, the size of the models induced by K G stabilizes for d l ≥ 400 while the accuracy still increases. This is not the case for the models induced by e L and p e , whose size keeps growing. To sum up, the best matrix learned by GESL outperforms the best matrix learned by [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF], which had been proven to perform better than other state-of-the-art methods.

Finally, one may wonder what kind of words are selected as reasonable points in the models. The intuition is that they should be some sort of "discriminative prototypes" the classifier is based on. Table 1 reasonable points obtained with K G using a set of 1,200 examples to learn α. 10 This small set actually carries a lot of discriminative patterns (shown in Table 2 along with their number of occurrences in each class over the entire dataset). For example, words ending with ly correspond to English words, while those ending with que characterize French words. Note that Table 1 also reflects the fact that English words are shorter on average (6.99) than French words (8.26) in the dataset, but the English (resp. French) reasonable points are significantly shorter (resp. longer) than the average (mean of 5.00 and 10.83 resp.), which allows better discrimination.

Conclusion and Future Work

In this work, we proposed a novel approach to the problem of learning edit similarities from data that induces (ǫ, γ, τ )-goodness. We derived a generalization bound using the notion of uniform stability that is independent from the size of the alphabet, making it suitable for problems involving large vocabularies. This 10 We used a high λ value in order to get a small set, thus making the analysis easier. w y k q nn gh ai ed$ ly$ es?$ ques?$ ^h English 146 144 83 [START_REF] Wang | On Learning with Dissimilarity Functions[END_REF] bound is related to the goodness of the resulting similarity, which gives guarantees that the similarity will induce accurate models for the task at hand. We experimentally showed that it is indeed the case and that the induced models are also sparser than if we use other (standard or learned) edit similarities. Our approach is flexible enough to be straightforwardly generalized to tree edit similarity learning: one just has to redefine e G to be a tree edit script. Considering that tree edit distances generally run in cubic time and that the methods for learning tree edit similarities available in the literature are mostly EM-based (thus requiring the distances to be recomputed many times), this seems a very promising avenue to explore. Finally, learning (ǫ, γ, τ )-good Mahalanobis distance could also be considered.

A Appendices

A.1 Proof of Lemma 1 Proof. |V (C, z, z ′ ) -V (C ′ , z, z ′ )| ≤ | 0≤i,j≤A (C i,j -C ′ i,j )# i,j (z, z ′ )| ≤ C - C ′ #(z, z ′ ) .
The first inequality uses the 1-lipschitz property of the hinge loss and the fact that B 1 's and B 2 's cancel out. The second one comes from the Cauchy-Schwartz inequality. 11 Finally, since #(z, z ′ ) ≤ W , the lemma holds.

A.2 Proof of Lemma 2 Proof. Let B = L T (C T +t∆C)-L T i,z (C T +t∆C)-(L T (C T )-L T i,z (C T )). Since L T , F T , L T i,z
and F T i,z are convex functions and using the fact that C T and C T i,z are minimizers of F T and F T i,z respectively, we get12 for any t ∈ [0, 1]: The second line is obtained by the fact that every z k in T , z k = z i , has at most two landmark points different between T and T i,z , and z and z i at most N L different landmarks. To complete the proof, we reorder the terms and use the 1lipschitz property, Cauchy-Schwartz, triangle inequalities and #(z, z ′ ) ≤ W . Proof. Since (C T , B 1 , B 2 ) is an optimal solution then the value reached by F T is lower than the one obtained with (0, B γ , 0), where 0 denotes the null matrix:

N T X k=1 1 NT N L X j=1 1 NL V (C, z k , z ′ k j ) + β CT 2 ≤ N T X k=1 1 NT N L X j=1 1 NL V (0, z k , z ′ k j ) + β 0 2 ≤ Bγ.
For the last inequality, note that V (0, z k , z ′ kj ) is bounded either by B γ or 0. Since |V (C T i,z , z1, z2)-V (C T i,z , z3, z4)|.

Theorem 2 .

 2 Let N T and N L be respectively the number of training examples and landmark points. Assuming that N L = αN T , α ∈ [0, 1], GESL has a uniform stability in κ NT , where κ = 2(2+α)W 2 βα .

Theorem 4 .

 4 Let T be a sample of N T randomly selected training examples and let C T be the edit costs learned by GESL with stability κ NT using N L = αN T landmark points. With probability 1 -δ, we have the following bound for L(C T ):

Fig. 1 .

 1 Fig. 1. Learning the costs: accuracy and sparsity results with respect to NT .

β ` CT 2 -≤ 2 (

 22 CT -t∆C 2 + C T i,z 2 -C T i,z + t∆C 2 ´≤ B.Then, using the previous upper bound B, we getB ≤ |LT (CT + t∆C) -L T i,z (CT + t∆C) + L T i,z (CT ) -LT (CT )| NT -1) + NL NT NL sup z 1 ,z 2 ∈T z 3 ,z 4 ∈T i,z |V (CT + t∆C, z1, z2) -V (CT , z1, z2) + V (CT , z3, z4) -V (CT + t∆C, z3, z4)| ≤ 2(NT -1) + NL NT NL t ∆C sup z 1 ,z 2 ∈T z 3 ,z 4 ∈T i,z ( #(z1, z2) + #(z3, z4) ) ≤ (2NT + NL)t2W NT NL ∆C .

A. 3 VV

 3 Proof of Lemma 3 Proof. ET [DT ] ≤ ET [E z,z ′ [V (CT , z, z ′ )] -LT (CT )] ≤ E T,z,z ′ [|V (CT , z, z ′ ) -(CT , z k , z ′ k j )|] ≤ E T,z,z ′ [CT , z, z ′ )-V (CT , z k , z ′ )+V (CT , z k , z ′ )(CT , z k , z ′ k j ))|].Since, T, z and z ′ are i.i.d. from distribution P , we do not change the expected value by replacing one point with another and thusE T,z,z ′ [|V (CT , z, z ′ ) -V (CT , z k , z ′ )|] = E T,z,z ′ [|V (CT , z, z ′ ) -V (C T k,z , z, z ′ )|].It suffices to apply this trick twice, combined with the triangle inequality and the property of stability in κ NT to lead to the lemma. A.4 Lemma 5 In order to bound |D T -D T i,z |, we need to bound C T . Lemma 5. Let (C T , B 1 , B 2 ) an optimal solution learned by GESL from a sample T , and let B γ = max(η γ , -log(1/2)), then C T ≤ Bγ β .

1 NL

 1 V (C, z k , z ′ kj ) ≥ 0, we get β C T 2 ≤ B γ .A.5 Proof of Lemma 4Proof. First, we derive a bound on|D T -D T i,z |. |DT -D T i,z | = |L(CT ) -LT (CT ) -(L(C T i,z ) -L T i,z (C T i,z ))| ≤ |L(CT ) -L(C T i,z )| + |LT (C T i,z ) -LT (CT )| + |L T i,z (C T i,z ) -LT (C T i,z )| ≤ Ez 1 ,z 2 [|V (CT , z1, z2) -V (C T i,z , z1, z2)|] T i,z , z k , z ′ k j ) -V (CT , z k , z ′ k j )| + |L T i,z (C T i,z ) -LT (C T i,z )| ≤ 2 κ NT + |L T i,z (C T i,z ) -LT (C T i,z )|.(by using the hypothesis of stability twice)Now, proving Lemma 4 boils down to bounding the last term above. Using similar arguments to the proof of Lemma 2,|L T i,z (C T i,z )-LT (C T i,z )| ≤ (2NT + NL) NT NL sup z 1 ,z 2 ∈T z 3 ,z 4 ∈T i,z

Table 1 .

 1 gives an example of a set of 11 Learning the separator: accuracy and sparsity results with respect to d l . Example of a set of 11 reasonable points.

		80									250
	Classification accuracy	65 70 75								Model size	200 100 150
		60									50
								eL								eL
								pe								pe
		55						KG			0					KG
		0	200	400	600	800	1000	1200	1400	1600	0	200	400	600	800	1000 1200 1400 1600
						dl									dl
		Fig. 2. English						French
			high showed holy		economiques americaines decouverte
			liked hardly			britannique informatique couverture

Table 2 .

 2 Some discriminative patterns extracted from the reasonable points of Table1(^: start of word, $: end of word, ?: 0 or 1 occurrence of preceding letter).

				5 34 39 151 51	265	0	62
	French	7	19	5 72 35 0 114 51	0	630	43	14

The original formulation proposed in[START_REF] Balcan | Improved Guarantees for Learning via Similarity Functions[END_REF] was actually L1-constrained. We transformed it into an equivalent L1-regularized one.

In practice, one could use another type of script. We picked the Levenshtein script because it is a "reasonable" edit script, since it corresponds to a shortest script transforming x into x ′ .

Also denoted #(z1, z2) for the sake of convenience when using labeled strings.

A similarity function that is not in [-1, 1] can be normalized.

In this series of experiments, we constrained the cost matrices to be symmetric in order not to be dependent on the order in which the examples are considered.

We used their software SEDiL, available online at http://labh-curien. univ-st-etienne.fr/SEDiL/

These lists are available at http://en.wiktionary.org/wiki/Wiktionary: Frequency_lists. We only considered unique words (i.e., not appearing in both lists) of length at least 4, and we also got rid of accent and punctuation marks. We ended up with about 1,300 words of each language over an alphabet of 26 symbols.

1-lipschitz implies |[X]+ -[Y ]+| ≤ |X -Y |, Cauchy-Schwartz | P n i=1 xiyi| ≤ x y .

Due to the limitation of space, the details of this construction are not presented in this paper. We advise the interested reader to have a look at Lemma 20 in[START_REF] Bousquet | Stability and generalization[END_REF].

We study two cases that need the 1-lipschtiz property of hinge loss and Lemma 5.


Romain Abraham
email: romain.abraham@univ-orleans.fr

Jean-Franc ¸ois Delmas
email: delmas@cermics.enpc.fr

β-COALESCENTS AND STABLE GALTON-WATSON TREES

Representation of coalescent process using pruning of trees has been used by Goldschmidt and Martin for the Bolthausen-Sznitman coalescent and by Abraham and Delmas for the β(3/2, 1/2)-coalescent. By considering a pruning procedure on stable Galton-Watson tree with n labeled leaves, we give a representation of the discrete β(1 + α, 1 -α)coalescent, with α ∈ [1/2, 1) starting from the trivial partition of the n first integers. The construction can also be made directly on the stable continuum Lévy tree, with parameter 1/α, simultaneously for all n. This representation allows to use results on the asymptotic number of coalescence events to get the asymptotic number of cuts in stable Galton-Watson tree (with infinite variance for the offspring distribution) needed to isolate the root. Using convergence of the stable Galton-Watson tree conditioned to have infinitely many leaves, one can get the asymptotic distribution of blocks in the last coalescence event in the β(1 + α, 1 -α)-coalescent.

1. Introduction 1.1. Framework. The idea of constructing coalescent processes by pruning discrete trees arises first in [START_REF] Goldschmidt | Random recursive trees and the Bolthausen-Sznitman coalescent[END_REF] where the Bolthausen-Sznitman coalescent is constructed by a uniform pruning of the branches of a random recursive tree, see also [START_REF] Schweinsberg | Dynamics of the evolving Bolthausen-Sznitman coalescent[END_REF] and [START_REF] Freund | Minimal clade size in the Bolthausen-Sznitman coalescent[END_REF] for applications of such a representation. The same kind of ideas has been used in [START_REF] Abraham | A construction of a β-coalescent via the pruning of binary trees[END_REF] to construct a β(3/1, 1/2)coalescent process using a uniform pruning of the branches of a uniform random binary tree. This construction is also closely related to Aldous's continuum random tree. The goal of this paper is to extend this result by applying a pruning at nodes (introduced in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF] in a continuous setting and in [START_REF] Abraham | Pruning Galton-Watson trees and tree-valued Markov processes[END_REF] in a discrete setting) to a stable Lévy tree, obtaining a β(1 + α, 1α)coalescent process, with 1/2 ≤ α < 1.

Let Λ be a finite measure on [0, 1]. A Λ-coalescent (Π(t), t ≥ 0) is a Markov process which takes values in the set of partitions of N * = {1, 2, . . .} introduced in [START_REF] Pitman | Coalescents with multiple collisions[END_REF] for coalescent processes with possible multiple collisions. It is defined via the transition rates of its restriction Π [n] = (Π [n] (t), t ≥ 0) to the n first integers: if Π [n] (t) is composed of b blocks, then k (2 ≤ k ≤ b) fixed blocks coalesce at rate:

(1)

λ b,k = 1 0 u k-2 (1 -u) b-k Λ(du).
In particular a coalescence event happens at rate:

(2)

λ b = b k=2 b k λ b,k .
We take the convention λ 1 = 0. We also define the discrete process Π

[n] dis = (Π

[n] dis (k), k ∈ N) as the different successive states of the process Π [n] until it reaches the absorbing state (which is the trivial partition consisting in one block) and afterward the discrete process remains constant.

Date: January 7, 2015.

As examples of Λ-coalescents, let us mention:

• the Kingman's coalescent with Λ(dx) = δ 0 (dx), see [START_REF] Kingman | The coalescent[END_REF],

• the Bolthausen-Sznitman coalescent with Λ(dx) = 1 (0,1) (x)dx, see [START_REF] Bolthausen | On Ruelle's probability cascades and an abstract cavity method[END_REF],

• the β-coalescents where Λ(dx) is (up to a multiplicative constant) the β(a, b) distribution. In the case of the β(1 + α, 1α)-coalescent, that is Λ(dx) = (x/(1x)) α dx, see [START_REF] Birkner | Alpha-stable branching and beta-coalescents[END_REF][START_REF] Berestycki | Beta-coalescents and continuous stable random trees[END_REF] for -1 < α < 0. The case α = 0 corresponds to the Bolthausen-Sznitman coalescent, while the limit case α = -1 formally corresponds to the Kingman's coalescent. For the β(1 + α, -α)-coalescent, with -1 < α < 0 see [START_REF] Foucard | Stable continuous-state branching processes with immigration and Beta-Fleming-Viot processes with immigration[END_REF].

We refer to the survey [START_REF] Berestycki | Recent progress in coalescent theory[END_REF] for further results on coalescent processes. Let α ∈ [1/2, 1). We consider a critical Galton-Watson (GW) tree T with offspring distribution characterized by its generating function for r ∈ [0, 1]:

(3)

g(r) = r + α(1 -r) 1/α .
This GW tree arises as the shape of the sub-tree of a stable Lévy tree with index γ = 1/α generated by leaves chosen in a Poissonian manner, see [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF], Theorem 3.2.1. We shall call these random trees the stable GW trees with parameter γ. We denote by P the distribution of T . If x is a node of T we denote by k x (T ) the number of offsprings of x. If k x (T ) = 0 (resp. k x (T ) > 0), then x is called a leaf (resp. an internal node) of T . We denote by L(T ) the number of leaves of the tree T . Since g ′ (0) = 0, we get that a.s. k x (T ) = 1 for all x ∈ T . We denote by P n the law of T conditioned to have exactly n leaves. Under P n , we label the leaves of T from 1 to n uniformly at random, independently of T , and then we consider the following pruning procedure which is derived from [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF], see Section 2.2. Choose an internal node x 1 (which has at least 2 children) at random with probability:

k x 1 (T ) -1 L(T ) -1 •
This internal node separates the tree into two subtrees: the fringe sub-tree T x 1 rooted at x 1 that consists of all nodes of T that have x 1 on their lineage to the root (including x 1 ), and the set T \ T x 1 which is still a tree. We set T (1) = (T \ T x 1 ) ∪ {x 1 } which is the new tree we work with. All the leaves of T (1) except x 1 are leaves of T and they keep their label. Notice that x 1 is a new leaf of T (1) and we label it by the block (i.e. the sequence) of labels of the leaves of T x 1 . We then iterate the procedure on the tree T (1) and so on until the root is chosen (see Figure [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF]). This pruning procedure defines a discrete time process Π

[n] GW = (Π [n]
GW (k), k ∈ N) taking values in the set of partitions of the n first integers, Π

[n] GW (k) being the set of labels of the leaves of the tree T (k) obtained after the k-th cut.

Main result. The process Π

[n] GW is then a coalescent process starting from the trivial partition consisting of singletons and blocks merge together as time goes by. Its law is given in the next theorem.

Theorem 1.1. We set α = 1 γ ∈ [1/2, 1). The process Π [n]
GW is distributed under P n as Π

[n] dis for the β(1 + α, 1α)-coalescent with coalescent measure: dis is discrete in time and thus characterizes the coalescent measure up to a multiplicative constant. It is possible to construct the continuoustime coalescent process Π [n] associated with the measure Λ given by Equation ( 4) from the process Π

(4) Λ(dx) = x 1 -x α dx.

[n]

GW by adding exponential times between the successive states of this process. More precisely, recall the definitions of the transitions rates λ b,k of Equation (1) and of the jump rates λ b of Equation [START_REF] Abraham | A continuum-tree-valued Markov process[END_REF]. Let (τ k ) k∈N be a sequence of independent random variables such that, conditionally given the process Π

[n] GW , the random variable τ k is exponentially distributed with parameter λ ℓ k where ℓ k is the number of blocks of the partition Π

[n] GW (k), with the convention that τ k = +∞ if ℓ k = 1. Then we set Π[n] (t) = Π [n] GW (k) if k-1 i=0 τ i ≤ t < k i=0 τ i .
As a direct consequence of Theorem 1.1 and the definition of a Λ-coalescent, we get that the processes Π [n] and Π[n] have the same distribution.

One major drawback of this construction is that we define the process for fixed n and not simultaneously for all n. However, as in [START_REF] Abraham | A construction of a β-coalescent via the pruning of binary trees[END_REF], we can construct directly the process (Π(θ), θ ≥ 0) taking values in the set of partitions of the integers using the pruning of a Lévy continuum random tree. More precisely, we consider the weighted stable Lévy tree (T , d, m T ) associated with the branching mechanism ψ(λ) = λ γ for γ ∈ (1, 2) (the case γ = 2 is studied in [START_REF] Abraham | A construction of a β-coalescent via the pruning of binary trees[END_REF] and requires a different pruning). We recall that T is a real tree and that m T corresponds to a uniform measure on the leaves of T , see [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF], [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF] and also [START_REF] Abraham | Exit times for an increasing Lévy tree-valued process[END_REF] more specifically for the space of weighted real trees. We work under the so-called normalized excursion measure N (1) under which m T is a probability measure. We consider given T the pruning defined in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF]: to each branching point x of T we can associate a "mass" ∆ x of this node, which intuitively represents the size of its progeny, and a random variable E x which is exponentially distributed with parameter ∆ x . This random variable represents the time at which the node x is cut. When we cut such a node, we remove the sub-tree above it. Let T θ denote the continuum random sub-tree obtained at time θ ≥ 0. We define a coalescent process using the usual paintbox procedure. Let (U i , i ∈ N * ) be independent random variables with distribution m T under N (1) . We define a partition of N * at time θ, Π Lévy (θ) by saying that two integers i and j belong to the same block of Π Lévy (θ) if and only if the random variables U i and U j have a leaf of T θ as a common ancestor. Intuitively this means that U i and U j belong to the same sub-tree attached above T θ . This defines a coalescent process Π Lévy = (Π Lévy (θ), θ ≥ 0). We are now interested in its discrete (in time) restriction to the n first integers. Let Π

[n] Lévy = (Π [n]
Lévy (k), k ∈ N) be the discrete process associated with Π Lévy restricted to the n first integers until it reaches the absorbing state (which is the trivial partition consisting in one block) and which afterward remains constant.

By construction, and thanks to Theorem 3.2.1 in [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF], we can deduce that under N (1) , the discrete coalescent process Π

[n]

Lévy is distributed as Π

[n] GW under P n . In fact, we have the following stronger result.

Theorem 1.3. We set α = 1 γ ∈ (1/2, 1). Under N (1) , the processes (Π

[n]
Lévy , n ∈ N * ) associated with the Lévy tree with branching mechanism ψ(λ) = λ γ are distributed as (Π

[n]
dis , n ∈ N * ) associated with the Lévy measure Λ(dx) = (x/1x) α dx.

Remark 1.4. Although the process Π Lévy is a continuous-time process like Π GW , it is not a coalescent process under N (1) as for instance the time of the first coalescence event in Π

[n] Lévy is not exponentially distributed, see Corollary 4.5.

We conjecture that there exists a random time-change (R(t), t ≥ 0) such that the process (Π Lévy (R(t)), t ≥ 0) is indeed under N (1) a β(1 + α, 1α)-coalescent, but we have no guess on what this time change could be.

Remark 1.5. Let us remark that the β(1 + α, 1α)-coalescent we obtain is also a β(2a, a)coalescent (with a = 1α) as in [START_REF] Berestycki | Beta-coalescents and continuous stable random trees[END_REF] but with a different range for a. The difference between the two cases is that in [START_REF] Berestycki | Beta-coalescents and continuous stable random trees[END_REF] α ∈ (-1, 0) and the coalescent process comes down from infinity (i.e. for every positive time θ, the partition Π(θ) contains only a finite number of blocks) whereas in our case α ∈ (1/2, 1) the process always contains an infinite number of singletons (also called "dust").

Remark 1.6. Let us remark that the pruning procedure described above is the same as in [START_REF] Miermont | Self-similar fragmentations derived from the stable tree. II. Splitting at nodes[END_REF] used to construct the Miermont's self-similar fragmentation process (see also [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF]). However, the time reversal of the process Π Lévy is not Miermont's fragmentation as once a sub-tree is cut and discarded, it is no more considered in our construction whereas it undergoes some others fragmentations in Miermont's construction. There are still some strong connections. For instance, the tree T θ is linked with a tagged fragment in the fragmentation, see [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF] Theorem 1.5 and Proposition 1.7 for the distribution of the tree T θ and for the distribution of a tagged fragment in Miermont's fragmentation. 1.3. Number of cuts needed to isolate the root in a stable GW tree. Using the above link between Galton-Watson trees and β-coalescents, known results in one field translate immediately in the other field giving sometimes new results. In that direction, we first focus on how known asymptotics on the number of coalescence events yield new results on the number of cuts needed to isolate the root in a stable GW tree with n leaves.

The original problem of cutting randomly a rooted tree arises first in Meir and Moon [START_REF] Meir | Cutting down random trees[END_REF]. Given a rooted tree T n with n edges, select an edge uniformly at random (notice that this is not exactly our pruning procedure) and delete the subtree not containing the root attached to this edge. On the remaining tree, iterate this procedure until only the edge attached to the root is left. We denote by Zn the number of edge-removals needed to isolate the root. The problem is then to study asymptotics of this random number Zn , depending on the law of the initial tree T n .

In the original paper [START_REF] Meir | Cutting down random trees[END_REF], Meir and Moon considered Cayley trees and obtained asymptotics for the first two moments of X n . Limits in distribution were then obtained, see for instance Panholzer [START_REF] Panholzer | Cutting down very simple trees[END_REF] for some simply generated trees, Drmota, Iksanov, Möhle and Roesler [START_REF] Drmota | A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree[END_REF] for random recursive trees, Holmgren [START_REF] Holmgren | Random records and cuttings in binary search trees[END_REF] for binary search trees, Bertoin [START_REF] Bertoin | Fires on trees[END_REF] for Cayley trees. In [START_REF] Janson | Random cutting and records in deterministic and random trees[END_REF], Janson focuses on conditioned Galton-Watson trees associated with critical offspring distributions with finite variance and proves that

Zn / √ n (d) -----→ n→+∞ Z,
where the random variable Z has Rayleigh distribution with density x e -x 2 /2 1 {x>0} , and can be explicitly constructed using a pruning procedure on the Brownian continuum random tree (which corresponds to the cases γ = 2 in our setting), see [START_REF] Abraham | Record process on the continuum random tree[END_REF]. In particular Z is distributed as the height of a random leaf of the Brownian continuum random tree. See also [START_REF] Addario-Berry | Cutting down trees with a Markov chainsaw[END_REF][START_REF] Bertoin | The cut-tree of large Galton-Watson trees and the Brownian CRT[END_REF] for further work on cutting randomly rooted trees. Notice that the reproduction law for stable GW tree has an infinite variance for α ∈ (1/2, 1), and the uniform pruning does not seem to be adapted to isolate the root. For this reason, we consider the pruning procedure developed in Section 1.1 to tackle the infinite variance case. So, let Z n be the number of cuts, using this procedure, needed to isolate the root of a stable GW tree:

Z n = inf{k; Π [n]
GW (k) = {{1, . . . , n}}}. Notice that for r-ary trees, since all the internal nodes have the same degree the cutting procedure given in Section 1.1, corresponds to choose an internal node uniformly.

We immediately deduce from asymptotics of the number of coalescence events in βcoalescent (see Corollary 1 [START_REF] Haas | Self-similar scaling limits of non-increasing Markov chains[END_REF], see also [START_REF] Gnedin | On asympotics of the beta-coalescents[END_REF], Table 1 for a summary of all the results concerning β-coalescents), the following result which extends part of the result in [START_REF] Janson | Random cutting and records in deterministic and random trees[END_REF] to GW tree with infinite variance of the reproduction law.

Corollary 1.7. Let α = 1/γ ∈ [1/2, 1). We have the following convergence in distribution:

n α-1 Z n (d) -----→ n→+∞ Z,
with the distribution of Z characterized by, for n ∈ N * :

E [Z n ] = α n Γ(n + 1)Γ(1 -α) Γ((n + 1)(1 -α)) •
Let us insist on the fact that this corollary does not need any proof as this is just a translation of known results on β-coalescents using our links with GW trees, only the moment computation needs some explanations and is done in Section 5,

The distribution of Z corresponds to the expected limit distribution in the Conjecture that is stated at the end of the introduction in [START_REF] Abraham | The forest associated with the record process on a Lévy tree[END_REF] for the number of cuts needed to isolate the root in general GW trees. (Notice that in the conjecture, one choose an internal node x ∈ T with probability proportional to k x (T ) whereas in Section 1.1 one choose an internal node x ∈ T with probability proportional to k x (T ) -1.) In particular, Z is distributed as the height of a random leaf of the normalized Lévy tree with branching mechanism ψ(λ) = λ γ . 1.4. Number of blocks in the last coalescence event. On the other hand, we can use results on GW trees conditioned to have an infinite number of leaves (which is very close to Kesten's result on GW tree conditionally on the non extinction, see [START_REF] Curien | Random non-crossing plane configurations: a conditioned Galton-Watson tree approach[END_REF] Theorem 3.1 or [START_REF] Abraham | Local limits of conditioned Galton-Watson trees: the infinite spine case[END_REF] Proposition 4.6) to get asymptotics on the number B n of blocks involved is the last coalescence event of Π [n] .

The proof of the following Proposition is given in Section 6.

Proposition 1.8. Let α = 1/γ ∈ [1/2, 1
). We have the following convergence in distribution:

B n (d) -----→ n→+∞ B,
with the distribution of B given by its generating function ϕ α (r) = E r B , with for r ∈ [0, 1]:

(5)

ϕ α (r) = (1 -α)r 1 0 dx 1 -(1 -x) α 1 (1 -rx) α -1 .
See also [START_REF] Abraham | A construction of a β-coalescent via the pruning of binary trees[END_REF] for more results in this direction when α = 1/2 including the number of singletons involved in the last coalescence event as well as a closed form for ϕ 1/2 . Remark 1.9. After we first posted this paper on arXiv, Hénard proved in [START_REF] Henard | The fixation line[END_REF] Theorem 3.5 that Equation ( 5) remains valid for all β(1 + α, 1α)-coalescents with α ∈ (-1, 1) (taking the limit when α = 0).

For α = 0, the β(1 + α, 1α)-coalescent corresponds to the Bolthausen-Sznitman coalescent, and thus ϕ 0 is the generating function of the asymptotic number of blocks of the last coalescence event in the Bolthausen-Sznitman coalescent whose distribution is given in Theorem 3.1 and Proposition 3.2 of [START_REF] Goldschmidt | Random recursive trees and the Bolthausen-Sznitman coalescent[END_REF].

As α goes down to -1, we recover the Kingman's coalescent as a limit. We also get ϕ -1 (r) = r 2 and notice that ϕ -1 is trivially the generating function of the number of blocks of the last (in fact all) coalescence event in the Kingman's coalescent, as all the coalescence events are binary.

1.5. Organization of the paper. Section 2 gives a representation of the pruning at node procedure for GW tree in continuous time motivated by [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF]. This procedure corresponds in fact to the one presented in Introduction, Section 1.1. Section 3 is devoted to the proof of Theorem 1.1. Section 4 devoted to the proof of Theorem 1.3 is more technical as it relies on continuum random Lévy trees and the pruning of such trees as developed in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF]. Eventually Sections 5 and 6 are devoted to the proofs of Propositions 1.7 and 1.8. A u = {v ∈ U ; there exists w ∈ U such that u = vw}.

Pruning at node of discrete GW trees

A discrete tree t is a subset of U that satisfies:

• ∅ ∈ t, • If u ∈ t, then A u ⊂ t.
• For every u ∈ t, there exists a non-negative integer k u (t) such that, for all positive integer i, ui ∈ t iff 1 ≤ i ≤ k u (t). The integer k u (t) represents the number of offsprings of the node u in the tree t. We define L(t) the set of leaves of t and N (t) the set of internal nodes of t by:

L(t) = {u ∈ t, k u (t) = 0} and N (t) = t \ L(t).
Let L(t) = Card (L(t)) be the number of leaves of the tree t, and notice that:

(7) L(t) -1 = u∈N (t) (k u (t) -1).
We denote by T the set of discrete trees and by T n = {t ∈ T; L(t) = n} the set of discrete trees with n leaves.

2.2.

A discrete tree-valued process. We consider the pruning procedure developed in [START_REF] Abraham | Pruning Galton-Watson trees and tree-valued Markov processes[END_REF]. Let t ∈ T. Under some probability measure P t , we consider a family of marks (ξ u , u ∈ U ) of independent non-negative real random variables (possibly infinite) such that:

• P t -a.s. ξ u = +∞ if u ∈ t or if u ∈ t and k u (t) ∈ {0, 1}, • P t (ξ u ≥ θ) = (1 + θ) 1-ku(t) if u ∈ t and k u (t) ≥ 2.
At time θ, we define the pruned tree P θ (t) as the sub-tree given by:

P θ (t) = {u ∈ t; ξ v > θ for all v ∈ A u , v = u}.
In particular, we always have ∅ ∈ P θ (t).

For u ∈ N (t), let D u be the event that u is marked first, that is:

D u = {ξ u = min v∈N (t) ξ v }.
Lemma 2.1. We suppose that L(t) = 1. Let u ∈ N (t). We have:

P t (D u ) = k u (t) -1 L(t) -1 •
This lemma implies that the cutting procedure given in Section 1.1, corresponds to the successive states of the process (P θ (t), θ ≥ 0).

Proof. We have, using [START_REF] Abraham | Pruning Galton-Watson trees and tree-valued Markov processes[END_REF] for the last equality:

P t (D u ) = P t (ξ u ≤ ξ v ∀v = u, v ∈ N (T )) = E t (1 + ξ u ) -v =u,v∈N (t) (kv(t)-1) = (k u (t) -1) [0,+∞) (1 + θ) -v∈N (t) (kv(t)-1)-1 dθ = k u (t) -1 v∈N (t) (k v (t) -1) = k u (t) -1 L(t) -1 • 2.3. Construction of the partition-valued process Π [n] GW . Let α ∈ [1/2, 1
). Recall that the function g defined by (3) is the generating function of a probability measure ν g on N. We denote by G g (dT ) the distribution on T of the critical GW tree with offspring distribution ν g . We will denote by P the probability measure on T × [0, +∞] U : P(dT, dξ) = G g (dT )P T (dξ).

Under P, the random tree T is a GW tree whose offspring distribution ν g has generating function g given by (3). According to Propositions 2.1 and 3.2 in [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF], (P θ (T ), θ ≥ 0) is a Markov process and P θ (T ) is a GW tree whose reproduction law has generating function g θ , with:

g θ (r) = 1 + (1 + θ) g r 1 + θ -g 1 1 + θ .
Notice that:

(8) g θ (r) = r + α (1 -r + θ) 1/α -θ 1/α (1 + θ) (1/α)-1 •
For every positive integer n, we set:

P n (•) = P(• L(T ) = n).
Under P n , the distribution of the tree T is given by the following formula (see [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF], Theorem 3.3.3, or [START_REF] Marchal | A note on the fragmentation of a stable tree[END_REF]), for t ∈ T n :

(9)

P n (T = t) = n!   v∈N (t) p kv(t) k v (t)!   α n-1 Γ(1 -α) Γ(n -α)
where p 1 = 0 and, for k ≥ 2,

p k = |(1 -γ)(2 -γ) • • • (k -γ)|.
Let n ∈ N * . Let T be a random tree distributed as P n . Conditionally on T , we define a uniform random labeling U 1 , . . . , U n of the leaves of T , independently of the variables (ξ u , u ∈ T ). Recall the set of ancestors defined in [START_REF] Abraham | Local limits of conditioned Galton-Watson trees: the infinite spine case[END_REF] and the pruning procedure P θ introduced in Section 2.2. We define the equivalence relation R

[n]

θ on {1, 2, . . . , n} by: iR

[n] θ j if A U i A U j L(P θ (T )
) is non empty, that is U i and U j have a leaf of P θ (T ) as common ancestor. Then, for every θ ≥ 0, let Π[n] GW (θ) be the equivalence classes of the equivalence relation R

[n] θ of the n first integers. Let Π [n] GW = (Π [n] GW (k), k ∈ N) be the discrete process associated with Π[n] GW = ( Π[n] GW (
θ), θ ≥ 0) until it reaches the absorbing state (which is the trivial partition consisting in one block) and afterward the discrete process remains constant.

We end this section with an elementary lemma which will be used in the proof of Theorem 1.1.

Lemma 2.2. We have for n ≥ 2:

(10) E n [k ∅ (T ) -1] = 1 -α α Γ (1 -α) Γ (α) Γ (n -1 + α) Γ (n -α) •
Proof. We consider the generating function of (k ∅ (T ), L(T )) under P, that is H(s, t) = E s k ∅ (T ) t L(T ) . Using the branching property of GW trees, we have:

(11) H(s, t) = E s k ∅ (T ) E[t L(T ) ] k ∅ (T ) 1 {k ∅ (T ) =0} + tP(k ∅ (T ) = 0).
Notice that g(s) = E s k ∅ (T ) = H(s, 1). We set h(t) = H(1, t) = E t L(T ) the generating function of L(T ). So that (11) becomes:

(12) H(s, t) = g(s h(t))g(0)(1t).

Taking s = 1 in (12), we get:

(13) g(h(t)) -h(t) = g(0)(1 -t).
Using expression (3), we get:

h(t) = 1 -(1 -t) α and H(s, t) = s h(t) + α(1 -s h(t)) 1/α -α(1 -t).
We deduce that:

E k ∅ (T )t L(T ) = ∂H ∂s (1, t) = h(t) -h(t)(1 -h(t)) (1/α)-1 = E t L(T ) -[1 -(1 -t) α ] (1 -t) 1-α = E t L(T ) -(1 -t) 1-α + 1 -t.
This gives:

E (k ∅ (T ) -1)t L(T ) = -(1 -t) 1-α + 1 -t.
For n ≥ 2, we get:

E (k ∅ (T ) -1)1 {L(T )=n} = 1 n! d n dt n E (k ∅ (T ) -1)t L(T ) | t=0 = 1 n! (1 -α) n-2 k=0 (α + k) = 1 n! (1 -α) Γ (n -1 + α) Γ (α) •
We also get for n ≥ 2:

P(L(T ) = n) = 1 n! h (n) (0) = 1 n! α n-1 k=1 (k -α) = 1 n! α Γ (n -α) Γ (1 -α) •
We deduce that:

E n [k ∅ (T ) -1] = E (k ∅ (T ) -1)1 {L(T )=n} P(L(T ) = n) = 1 -α α Γ(1 -α) Γ(α) Γ(n -1 + α) Γ(n -α) • 3. Proof of Theorem 1.1 Let α ∈ [1/2, 1
) and Λ given by (4). Notice that the probability that the first coalescence event for Π

[n] dis corresponds to the collision of k given blocks is λ n,k /λ n , with λ n,k and λ n given respectively by (1) and (2).

Theorem 1.1 is a direct consequence of Lemma 3.3 which states that the probability that the first coalescence event for Π

[n] GW corresponds to the collision of k given blocks is λ n,k /λ n , and of Lemma 3.4, which states that after the first coalescence event, the law of the pruned tree under P n conditionally given that it has k leaves is exactly P k .

The proof of Lemme 3.3 (resp. 3.4) is given in Section 3.1 (resp. 3.2).

3.1.

Computation of the coalescence rates. We first give an intermediate lemma. For α ∈ (0, 1) and λ > α -1, we set:

(14) φ 1+α,1-α (λ) = 1 0 1 -(1 -x) λ x α-2 (1 -x) -α dx.
Lemma 3.1. For α ∈ (0, 1) and λ > α -1, we have:

(15) φ 1+α,1-α (λ) = λ Γ(α)Γ(λ + 1 -α) (1 -α)Γ(λ + 1) •
Notice that for λ > 0, [START_REF] Birkner | Alpha-stable branching and beta-coalescents[END_REF] reduces to:

(16) φ 1+α,1-α (λ) = Γ(α)Γ(λ + 1 -α) (1 -α)Γ(λ) •
Proof. We set:

I = 1 0 (1 -u) -α -1 u α-2 du.
Notice that I is finite and φ 1+α,1-α (α) = I. For λ > α, using an integration by part, we have:

φ 1+α,1-α (λ) = 1 0 1 -(1 -x) λ x α-2 (1 -x) -α dx = 1 0 (1 -x) -α -1 x α-2 dx + 1 0 1 -(1 -x) λ-α x α-2 dx = I - 1 1 -α + λ -α 1 -α 1 0 (1 -x) λ-α-1 x α-1 dx = I - 1 1 -α + Γ(α)Γ(λ + 1 -α) (1 -α)Γ(λ) •
We now compute I. For λ = 1, we also have:

φ 1+α,1-α (1) = 1 0 x α-1 (1 -x) -α dx = Γ(α)Γ(1 -α).
We deduce that:

I - 1 1 -α + Γ(α)Γ(2 -α) (1 -α)Γ(1) = φ 1+α,1-α (1) = Γ(α)Γ(1 -α).
This readily implies that I = 1/(1α) and thus [START_REF] Birkner | Alpha-stable branching and beta-coalescents[END_REF] holds for λ ≥ α. Then uses that the right-hand sides of ( 14) and ( 15) are analytic for λ > α -1 to get that (15) also holds for λ > α -1.

Recall that λ n,k and λ n are given respectively by ( 1) and ( 2), for Λ given by (4).

Lemma 3.2. Let α ∈ [1/2, 1). We have for 2 ≤ k ≤ n:

(17) λ n,k λ n = 1 -α Γ(α + 1) Γ(k + α -1)Γ(n -k -α + 1) Γ(n -α) 1 n -1 • Proof. We have λ n,k = 1 0 u k-2 (1 -u) n-k Λ(du) = 1 0 u k-2+α (1 -u) n-k-α du = β(k + α -1, n -k -α + 1) = Γ(k + α -1)Γ(n -k -α + 1) Γ(n) ,
and

λ n = n k=2 n k λ n,k = 1 0 (1 -(1 -u) n -nu(1 -u) n-1 )u -2 Λ(du).
Then using notations ( 14) and ( 16), we deduce that:

λ n = φ 1+α,1-α (n) -n 1 0 u α-1 (1 -u) n-1-α du = Γ(α)Γ(n + 1 -α) (1 -α)Γ(n) -n Γ(α)Γ(n -α) Γ(n) = n -α 1 -α -n Γ(α)Γ(n -α) Γ(n) = (n -1) α 1 -α Γ(α)Γ(n -α) Γ(n) •
The expression obtained for λ n,k then gives the result.

If t 1 and t 2 are two discrete trees and u ∈ L(t 1 ) is a leaf of t 1 , we shall denote by t 1 ⊛ u t 2 the tree obtained by grafting the tree t 2 on the leaf u of t 1 , that is:

(18) t 1 ⊛ u t 2 = t 1 ∪ {uv, v ∈ t 2 }. Lemma 3.3. Let α ∈ [1/2, 1
). The probability under P n that the first coalescence event in Π

[n]

GW is the coalescence of k given integers into one block is λ n,k /λ n .

Proof. Let A k be the event that the first coalescence event corresponds to the k first integers merging together. By exchangeability, the lemma is proved as soon as we check that

P n (A k ) = λ n,k /λ n .
The event A k is realized, if and only if:

• The initial tree T is of the form t 1 ⊛ u t 2 for some t 2 ∈ T k and t 1 ∈ T n-k+1 and u ∈ L(t 1 ). • The leaves of t 2 are labeled from 1 to k (and therefore, the leaves of t 1 except u are labeled from k + 1 to n). This occurs with probability k!(n-k)! n! . • The first chosen node of t 1 ⊛ u t 2 is u. This occurs according to Lemma 2.1 with probability k ∅ (t 2 )-1 n-1 .

Thus, using [START_REF] Abraham | Exit times for an increasing Lévy tree-valued process[END_REF] for the probability of having a given tree, we have:

P n (A k ) = t 1 ∈T n-k+1 t 2 ∈T k u∈L(t 1 ) P n (T = t 1 ⊛ u t 2 ) k!(n -k)! n! k ∅ (t 2 ) -1 n -1 = t 1 ∈T n-k+1 t 2 ∈T k u∈L(t 1 ) n!   v∈N (t 1 ⊛ut 2 ) p kv(t 1 ⊛ut 2 ) k v (t 1 ⊛ u t 2 )!   α n-1 Γ(1 -α) Γ(n -α) k!(n -k)! n! k ∅ (t 2 ) -1 n -1 = (n -k + 1) t 1 ∈T n-k+1 t 2 ∈T k n! k!(n -k + 1)! P n-k+1 (T = t 1 )P k (T = t 2 ) α n-1 Γ(1 -α) Γ(n -α) Γ(n -k -α + 1) α n-k Γ(1 -α) Γ(k -α) α k-1 Γ(1 -α) k!(n -k)! n! k ∅ (t 2 ) -1 n -1 = Γ(n -k -α + 1)Γ(k -α) Γ(n -α)Γ(1 -α) 1 n -1 E k [k ∅ (T ) -1] .
We then use Lemma 2.2 and Lemma 3.2 to conclude.

3.2.

Law of the tree after the first coalescence event. Let S be the time of the first coalescence event and recall that P S (T ) denote the pruned tree at the first coalescence event.

Lemma 3.4. Let t ∈ T k . We have:

P n (P S (T ) = t L(P S (T )) = k) = P k (T = t).

Proof. Let t ∈ T k . We obtain t just after the first coalescence event if T is of the form t ⊛ u s for some s ∈ T n-k+1 , u ∈ L(t) and u is the first chosen internal node. This gives:

P n (P S (T ) = t) = u∈L(t)
s∈T n-k+1

P n (T = t ⊛ u s) k ∅ (s) -1 n -1 = k s∈T n-k+1 n!   v∈N (t) p kv(t) k v (t)! v∈N (s) p kv(s) k v (s)!   α n-1 Γ(1 -α) Γ(n -α) k ∅ (s) -1 n -1 = k s∈T n-k+1 n! k!(n -k + 1)! P k (T = t)P n-k+1 (T = s) α n-1 Γ(1 -α) Γ(n -α) Γ(k -α) α k-1 Γ(1 -α) Γ(n -k + 1 -α) α n-k Γ(1 -α) k ∅ (s) -1 n -1 = n! (k -1)!(n -k + 1)! Γ(n -k + 1 -α)Γ(k -α) Γ(n -α)Γ(1 -α) 1 n -1 E n-k+1 [k ∅ (T ) -1]P k (T = t).
As the term in front of P k (T = t) does not depend on t, it has to be equal to P n (L(P S (T )) = k) and therefore (19) holds.

Pruning of rooted real trees and proof of Theorem 1.3

The aim of this section is to use the pruning procedure for Lévy trees developed in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF] to give a consistent representation of the family of coalescent processes ( Π[n] GW , n ∈ N * ), see Corollary 4.4 and thus deduce Theorem 1.3. 4.1. The CRT framework.

4.1.1. Real trees. Real trees have been introduced first in the field of geometric group theory (see for instance [START_REF] Dress | T-theory: an overview[END_REF]) and then used later for defining continuum random trees (the framework first appeared in [START_REF] Evans | Rayleigh processes, real trees and root growth with re-grafting[END_REF]). A real tree is a metric space (T , d) satisfying the following two properties for every x, y ∈ T :

• (unique geodesic) There is a unique isometric map f x,y from [0, d(x, y)] into T such that f x,y (0) = x and f x,y (d(x, y)) = y.

• (no loop) If ϕ is a continuous injective map from [0, 1] into T such that ϕ(0) = x and ϕ(1) = y, then ϕ([0, 1]) = f x,y ([0, d(x, y)]).
A rooted real tree is a real tree with a distinguished vertex denoted ∅ and called the root.

For every x, y ∈ T , we denote by [[x, y]] the range of the map f x,y (i.e. the only path in the tree that links x to y) and we set

[[x, y[[= [[x, y]] \ {y}.
If T is a rooted real tree, for x ∈ T , we define the degree of x, denoted by n x , as the number of connected components of T \ {x}. The leaves of T is L(T ) = {x ∈ T \ {∅}; n x = 1}. If n x ≥ 3, we say that x is a branching point of T . We denote by B br (T ) the set of branching points of T . The height of T is H max (T ) = sup{d(∅, x); x ∈ T }. Let (x i , i ∈ I) be a family of elements of T , we define their most recent common ancestor denoted by MRCA(x i , i ∈ I)

as the element x of T such that [[∅, x]] = i∈I [[∅, x i ]].
A weighted rooted real tree (T , d, m) is a rooted real tree (T , d) endowed with a σ-finite measure m called the mass measure. 4.1.2. Stable Lévy tree. Set ψ(λ) = λ γ with γ ∈ (1, 2). We refer to [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF] and [START_REF] Abraham | Exit times for an increasing Lévy tree-valued process[END_REF] for the existence of a measure N[dT ] on the set of weighted locally compact rooted real tree such that T is under N[dT ] a Lévy tree associated with the branching mechanism ψ. For the Lévy tree (T , d, m), N[dT ] -a.e., the mass measure has support L(T ) and has no atom. Furthermore, N[dT ]-a.e., all the branching points of the tree are of infinite degree. Following [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF], there exists a local time process (ℓ a , a ≥ 0) with values on finite measures on T , which is càdlàg for the weak topology on finite measures on T and such that N ψ [dT ]-a.e.:

m(dx) = ∞ 0 ℓ a (dx) da, ℓ 0 = 0, inf{a > 0; ℓ a = 0} = sup{a ≥ 0; ℓ a = 0} = H max (T )
and for every fixed a ≥ 0, N ψ [dT ]-a.e. the measure ℓ a is supported on {x ∈ T ; d(∅, x) = a} and the real valued process ( ℓ a , 1 , a ≥ 0) is distributed as a continuous state branching process (CSBP) with branching mechanism ψ under its canonical measure. In particular, as the total size of a critical CSBP is finite, we get that N-a.e. σ = m(T ) is finite.

The set {d(∅, x), x ∈ Br(T )} coincides N ψ -a.e. with the set of discontinuity times of the mapping a → ℓ a . Moreover, N ψ -a.e., for every such discontinuity time b, there is a unique x ∈ B br (T ) such that d(∅, x) = b and ∆ x > 0, such that:

ℓ b = ℓ b-+ ∆ x δ x ,
where ∆ x > 0 is called the mass of the node x. Intuitively ∆ x represents the size of the progeny of x.

The scaling property of the stable Lévy tree implies that there exists a well defined probability measure N (1) defined as the measure N conditioned on {σ = 1}. The probability measure is also referred as the normalized excursion measure for Lévy trees. 4.2. The partition-valued process. Set ψ(λ) = λ γ with γ ∈ (1, 2). 4.2.1. Pruning of the stable Lévy tree. We consider the pruning procedure introduced in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF] (this procedure is defined when there is no Brownian part in the Lévy process with index given by the branching mechanism ψ). Under N or N (1) , conditionally given T , we consider a family (E x , x ∈ B br (T )) of independent real random variables such that the random variable E x is exponentially distributed with parameter ∆ x . This random variable represents the time at which the branching point x is marked. For every θ > 0, we set

T θ = {x ∈ T , ∀y ∈ [[∅, x[[, E y ≥ θ}.
The set T θ is still a real tree which represents the tree T pruned at time θ: we cut T at the points that are marked before time θ and keep the connected component of the tree that contains the root. We set T 0 = T . By [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF], Theorem 1.5, the tree T θ is distributed under N as a Lévy tree with branching mechanism ψ θ defined by:

ψ θ (λ) = ψ(λ + θ) -ψ(θ).
Moreover, by [START_REF] Abraham | A continuum-tree-valued Markov process[END_REF], the process (T θ , θ ≥ 0) is under N a Markov process. 4.2.2. Definition of the partition-valued process. Under N or N (1) , conditionally on T , let (F i , i ∈ N * ) be independent random variables on T distributed according to the probability mass measure m/m(T ), and independent of the marks (E x , x ∈ B br (T )). Notice that N-a.e. or N (1) -a.s. (F i , i ∈ N * ) are leaves of T . For θ ≥ 0, we define the equivalence relation R Lévy θ on N * by: iR Lévy

θ j if [[∅, F i ]] [[∅, F j ]] L(T θ
) is non empty, that is F i and F j have a leaf of T θ as common ancestor. This is very close to the definition of the equivalence relation R 4.3.1. Skeleton of finite real tree. Let t be a real tree with finite height and a finite number of leaves, such that the leaves (f i , i ∈ I( t)) are indexed by a totally ordered set I( t). We define the skeleton t of the tree t as the discrete tree (belonging to T) where we forget the edge lengths. As the trees in T are ordered, we must be a bit more rigorous for the definition of t.

The skeleton t of the real tree with ordered leaves t, (f i , i ∈ I( t)) is defined recursively as follows. We define k ∅ ( t) as the degree of MRCA(f i , i ∈ I( t)) the ancestor of all the leaves of t. If k ∅ ( t) = 0, then t is reduced to ∅. In this case t has one leaf, let f be its label, and the discrete tree t has thus one leaf to which we give the label f . If k ∅ ( t) > 0, then we consider the k ∅ ( t) connected components of t \ {MRCA(f i , i ∈ I( t))} that do not contain the root and label them from 1 to k ∅ ( t) according to the lowest label of the leaves of t which belongs to them. This gives an ordered family ( tk , k ∈ {1, . . . , k ∅ ( t)}) of real trees, and let MRCA(f i , i ∈ I( t))}) be the root of each one. For k ∈ {1, . . . , k ∅ ( t)}, let I( tk ) = {i ∈ I( t); f i ∈ tk ) be the labels of the leaves of tk and the discrete tree tk is the skeleton of tk , (f i , i ∈ I( tk )) .

Notice that t is finite, k u ( t) = 1 for all u ∈ t, and t and t have the same number of leaves. In the previous construction to a leaf f i of t with label i corresponds a unique leaf e i of t with label i. For u ∈ t, we define tu the sub-tree of t attached to the node u i.e. [START_REF] Duquesne | A limit theorem for the contour process of conditioned Galton-Watson trees[END_REF] tu = {w ∈ U , uw ∈ t}, and let I u = {i; e i ∈ tu }. Define tu as s u = t\ i ∈Iu [[∅, f i ]] to which we add the root ∅ u = s u \s u , and I( tu ) = {i; e i ∈ tu }. Notice that by construction tu is the skeleton of tu , (f i ; i ∈ I( tu )) . We say that u ∈ t are the individuals of t, and define their lifetime as the length h u of the geodesic

B(u) = [[∅ u , MRCA(f i , i ∈ I( tu ))]]. We say the corresponding node in t of u ∈ t is C(u) = MRCA(f i , i ∈ I( tu )).
Notice it is easy to reconstruct t from t and the family of lifetime (h u , u ∈ t).

4.3.2.

Coalescence of Lévy tree and GW tree. Let M be, under N or N (1) conditionally on T , a Poisson random variable with finite mean σ = m(T ). We shall work on {M ≥ 1}. On {M ≥ 1}, let T0 be the real sub-tree of T generated by the root and

(F i , 1 ≤ i ≤ M ): T0 = 1≤i≤M [[∅, F i ]].
Since m has support L(T ) and has no atom, we deduce that (F i , 1 ≤ i ≤ M ) are distinct and are the leaves of T0 . We denote by T0 the skeleton of T0 with the labeled leaves (F i , 1 ≤ i ≤ M ). According to [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF], Theorem 3.2.1, the tree T0 is distributed under N[ • M ≥ 1] as a continuous GW tree (i.e. a GW tree with edge-lengths) such that • The discrete tree T0 is a GW tree with offspring distribution characterized by its generating function g defined by (3) with α = 1/γ. • Lifetimes of individuals (h u , u ∈ T0 ) are independent random variables with exponential distribution with parameter γ. We must first prove the following lemma which will be a key point in the sequel. Its proof relies on the scaling property of the Lévy tree. Proof. For a tree T and points x 1 , . . . , x n of T , let us denote by T (T , x 1 , . . . , x n ) the tree spanned by the points (x i ) and the root of the tree and T (T , x 1 , . . . , x n ) the associated discrete tree so that under N[ • M = n] or N (1)

[ • M = n], we have T0 = T (T , F 1 , . . . , F n ).
Then, for every bounded measurable function φ, we have

N φ T (T , F 1 , . . . , F n ) 1 {M =n} = N φ T (T , F 1 , . . . , F n ) σ n n! e -σ .
Let ν be the distribution of σ under N i.e. the only measure ν such that for every λ > 0, +∞ 0

(1e -λu )ν(du) = λ α .

Then we have

N φ T (T , F 1 , . . . , F n ) 1 {M =n} = +∞ 0 N (u) φ T (T , F 1 , . . . , F n ) u n n! e -u ν(du).
Using the scaling property of the stable Lévy tree (see [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF] Section 3.3), we have that the law of the tree T under N (u) is the same as the law of u 1-α T under N (1) where the notation λT means that we multiply the distance that defines T by the factor λ (i.e. we scale all the edge lengths by λ). Moreover, as we only look at discrete trees, this factor does not modify the tree T0 . Therefore, we get:

N φ T (T , F 1 , . . . , F n ) 1 {M =n} = +∞ 0 N (1) φ T (T , F 1 , . . . , F n ) u n n! e -u ν(du) = N (1) φ T (T , F 1 , . . . , F n ) N[M = n].
We deduce:

N[φ( T0 ) M = n] = N φ T (T , F 1 , . . . , F n ) M = n = N (1) φ T (T , F 1 , . . . , F n ) = N (1) [φ( T0 ) M = n]
since T and M are independent under N (1) .

We now consider the marks that define the pruned tree T θ and we define on the event {M ≥ 1} the tree Tθ as the tree T0 pruned on the same marks, in other words, we set Tθ = T0 ∩ T θ .

Let Π[n]

Lévy be the restriction of Π Lévy to the n first integers. By construction, if C θ is an element of Π[n] Lévy (θ), then there exists a leaf x of Tθ such that x belongs to the sub-tree i∈C θ [[∅, F i ]], and x is the only leaf of Tθ with this property. We set C θ for the label of x, and we consider the order of the elements of Π[n] Lévy given by the order of their smallest integer. We set I θ = I( Tθ ) for the labels of the leaves of Tθ and (F θ i , i ∈ I θ ) for the leaves of Tθ . We denote by Tθ the skeleton of Tθ with the labeled leaves (F θ i , i ∈ I θ ). According to [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF], Proposition 4.1, the tree Tθ is distributed under N[ • M ≥ 1] as a continuous GW tree such that

• Tθ is a GW tree with offspring distribution characterized by its generating function g θ given in [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF] with α = 1/γ. • The lifetimes of individuals (h u , u ∈ Tθ ) are independent random variable with exponential distribution with parameter ψ ′ θ (1) = γ(1 + θ) γ-1 . The following Lemma is a consequence of Theorem 6.1 of [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF].

Lemma 4.2. The process ( Tθ , θ ≥ 0) is distributed under N[ • M ≥ 1] as the process (P θ (T ), θ ≥ 0) under P.

Proof. Let θ > 0. Theorem 6.1 of [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF] describes how Tθ is obtained from T0 :

• A branching point x of T0 with k x = k x ( T0 ) children is marked at time τ x with distribution given by:

N[τ x ≥ θ T0 ] = - +∞ θ ψ (kx+1) (1 + z) ψ (kx) (1) dz = ψ (kx) (1 + θ) ψ (kx) (1) = 1 1 + θ kx-γ .
• A branch B of length h is marked at time τ B with distribution given by:

N[τ B ≥ θ T0 ] = exp -h θ 0 ψ ′′ (1 + z)dz = e -ψ ′ (1+θ)-ψ ′ (1) h .
Then the tree T0 is cut according to the marks present at time θ and the tree Tθ is the connected component that contains the root. Therefore, the tree Tθ is obtained from the tree T0 by a pruning at node. A node u ∈ T0 is marked if the corresponding node C(u) ∈ T0 is marked at time θ in the previous procedure OR the branch B(u) with length h u is marked. So the node u of T0 is marked at time ζ u = τ C(u) ∧ τ B(u) and using that the edge lengths of T0 are independent and exponentially distributed with parameter γ = ψ ′ (1), we have with

k u = k u ( T0 ): N[ζ u ≥ θ T0 ] = N[τ C(u) ≥ θ T0 ] N[τ B(u) ≥ θ T0 ] = 1 1 + θ ku-γ +∞ 0 dh γ e -γh e -ψ ′ (1+θ)-γ h = 1 1 + θ ku-γ 1 1 + θ γ-1 = 1 1 + θ ku-1

•

Since the cutting time τ C(u) and τ B(u) are independent for all internal nodes u, we recover the discrete pruning procedure that defines the process (P θ (T ), θ ≥ 0) under P. To conclude notice that T0 and T are GW tree with offspring distribution characterized by its generating function g.

4.4.

Proof of Theorem 1.3. The next corollary states that the pruning procedure for stable GW tree developed in [START_REF] Abraham | Pruning Galton-Watson trees and tree-valued Markov processes[END_REF] and the pruning procedure for Lévy trees developed in [START_REF] Abraham | Fragmentation associated with Lévy processes using snake[END_REF] and applied in [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF] to sub-trees with finite number of leaves coincide. Proof. This is a direct consequence of Lemma 4.2 and the fact that M = L( T0 ). Lévy . Then we have for θ ≥ 0:

N (1) [τ (n) 1 ≥ θ] = 1 1 + θ n-1 .
Proof. We keep the notations of the proof of Lemma 4.2. We have:

N (1) [τ (n) 1 ≥ θ] = N N inf u∈N ( T0 ) ζ u ≥ θ T0 M = n = N   u∈N ( T0 ) 1 1 + θ ku( T0 )-1 M = n   = N 1 1 + θ M -1 M = n = 1 1 + θ n-1
, using [START_REF] Abraham | Pruning Galton-Watson trees and tree-valued Markov processes[END_REF] for the third equality.

Proof of Proposition 1.7

We recall results from [START_REF] Haas | Self-similar scaling limits of non-increasing Markov chains[END_REF], Corollary 1. Let X n be the number of coalescence events for a β(a, b)-coalescent. For 1 < a < 2 and b > 0, we have that:

2 -a Γ(a) n a-2 X n converges in distribution towards W a,b = ∞ 0 dt e -(2-a)S a,b (t) ,
where S a,b is a subordinator with Laplace exponent φ a,b given by:

φ a,b (λ) = 1 0 1 -(1 -x) λ x a-3 (1 -x) b-1 dx.
Notice that this notation is consistent with [START_REF] Bertoin | The cut-tree of large Galton-Watson trees and the Brownian CRT[END_REF]. Since Z n is distributed as X n with a = 1+ α and b = 1α. We deduce that:

n α-1 Z n (d) -----→ n→+∞ Z,
with Z distributed as Γ(1+α) 1-α W 1+α,1-α . Using Lemma 3.1, we compute the moments of Z:

E W n 1+α,1-α = n! 0≤t 1 ≤•••≤tn E e -(1-α) n k=1 S 1-α,1+α (t k ) dt 1 • • • dt n = n! 0≤r 1 ,••• ,0≤rn n k=1 E e -(1-α)kS 1-α,1+α (r k ) dr 1 • • • dr n = n! n k=1 φ 1+α,1-α (k(1 -α)) = 1 -α Γ(α) n Γ(n + 1)Γ(1 -α) Γ((n + 1)(1 -α)) •
We deduce that:

E [Z n ] = α n Γ(n + 1)Γ(1 -α) Γ((n + 1)(1 -α)) •

Number of blocks in the last coalescence event

We consider the number of blocks B n involved in the last coalescence event of Π

[n] dis . In order to stress the dependence in n, we shall denote by T n the GW tree T under P n . We also write ξ u (T n ) for ξ u to stress the dependence of the marks introduced in Section 2.2 as a function of the underlying tree T n . Notice that the time ξ ∅ (T n ) at which the root of T n is marked corresponds to the last coalescence event associated with T n . Thanks to Theorem 1.1, B n is distributed as the number of leaves of the pruned tree obtained from T n just before the last coalescence event, that is:

(21) B n (d) = L(P ξ ∅ (Tn)-(T n )).
6.1. Local limit. The method used in [START_REF] Abraham | A construction of a β-coalescent via the pruning of binary trees[END_REF] when α = 1/2 relies on the Aldous's CRT, which is the (global) limit of T n when the length of the branch of T n are rescaled by 1/ √ n, see [START_REF] Duquesne | A limit theorem for the contour process of conditioned Galton-Watson trees[END_REF].

Since Lévy's trees are more difficult to handle, we choose here to use the local limit of T n , which is the Kesten's tree T * , according to [START_REF] Curien | Random non-crossing plane configurations: a conditioned Galton-Watson tree approach[END_REF] Theorem 3.1 or [6] Proposition 4.6.

Recall that ν g is the distribution with generating function g given in (3) and that ν g is critical as g ′ (1) = 1. We recall the distribution of the Kesten's tree T * associated with the critical reproduction law ν g , see [START_REF] Kesten | Subdiffusive behavior of random walk on a random cluster[END_REF]. Let ν * g be the corresponding size-biased distribution: ν * g (k) = kν g (k) for all k ∈ N. For h ∈ N, we consider the truncation operator r h on T defined as: r h t = {u ∈ t; |u| ≤ h}. The distribution of T * is as follows. Almost surely, T * contains a unique infinite path i.e. a unique infinite sequence (V k , k ∈ N * ) of positive integers such that, for every h ∈ N,

V 1 • • • V h ∈ T * , with the convention that V 1 • • • V h = ∅ if h = 0.
The joint distribution of (V k , k ∈ N * ) and T * is determined recursively as follows: for each h ∈ N, conditionally given (V 1 , . . . , V h ) and r h T * , we have:

• The number of children (k v (T * ), v ∈ T * , |v| = h) are independent and distributed according to

ν g if v = V 1 • • • V h and according to ν * g if v = V 1 • • • V h .
• Given also the numbers of children (k v (T * ), v ∈ T * , |v| = h), the vertex V h+1 is uniformly distributed on the set of integers 1, . . . , v∈T * , |v|=h k v (T * ) .

We denote by P the distribution of T * .

Recall that the height of a discrete tree t ∈ T is H max (t) = sup{|u|, u ∈ t}. The local limit convergence of critical GW trees, see [START_REF] Abraham | Local limits of conditioned Galton-Watson trees: the infinite spine case[END_REF], implies that, for all h ∈ N * , t ∈ T with height h: lim n→+∞ P n (r h T n = t) = P(r h T * = t).

Notice that P θ (T * ) is a.s. finite for any θ > 0. By construction of the marks, we easily get that the local limit of (P θ (T n ), θ ≥ 0) is given by (P θ (T * ), θ ≥ 0). Since k ∅ (T n ) converges in distribution to k ∅ (T * ) (with distribution ν * g ), we deduce the convergence in distribution of the mark ξ ∅ (T n ) to ξ * ∅ distributed under P as: P(ξ * ∅ ≥ θ|T * ) = (1 + θ) 1-k ∅ (T * ) . We deduce that the local limit in distribution of P ξ ∅ (Tn)-(T n ) is given by P ξ * ∅ -(T * ). This and the definition of T * gives the following Lemma. For t ∈ T, and u ∈ t, recall the notation t u for the sub-tree attached at u, see [START_REF] Duquesne | A limit theorem for the contour process of conditioned Galton-Watson trees[END_REF]. Lemma 6.1. We have, for all t ∈ T:

lim n→+∞ P n (P ξ ∅ (Tn)-(T n ) = t) = P( T = t),
where T is such that:

• k ∅ ( T ) has distribution ν * g . • Conditionally on k ∅ ( T ), ξ is a random variable such that P(ξ ≥ θ) = (1 + θ) 1-k ∅ ( T ) for all θ ≥ 0. • Conditionally on k ∅ ( T ) and ξ, V 1 is a uniform random variable on {1, . . . , k ∅ ( T )}.

• Conditionally on k ∅ ( T ), ξ and V 1 , ( Tu , u ∈ {1, . . . , k ∅ ( T )}) are independent random trees distributed such that for u = V 1 , T u is distributed as P ξ (T ) with T a GW tree with offspring distribution ν g , and T V 1 is distributed as P ξ (T * ), with T * distributed as the Kesten's tree associated with the reproduction law ν g .

Notice that by construction, T is finite.

6.2. Proof of Proposition 1.8. We deduce from ( 21), Lemma 6.1 and the fact that T is a.s. finite, that B n converge in distribution to B = L( T ). From Lemma 6.1, we have that B is distributed as

L(P ξ (T * )) + k ∅ -1 k=1 L(P ξ (T k )),
where k ∅ has distribution ν * g , ξ has density (k ∅ -1)(1 + θ) -k ∅ 1 {θ≥0} , T * is independent and distributed as the Kesten's tree associated with ν g , and (T k , k ∈ N * ) are independent and distributed as a Galton-Watson tree T with offspring distribution ν g . We deduce that:

E r B = E N (N -1) +∞ 0 (1 + θ) -N dθ E r L θ N -1 E r L * θ ,
where N has distribution ν g , L θ is the number of leaves of P θ (T ) and L * θ is the number of leaves of P θ (T * ).

Let h θ be the generating function of L θ and h * θ be the generating function of L * θ . We have:

E r B = +∞ 0 dθ (1 + θ) 2 g ′′ h θ (r)
1 + θ h θ (r)h * θ (r).

Recall that P θ (T ) is a GW tree whose reproduction law has generating function g θ given by [START_REF] Abraham | Pruning of CRT-sub-trees[END_REF]. Similar arguments as in the proof of [START_REF] Bertoin | Fires on trees[END_REF], yields that: [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF] g θ (h θ (r))h θ (r) = g θ (0)(1r).

We deduce from (8) that:

g ′′ θ (r) = g ′′ r 1 + θ

Figure 1 .

 1 Figure 1. The pruning at node of a given tree. The bold internal node corresponds to the next chosen node.

2. 1 .

 1 Discrete trees. Let us recall here the formalism for ordered discrete trees. We setU = n≥0 (N * ) nthe set of finite sequences of positive integers with the convention (N * ) 0 = {∅}. For u ∈ U let |u| be the length or generation of u defined as the integer n such that u ∈ (N * ) n . If u and v are two sequences of U , we denote by uv the concatenation of the two sequences, with the convention that uv = u if v = ∅ and uv = v if u = ∅. The set of ancestors of u is the set:[START_REF] Abraham | Local limits of conditioned Galton-Watson trees: the infinite spine case[END_REF]

3 .

 3 We denote by Π Lévy (θ) the partition of N * formed by the equivalence classes of R Lévy θ and set Π Lévy = (Π Lévy (θ), θ ≥ 0). 4.3. Lévy sub-trees.

Lemma 4 . 1 .

 41 The distributions of T0 under N[ • M = n] and under N(1) [ • M = n] are the same.

Corollary 4 . 3 .

 43 Let n ∈ N. The process ( Tθ , θ ≥ 0) is distributed under N[ • M = n] as the process (P θ (T ), θ ≥ 0) under P n .

  Theorem 1.3 follows directly from Theorem 1.1 and from the following corollary, which is a direct consequence of Corollary 4.3. Recall that Π[n]Lévy is the restriction of Π Lévy defined in Section 4.2.2 to the n first integers.

	Corollary 4.4. The process	Π[n] Lévy is under N (1) distributed as	Π[n] GW under P n .
	Using Lemma 4.2, we also have the following corollary which shows that the first coalescent
	event in	Π[n] Lévy is not exponentially distributed.
	Corollary 4.5. Let τ	(n) 1	be the first coalescent event in	Π[n]