Gibbs fragmentation trees
Gibbs fragmentation trees
Bernoulli 14(4), 2008, 988–1002
DOI: 10.3150/08-BEJ134
Gibbs fragmentation trees
PETER MCCULLAGH1 , JIM PITMAN2 and MATTHIAS WINKEL3
1Department of Statistics, University of Chicago, 5734 University Ave, Chicago, IL 60637, USA.
E-mail: pmcc@galton.uchicago.edu
2Statistics Department, 367 Evans Hall # 3860, University of California, Berkeley, CA 94720-
3860, USA. E-mail: pitman@stat.berkeley.edu
3Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK.
E-mail: winkel@stats.ox.ac.uk
We study fragmentation trees of Gibbs type. In the binary case, we identify the most general
Gibbs-type fragmentation tree with Aldous’ beta-splitting model, which has an extended pa-
rameter range β >−2 with respect to the beta(β + 1, β + 1) probability distributions on which
it is based. In the multifurcating case, we show that Gibbs fragmentation trees are associated
with the two-parameter Poisson–Dirichlet models for exchangeable random partitions of N, with
an extended parameter range 0≤ α≤ 1, θ ≥−2α and α< 0, θ =−mα, m ∈ N.
Keywords: Aldous’ beta-splitting model; Gibbs distribution; Markov branching model;
Poisson–Dirichlet distribution
1. Introduction
We are interested in various models for random trees associated with processes of re-
cursive partitioning of a finite or infinite set, known as fragmentation processes [2, 4, 9].
We start by introducing a convenient formalism for the kind of combinatorial trees aris-
ing naturally in this context [16, 18]. Let #B be the number of elements in the finite
non-empty set B. Following standard terminology, a partition of B is a collection
πB = {B1, . . . ,Bk}
of non-empty disjoint subsets of B whose union is B. To introduce a new terminology
convenient for our purpose, we make the following recursive definition. A fragmentation
of B (sometimes called a hierarchy or a total partition) is a collection tB of non-empty
subsets of B such that
(i) B ∈ tB ;
(ii) if #B ≥ 2 then, there is a partition πB of B into k parts, B1, . . . ,Bk, called the
children of B, for some k ≥ 2, with
tB = {B} ∪ tB1 ∪ · · · ∪ tBk , (1)
This is an electronic reprint of the original article published by the ISI/BS in Bernoulli,
2008, Vol. 14, No. 4, 988–1002. This reprint differs from the original in pagination and
typographic detail.
1350-7265 c© 2008 ISI/BS
http://arxiv.org/abs/0704.0945v2
http://isi.cbs.nl/bernoulli/
http://dx.doi.org/10.3150/08-BEJ134
mailto:pmcc@galton.uchicago.edu
mailto:pitman@stat.berkeley.edu
mailto:winkel@stats.ox.ac.uk
http://isi.cbs.nl/BS/bshome.htm
http://isi.cbs.nl/bernoulli/
http://dx.doi.org/10.3150/08-BEJ134
Gibbs fragmentation trees 989
Figure 1. Two fragmentations of [9] graphically represented as trees labeled by subsets of [9].
where tBi is a fragmentation of Bi for each 1≤ i≤ k.
Necessarily, Bi ∈ tB , each child Bi of B with #Bi ≥ 2 has further children, and so on,
until the set B is broken down into singletons. We use the same notation tB both
• for such a collection of subsets of B, and
• for the tree whose vertices are these subsets of B and whose edges are defined by
the parent/child relation determined by the fragmentation.
To emphasize the tree structure, we may call tB a fragmentation tree. Thus, B is the root
of tB and each singleton subset of B is a leaf of tB (see Figure 1 – here [9] = {1, . . . ,9};
we also put [n] = {1, . . . , n}). We denote by TB the collection of all fragmentations of B.
A fragmentation tB ∈ TB is called binary if every A ∈ tB has either 0 or 2 children. We
denote by BB ⊆ TB the collection of binary fragmentations of B.
For each non-empty subset A of B, the restriction to A of tB , denoted tA,B , is the
fragmentation tree whose root is A, whose leaves are the singleton subsets of A and
whose tree structure is defined by restriction of tB . That is, tA,B is the fragmentation
{C ∩ A : C ∩ A 6= ∅,C ∈ tB} ∈ TA, corresponding to a reduced subtree, as discussed by
Aldous [1].
Given a rooted combinatorial tree with no single-child vertices and whose leaves are
labeled by a finite set B, there is a corresponding fragmentation tB , where each vertex
of the combinatorial tree is associated with the set of leaves in the subtree above that
vertex. So the fragmentations defined here provide a convenient way to label the vertices
of a combinatorial tree and to encode the tree structure in the labeling.
A random fragmentation model is an assignment, for each finite subset B of N, of a
probability distribution on TB for a random fragmentation TB of B. We assume through-
out this paper that the model is exchangeable, meaning that the distribution of TB is
invariant under the obvious action of permutations of B on fragmentations of B. The
distribution of ΠB , the partition of B generated by the branching of TB at its root, is
then of the form
P(ΠB = {B1, . . . ,Bk}) = p(#B1, . . . ,#Bk) (2)
for all partitions {B1, . . . ,Bk} with k ≥ 2 blocks and some symmetric function p of com-
positions of positive integers, called a splitting probability rule. The model is called
990 P. McCullagh, J. Pitman and M. Winkel
• consistent if for every A⊂B, the restricted tree TA,B is distributed like TA;
• Markovian if, given ΠB = {B1, . . . ,Bk}, the k restricted trees TB1,B, . . . , TBk,B are
independent and distributed as TB1 , . . . , TBk ;
• binary if TB is a binary tree with probability one, for every B.
Aldous [2] initiated the study of consistent Markovian binary trees as models for neutral
evolutionary trees. He observed parallels between these models and Kingman’s theory
of exchangeable random partitions of N, and posed the problem of characterizing these
models analogously to known characterizations of the Ewens sampling formula for random
partitions. In [9], we showed how consistent Markovian trees arise naturally in Bertoin’s
theory of homogeneous fragmentation processes [4] and deduced from Bertoin’s theory a
general integral representation for the splitting rule of a Markovian fragmentation model.
To briefly review these developments in the binary case, the distribution of a Markovian
binary fragmentation TB is determined by a splitting rule p, which is a symmetric function
p of pairs of positive integers (i, j), according to the following formula for the probability
of a given tree t ∈ BB :
P(TB = t) =
A∈t:#A≥2
p(#A1,#A2), (3)
where A1 and A2 denote the two children of A in the tree TB .
The following proposition collects some known results.
Proposition 1. (i) Every non-negative symmetric function p subject to normalization
conditions
p(k,n− k) = 1 for all n≥ 2
defines a Markovian binary fragmentation model.
(ii) A splitting rule p gives rise to a consistent Markovian binary fragmentation if
and only if
p(i, j) = p(i+1, j) + p(i, j + 1)+ p(i+ j,1)p(i, j) for all i, j ≥ 1. (4)
(iii) Every consistent splitting rule admits an integral representation
p(i, j) =
Z(i+ j)
(0,1)
xi(1− x)jν(dx) + c1{i=1 or j=1}
for all i, j ≥ 1, (5)
with characteristics c≥ 0 and ν a symmetric measure on (0,1) with
(0,1)
x(1−x)ν(dx)<
∞, and Z(n) a sequence of normalization constants.
Proof. (i) is elementary. For (ii), Ford [6], Proposition 41, gave a characterizaton of
consistency for models of unlabeled trees which is easily shown to be equivalent to the
Gibbs fragmentation trees 991
condition stated here. The interpretation (and sketch of proof) of this condition is that
for B = C ∪ {k} (with k /∈ C), the vertex C of TC splits into a particular partition of
sizes i and j if and only if TB splits into that partition with k added to one or the other
block, or if TB first splits into C and {k} and then C splits further into that partition
of sizes i and j. (iii) is directly read from [9]. �
Aldous [2] studied in some detail the beta-splitting model which arises as the particular
case of (5) with characteristics c= 0 and
ν(dx) = xβ(1− x)βdx for β ∈ (−2,∞) and ν(dx) = δ1/2(dx) for β =∞. (6)
Aldous posed the problem of characterizing this model among all consistent binary
Markov models. The main focus of this paper is the following result.
Theorem 2. Aldous’ beta-splitting models for β ∈ (−2,∞] are the only consistent
Markovian binary fragmentations with splitting rule of the form
p(i, j) =
w(i)w(j)
Z(i+ j)
for all i, j ≥ 1, (7)
for some sequence of weights w(j)≥ 0, j ≥ 1, and normalization constants Z(n), n≥ 2.
As a corollary, we extract a statement purely about measures on (0,1).
Corollary 3. Every symmetric measure ν on (0,1) with
(0,1)
x(1−x)ν(dx)<∞, whose
moments factorize into the form
(0,1)
xi(1− x)jν(dx) =w(i)w(j) for all i, j ≥ 1
for some w(i)≥ 0, i≥ 1, is a multiple of one of Aldous’ beta-splitting measures (6).
In particular, this characterizes the symmetric beta distributions among probability
measures on (0,1).
Berestycki and Pitman [3] encountered a different one-dimensional class of Gibbs split-
ting rules in the study of fragmentation processes related to the affine coalescent. These
are not consistent, but the Gibbs fragmentations are naturally embedded in continuous
time.
The rest of this paper is organized as follows. Section 2 offers an alternative char-
acterization of what we call binary Gibbs models, meaning models with splitting rule
of the form (7), without assuming consistency. Theorem 2 is then proved in Section 3.
In Section 4, we discuss growth procedures and embedding in continuous time for the
consistent case. Section 5 gives a generalization of the Gibbs results to multifurcating
trees.
992 P. McCullagh, J. Pitman and M. Winkel
2. Characterization of binary Gibbs fragmentations
The Gibbs model (7) is overparameterized: if we multiply w(k), k ≥ 1, by abk (and
then Z(m), m≥ 2, by a2bm), the model remains unchanged. Note, further, that neither
w(1) = 0 nor w(2) = 0 is possible since then (7) does not define a probability function for
n= i+ j = 3. Hence, we may assume w(1) = 1 and w(2) = 1. It is now easy to see that
for any two different such sequences, the models are different. Note that the following
result does not assume a consistent model.
Proposition 4. The following two conditions on a collection of random binary fragmen-
tations TB indexed by finite subsets B of N are equivalent:
(i) TB is for each B an exchangeable Markovian binary fragmentation with splitting
rule of the Gibbs form (7) for some sequence of weights w(j)> 0, j ≥ 1, and normaliza-
tion constants Z(n), n≥ 2;
(ii) for each B, the probability distribution of TB is of the form
P(TB = t) =
w(#B)
ψ(#A) for all t ∈ BB , (8)
for some sequence of weights ψ(j)> 0, j ≥ 1, and normalisation constants w(n), n≥ 1.
More precisely, if (i) holds with w(1) = 1, then (ii) holds for the same sequence w with
ψ(1) = 1 and ψ(k) =w(k)/Z(k), k ≥ 2. (9)
Conversely, if (ii) holds for some sequence ψ with ψ(1) = 1, then (i) holds for the sequence
w(n), n≥ 1, determined by (8); in particular, w(1) = 1.
Proof. Given a Gibbs model with w(1) = 1, we can combine (3) and (7) to get, for all
t ∈ BB ,
P(TB = t) =
A∈t:#A≥2
w(#A1)w(#A2)
Z(#A)
w(#B)
A∈t:#A≥2
w(#A)
Z(#A)
If we make the substitution (9), we can read off w(n) as the correct normalization constant
and (8) follows, with ψ(1) = 1.
On the other hand, (8) determines the sequence w(n), n≥ 1, as
w(n) =
t∈B[n]
ψ(#A).
Note, in particular, that w(1) = ψ(1). We can express the normalization constants in the
Gibbs model (7) by the formula
Z(m) =
w(k)w(m− k) (10)
Gibbs fragmentation trees 993
t1∈B[k]
ψ(#A)
t2∈B[m−k]
ψ(#A)
t∈B[m]
A∈t:A 6=[m]
ψ(#A) =w(m)/ψ(m),
as in (9). By application of the previous implication from (i) to (ii), formula (8) gives
the distribution of the Gibbs model derived from this weight sequence w(n) and the
conclusion follows. �
Note that the normalization constant Z(m) in the Gibbs splitting rule (7) model and
given in (10) is a partial Bell polynomial in w(1),w(2), . . . (see [15] for more applications of
Bell polynomials), whereas the normalization constant w(n) in the Gibbs tree formula (8)
is a polynomial in ψ(1), ψ(2), . . . of a much a more complicated form. The normalization
constant in (8) is
w(n) =
t∈B[n]
ψ(#A).
In an attempt to study this polynomial in ψ(1), ψ(2), . . . , we introduce the signature
σt : [n]→N of a tree t ∈ B[n] by
σt(j) =#{A ∈ t :#A= j}, j = 1, . . . , n.
Note that P(Tn = t) depends on t only via σt, that is, σt is a sufficient statistic for
the Gibbs probabilities (8). Denote the set of signatures by Sign = {σt : t ∈ B[n]}. The
inductive definition of B[n] yields
Sign = {σ
(1) + σ(2) + 1n :σ
(1) ∈ Sign1 , σ
(2) ∈ Sign2 , n1 + n2 = n},
where 1n(j) = 1 if j = n, 1n(j) = 0 otherwise. The coefficients Qσ in w(n), when expanded
as a polynomial in ψ(1), ψ(2), . . . , are numbers of fragmentations with the same signature
σ ∈ Sign:
w(n) =
σ∈Sign
σ, where ψσ =
ψ(j)σ(j).
Let us associate with each fragmentation t ∈ B[n] its tree shape (combinatorial tree
without labels) t◦ and denote by B◦n the collection of shapes of binary trees with n
leaves. Clearly, two fragmentations with the same tree shape have the same signature,
so we can define σ(t◦) in the obvious way. For n ≤ 8 (and many larger trees), direct
enumeration shows that the tree shape t◦ ∈ B◦n is uniquely determined by its signature
σ, and Qσ is just the number q(t
◦) of different labelings. For n≥ 9, this is false: there
are two tree shapes with signature (9,3,1,2,1,0,0,0,1); see Figure 2. If we denote by
994 P. McCullagh, J. Pitman and M. Winkel
I◦σ ⊆ B
n the set of tree shapes with signature σ, then Qσ =
t◦∈I◦
q(t◦). The remaining
combinatorial problem is therefore to study I◦σ and q(t
◦). We have not been able to solve
this problem. The preprint version [12] of the present paper includes an Appendix with
a partial study: see also Corollary 2.4.3 of [17].
3. Consistent binary Gibbs rules
The statement of Theorem 2 specifies Aldous’ [2] beta-splitting models by their integral
representation (5). Observe that the moment formula for beta distributions easily gives
p(i, j) =
Z(i+ j)
xi+β(1− x)j+β dx
Γ(i+ β + 1)Γ(j + β + 1)
R(i+ j)
for all i, j ≥ 1,
for normalization constants R(n) = Z(n)Γ(n+ 2β + 2), n ≥ 2. This is for β ∈ (−2,∞).
For β =∞, we simply get p(i, j) = 1/R(i+ j) for all i, j ≥ 1, where R(n) = Z(n)2n, n≥ 2.
Proof of Theorem 2. We start from a general Gibbs model (7) with w(1) = 1 and
follow [7], Section 2 closely, where a similar characterization is derived in a partition
rather than a tree context. Let the Gibbs model be consistent. This immediately implies
that w(j)> 0 for all j ≥ 1. The consistency criterion (4) in terms of Wj =w(j +1)/w(j)
now gives
Wi +Wj =
Z(i+ j + 1)−w(i+ j)
Z(i+ j)
for all i, j ≥ 1. (12)
The right-hand side is a function of i+ j, soWj+1−Wj is constant and henceWj = a+bj
for some b≥ 0 and a >−b. Now, either b= 0 (excluded for the time being) or
w(j) =W1 · · ·Wj−1 =
(a+ bq)
Figure 2. Two tree shapes with the same signature (here marked by subtree sizes).
Gibbs fragmentation trees 995
= bj−1
= bj−1
Γ(a/b+ j)
Γ(a/b+ 1)
and, hence, reparameterizing by β = a/b − 1 ∈ (−2,∞) and pushing bi+j−2 into the
normalization constant di+j = b
i+j−2/Z(i+ j), we have
p(i, j) =
w(i)w(j)
Z(i+ j)
= di+j
Γ(i+ 1+ β)
Γ(2 + β)
Γ(j + 1+ β)
Γ(2+ β)
The case b= 0 is the limiting case β =∞, when, clearly, w(j) ≡ 1 (now pushing ai+j−2
into the normalization constant).
These are precisely Aldous’ beta-splitting models, as in (11). �
While we identified the boundary case β =∞ as being of Gibbs type, the boundary
case β =−2 is not of Gibbs type, although it can still be made precise as a Markovian
fragmentation model with characteristics c > 0 and ν = 0 (pure erosion): p(i, j) = 0 unless
i= 1 or j = 1, so the Markovian fragmentations Tn are combs, where all n− 1 branching
vertices are lined up in a single spine.
In the proof of the theorem, we obtained as parameterization for the Gibbs models
w(j) =
Γ(j +1+ β)
Γ(2 + β)
, j ≥ 1, (13)
for some β ∈ (−2,∞), or w(j)≡ 1 for β =∞. Note that the simple convention w(2) = 1
from Section 2 is not useful here. We can now still deduce the parameterization (8) by
Proposition 4, in principle. However, since ψ(k) =w(k)/Z(k) involves partial Bell polyno-
mials Z(k) in w(1),w(2), . . . , this is less explicit in terms of β than the parameterization
ψ(2) = 2+ β, ψ(3) =
, ψ(4) =
(3 + β)(4 + β)
18 + 7β
, . . . .
Special cases that have been studied in various biology and computer science contexts
(see Aldous [2] for a review) include the following: β = −3/2,−1,0,∞. In these cases,
we can explicitly calculate the Gibbs parameters in (7) and (8) and the normalisation
constants.
If β = −3/2, we can take ψ(n) ≡ 1 and TB is uniformly distributed : if #B = n, then
P(TB = t) = 2
n−1(n − 1)!/(2n− 2)!, t ∈ BB . The asymptotics of uniform trees lead to
Aldous’ Brownian CRT [1]; see also [15], Section 6.3. Table 1 uses a different parameter-
ization via the convenient relations (9) and (13).
The case β = −1 is the limiting conditional distribution in the Ewens family as the
Ewens parameter λ→ 0, conditional on the occurrence of a split. The β = 0 case is
known as the Yule model and β = ∞ as the symmetric binary trie (see Aldous [2]).
Continuum tree limits of the beta-splitting model for β ∈ (−2,−1) are described in [9].
996 P. McCullagh, J. Pitman and M. Winkel
The normalization that leads to a compact limit tree is here T[n]/n
−β−1, where T[n] is
represented as a metric tree with unit edge lengths and the scaling T[n]/n
−β−1 refers
to scaling of edge lengths. Aldous [2] studies weaker asymptotic properties for average
distance from a leaf to the root, also for β ≥−1, where growth is logarithmic.
4. Growth rules and embedding in continuous time
In [9], we study the consistently growing sequence Tn, n≥ 1, where Tn := T[n] = T[n],[n+1]
is the restriction of Tn+1 to [n] for all n≥ 1, in a general context of consistent Marko-
vian multifurcating fragmentation models. The integral representation (5) stems from an
association with Bertoin’s theory of homogeneous fragmentation processes in continuous
time [4]. Let us here look at the binary case in general and Gibbs fragmentations in
particular.
Consider the distribution of Tn+1, given Tn. The tree Tn+1 has a vertex A ∪ {n+ 1}
with children {n + 1} and A ∈ Tn. We say that n + 1 has been attached below A. In
passing from Tn to Tn+1, leaf n+1 can be attached below any vertex A of Tn (including
[n] and all leaf nodes). Note that to construct Tn+1 from Tn, n+ 1 is also added as an
element to all vertices on the path from [n] to A. Vertex A ∈ Tn is special in that both
A and A∪ {n+ 1} are in Tn+1.
Fix a vertex A of t ∈ B[n] and consider the conditional probability, given Tn = t, of
n+ 1 being attached below A. This is the ratio of two probabilities of the form (3) in
which many common factors cancel so that only the probabilities along the path from
[n] to A remain. This yields the following result.
Proposition 5. Let t ∈ B[n] and A ∈ t. Denote by
[n] =A1 ⊃ · · · ⊃Ah =A
Table 1. Closed form expressions of the parameters for β =
−3/2,−1,0,∞
β −3/2 −1 0 ∞
(2n− 2)!
22n−2(n− 1)!
(n− 1)! n! 1
(2n− 2)!
22n−3(n− 1)!
(n− 1)!
(n− 1)n! 2n−1 − 1
2n−1 − 1
Gibbs fragmentation trees 997
the path from [n] to A. We refer to h≥ 1 as the height of A in t. The probability that
n+1 attaches below A is then
p(#Aj+1 + 1,#(Aj \Aj+1))
p(#Aj+1,#(Aj \Aj+1))
p(#Ah,1).
For the uniform model (Gibbs fragmentation with β =−3/2), this product is telescop-
ing, or we calculate directly from (8)
p(#Aj+1 +1,#(Aj \Aj+1))
p(#Aj+1,#(Aj \Aj+1))
p(#Ah,1) =
2n− 1
giving a simple sequential construction (see, e.g., [15], Exercise 7.4.11).
It was shown in [9] that consistent Markovian fragmentation models can be assigned
consistent independent exponential edge lengths, where the edge below vertex A is given
parameter λ#A, for a family (λm)m≥1 of rates, where λ1 = 0, λ2 is arbitrary and λm,
m≥ 3, is determined by λ2 and the splitting rule p, in that consistency requires
λn+1(1− p(n,1)) = λn for all n≥ 2. (14)
The interpretation is that the partition of [n+1] in Tn+1 (arriving at rate λn+1) splits [n]
only with probability 1− p(n,1) and this thinning must reduce the rate for the partition
of [n] in Tn to λn. This rate λn also applies in Tn+1 after a first split {[n],{n+ 1}}.
Using consistency, equation (14) also implies
λnp(i, j) = λn+1(p(i, j + 1)+ p(i+ 1, j)) for all i, j ≥ 1 with i+ j = n.
For the Gibbs fragmentation models, we obtain, using (14), (7), (12) and (13),
λn = λ2
1− p(j,1)
Z(j + 1)
Z(j + 1)−w(j)
= λ2Z(n)
W1 +Wj−1
= λ2Z(n)
w(j − 1)
w(2)w(j − 1) +w(j)
= λ2Z(n)
Γ(4 + 2β)
Γ(n+2+ 2β)
where we require β <∞ for the last step. Table 2 contains the rate sequences for β =
−3/2,−1,0,∞ in the case λ2 = 1.
Not only is (λn)n≥3 determined by p, but a converse of this also holds.
Proposition 6. Let (λn)n≥2 be a consistent rate sequence associated with a consistent
Markovian binary fragmentation model with splitting rule p, meaning that (14) holds.
Then, p is uniquely determined by (λn)n≥2.
998 P. McCullagh, J. Pitman and M. Winkel
Proof. It is evident from (14) that p(n,1) is determined for all n ≥ 2, and p(1,1) = 1.
Now, (4) for i= 1 determines p(i+1, j) for all j ≥ 2, and an induction in i completes the
proof. �
A more subtle question is to ask what sequences (λn)n≥2 arise as consistent rate
sequences. The above argument can be made more explicit to yield
p(k,n− k) =
(−1)k−j+1
λn−j , 1≤ k ≤ n/2,
which means that (λn)n≥2 must have a discrete complete monotonicity, in that kth
differences of (λn)n≥2 must be of alternating signs, k ≥ 1. This condition is not sufficient,
however, as simple examples for n= 3 show (λn = (n− 1)
α is completely monotone for
α ∈ (0,1), but exchangeability implies that 1/3 = p(1,2) = (λ3 −λ2)/λ3 and so λ3 = 3/2,
whereas (3− 1)α ∈ (1,2) – even in the multifurcating case, cf. Section 5, we always have
λ3 ≤ 3/2).
Proposition 7. A sequence (λn)n≥2 arises as rate sequence of a consistent Markovian
binary fragmentation model if and only if
λn = nc+
(0,1)
(1− xn − (1− x)n)ν(dx)
for some c≥ 0 and ν a symmetric measure on (0,1) with
(0,1)
x(1− x)ν(dx) <∞. The
characteristics of the splitting rules associated with (λn)n≥2 are (c, ν).
Proof. This is a consequence of the integral representation (5) and [9], Proposition 3.
Specifically, the association with Bertoin’s theory of homogeneous fragmentations yields
that each of 1, . . . , n suffer erosion (being turned into a singleton) at rate c; the measure
ν(dx) gives the rate of fragmentations into two parts, to which 1, . . . , n are allocated
independently with probabilities (x,1− x), hence splitting [n] with probability 1− xn −
(1− x)n. �
The complete monotonicity is related to the study of the block containing 1, a tagged
fragment ; see [4, 10]. Since λn is the rate at which one or more of {2, . . . , n} leave the
Table 2. Explicit rate sequences for β =−3/2,−1,0,∞
β −3/2 −1 0 ∞
22n−3
2n− 2
) n−1
3n− 3
2(1− 2−(n−1)).
Gibbs fragmentation trees 999
block containing 1, the rate is composed of three components – a rate c for the erosion
of 1, a rate (n− 1)c for the erosion of 2, . . . , n and a rate Λ(dz) of fragmentations into
two parts, to which 2, . . . , n are allocated independently with probabilities (e−z,1− e−z),
with 1 in the former part, hence splitting [n] with probability 1− e−(n−1)z . Therefore
λn = c+ (n− 1)c+
(0,∞)
(1− e−(n−1)z)Λ(dz) = cn+
(0,1)
1− ξn−1
µ(dξ) = Φ(n− 1)
for a Bernstein function Φ, a finite measure µ on (0,1) or a Lévy measure Λ on (0,∞)
(0,∞)
(1∧x)Λ(dx)<∞; (see [4, 8, 10]), that is, λn can be extended to a completely
monotone function of a real parameter.
5. Multifurcating Gibbs fragmentations and
Poisson–Dirichlet models
As a generalization of the binary framework of the previous sections, we consider in this
section consistent Markovian fragmentation models with splitting rule p as in (2) of the
Gibbs form
p(n1, . . . , nk) =
w(ni) (15)
for some w(j) ≥ 0, j ≥ 1, a(k) ≥ 0, k ≥ 2, and normalization constants c(n) > 0, n ≥ 2.
Note that we must have w(1)> 0 and a(2)> 0 to get positive probabilities for n= 2. To
remove overparameterization, we will assume w(1) = 1 and a(2) = 1. Also, if we multiply
w(j) by bj−1 and a(k) by bk (and c(n) by bn), the model remains unchanged. We will
use this observation to get a nice parameterization in the consistent case (Theorem 8
below).
In [9], we showed that consistency of the model is equivalent to the set of equations
p(n1, . . . , nk) = p(n1 + 1, n2, . . . , nk) + · · ·+ p(n1, . . . , nk + 1)+ p(n1, . . . , nk,1)
+ p(n1 + · · ·+ nk,1)p(n1, . . . , nk)
for all n1, . . . , nk ≥ 1, k ≥ 2. We also established an integral representation extending (5)
to the multifurcating case. The special case relevant for us is in terms of a measure ν on
S↓ = {s = (si)i≥1 : s1 ≥ s2 ≥ · · · ≥ 0, s1 + s2 + · · ·= 1} satisfying
(1− s1)ν(ds)<∞:
p(n1, . . . , nk) =
Z(n1 + · · ·+ nk)
i1,...,ik distinct
ν(ds). (17)
The general case has a further parameter c ≥ 0, as in (5), and also allows ν to charge
(si)i≥1 with s1 + s2 + · · ·< 1; see [9]. We will only meet the extreme case p(1, . . . ,1) = 1,
which corresponds to ν = δ(0,0,...).
1000 P. McCullagh, J. Pitman and M. Winkel
We set
a(k+ 1)
c(n+1)
w(n+ 1)
and, in analogy to Proposition 5, we find that, given Tn = t ∈ T[n], for each vertex B ∈ t,
the probability that n+ 1 attaches below B is
Wnj+1
a(2)w(nh)w(1)
c(nh +1)
where [n] ⊃ S1 ⊃ · · · ⊃ Sh = B is the path from [n] to B, nj =#Sj and kj denotes the
number of children of Sj , j = 1, . . . , h.
However, n+1 can also attach as a singleton block to an existing partition {B1, . . . ,Bk}
of B ∈ Tn. In this case, we say that n+ 1 attaches to the vertex B. For each non-leaf
vertex B ∈ t, the probability that n+ 1 attaches to the vertex B is
Wnj+1
Akhw(1)
In this framework, we have the following generalization of Theorem 2 to the multifurcat-
ing case.
Theorem 8. If p is of the Gibbs form (15) and consistent, then p is associated with the
two-parameter Ewens–Pitman family given by
w(n) =
Γ(n−α)
Γ(1− α)
, n≥ 1, and a(k) = αk−2
Γ(k+ θ/α)
Γ(2 + θ/α)
, k ≥ 2
(or limiting quantities α ↓ 0), c(n), n≥ 1, being normalization constants, for a parameter
range extended as follows:
• either 0≤ α < 1 and θ >−2α (multifurcating cases with arbitrarily high block num-
bers),
• or α < 0 and θ = −mα for some integer m ≥ 3 (multifurcating with at most m
blocks),
• or α< 1 and θ =−2α (binary case),
• or α = −∞ and θ = m for some integer m ≥ 2, that is, a(2) = 1, a(k) = (m −
2) · · · (m− k + 1), k ≥ 3, and w(j) ≡ 1 (recursive coupon collector, where a split of
[n] is obtained by letting each element of [n] pick one of m coupons at random, just
conditioned so that at least two different coupons are picked),
• or α= 1, that is, w(1) = 1, w(j) = 0, j ≥ 2 (deterministic split into singleton blocks).
In terms of the integral representation (17), the measure ν on S↓ is, respectively, size-
ordered Poisson–Dirichlet(α, θ), Dirichlet(−α, . . . ,−α), Beta(−α,−α), δ(1/m,...,1/m) and
δ(0,0,...).
Gibbs fragmentation trees 1001
Proof. For the Gibbs fragmentation model with w(1) = a(2) = 1 and w(j) > 0 for all
j ≥ 2 with notation as introduced, consistency (16) is easily seen to be equivalent to
Cn =Wn1 + · · ·+Wnk +Ak +
for all n1 + · · ·+ nk = n, (18)
where k ≤m if m= inf{i≥ 1 :a(i+ 1) = 0}<∞.
As in the proof of Theorem 2, we deduce from this (the special case k = 2) that either
Wj = a > 0 (excluded for the time being as b= 0) or
Wj = a+ bj ⇒ w(j) =W1 . . .Wj−1 = b
j−1Γ(j −α)
Γ(1− α)
for all j ≥ 1,
for some b > 0, a > −b and α := −a/b < 1. As noted above, we can reparameterize so
that we get b= 1 without loss of generality. In particular, Wj = j−α, j ≥ 1, and so (18)
reduces to
Cn = n− kα+Ak +
for all 2≤ k ≤m∧ n.
Similarly, we deduce that θ :=Ak−kα does not depend on k and so a(k) = θ
k−2 if α= 0,
and otherwise,
Ak = θ+ kα ⇒ a(k) =A2 . . .Ak−1 = α
k−2Γ(k+ θ/α)
Γ(2 + θ/α)
for all 2≤ k ≤m+ 1.
Note that this algebraic derivation leads to probabilities in (15) only in the following
cases.
• If 0 ≤ α < 1, then a(3) = A2 = θ + 2α > 0 if and only if θ > −2α, and then also
Ak = θ+ kα > 0 and a(k)> 0 for all k ≥ 3.
• If α< 0, then a(3) =A2 = θ+2α> 0 if and only if θ >−2α also, but then Ak = θ+kα
is strictly decreasing in k and Ak < 0 eventually, which impedes m=∞. If we have
m<∞, we achieve a(m+ 1) = 0 if and only if θ =−mα. The iteration only takes
us to a(m+ 1) = 0 and we specify a(k) = 0 for k >m also. We cannot specify a(k),
k > m + 1, differently, since every consistent Gibbs fragmentation with a(k) > 0
for k > m+ 1 has the property that T[k] = {[k],{1}, . . . ,{k}} has only one branch
point [k] of multiplicity k with positive probability, but then the restricted tree
T[m+1],[k] = {[m+ 1],{1}, . . . ,{m+ 1}} with positive probability, which contradicts
a(m+ 1) = 0.
• If a(3) = 0, that is, m= 2, the argument of the preceding bullet point shows that we
are in the binary case a(k) = 0 for all k ≥ 3 and we can conclude by Theorem 2.
• The case b= 0 is the limiting case α=−∞ with w(j)≡ 1. We take up the argument
to see that Ak = θ − k and so m<∞ and θ =m, where we then get a(2) = 1 and
a(k) = (m− 2) · · · (m− k+ 1), 3≤ k ≤m+ 1.
1002 P. McCullagh, J. Pitman and M. Winkel
Finally, if w(m) = 0 for some m ≥ 2, then consistency imposes w(j) = 0 for all j ≥m,
and it follows from the integral representation (17) that in fact w(j) = 0 for all j ≥ 2.
The identification of ν on the standard parameter range can be read from [15], Section
3.2. For the extension −α≥ θ≥−2α, we refer to [10]. �
Kerov [11] showed that the only exchangeable partitions of N of Gibbs type are of
the two-parameter family PD(α, θ) with usual range for parameters θ > −α, etc.; see
also [7, 14]. Theorem 8 is a generalization to splitting rules that allows an extended
parameter range for the same reason as in the binary case: the trivial partition of one
single block is excluded from p and when associating consistent exponential edge lengths
with parameters λm, m≥ 1, the first split of [m+1] happens at a higher and higher rate
and we may have λm →∞. In fact,
κ({π ∈ PN :π|[n] = {B1, . . . ,Bk}}) = λnp(#B1, . . . ,#Bk)
uniquely defines a σ-finite measure on PN \ {N}, the set of non-trivial partitions of N,
associated with a homogeneous fragmentation process. This is closely related to (17)
via Kingman’s paintbox representation κ =
κsν(ds). The extended range was first
observed by Miermont [13] in the special case θ = −1 (related to the stable trees of
Duquesne and Le Gall [5]).
We refer to [10] for a study of spinal partitions of Markovian fragmentation models.
There are notions of fine and coarse spinal partitions. First, remove from Tn the spine
of 1, that is, the path from [n] to {1}. The resulting collection is a disjoint union of
fragmentations of sets Bj , say, that form a partition of {2, . . . , n}, which is called the fine
spinal partition. Second, merge blocks (in the multifurcating case) that were children of
the same spinal vertex; the resulting partition is called the coarse spinal partition. It is
shown that for the splitting rules from the two-parameter family with parameters α and
θ (the Gibbs fragmentations), the fine partition is obtained from the coarse partition by
applying independently for each block of the coarse partition an exchangeable partition
from the two-parameter family of random partitions, with parameters α and α+ θ.
Acknowledgements
This research was supported in part by EPSRC Grant GR/T26368/01 and NSF Grants
DMS-04-05779 and DMS-03-05009. M. Winkel was also supported by the Institute of
Actuaries and the insurance group Aon Limited.
References
[1] Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1–28. MR1085326
[2] Aldous, D. (1996). Probability distributions on cladograms. In Random Discrete Struc-
tures (Minneapolis, MN, 1993). IMA Vol. Math. Appl. 76 1–18. New York: Springer.
MR1395604
http://www.ams.org/mathscinet-getitem?mr=1085326
http://www.ams.org/mathscinet-getitem?mr=1395604
Gibbs fragmentation trees 1003
[3] Berestycki, N. and Pitman, J. (2007). Gibbs distributions for random partitions generated
by a fragmentation process. J. Stat. Phys. 127 381–418. MR2314353
[4] Bertoin, J. (2001). Homogeneous fragmentation processes. Probab. Theory Related Fields
121 301–318. MR1867425
[5] Duquesne, T. and Le Gall, J.-F. (2002). Random trees, Lévy processes and spatial branching
processes. Astérisque 281 vi+147. MR1954148
[6] Ford, D.J. (2005). Probabilities on cladograms: Introduction to the alpha model. Preprint.
arXiv:math.PR/0511246.
[7] Gnedin, A. and Pitman, J. (2005). Exchangeable Gibbs partitions and Stirling triangles.
Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 325 (Teor. Predst.
Din. Sist. Komb. i Algoritm. Metody 12) 83–102, 244–245. MR2160320
[8] Gnedin, A. and Pitman, J. (2006). Moments of convex distribution functions and completely
alternating sequences. Preprint. arXiv:math.PR/0602091.
[9] Haas, B., Miermont, G., Pitman, J. and Winkel, M. (2006). Continuum tree asymp-
totics of discrete fragmentations and applications to phylogenetic models. Preprint.
arXiv:math.PR/0604350. Ann. Probab. To appear.
[10] Haas, B., Pitman, J. and Winkel, M. (2007). Spinal partitions and invariance under re-
rooting of continuum random trees. Preprint. arXiv:0705.3602. Ann. Probab. To ap-
pear.
[11] Kerov, S. (2005). Coherent random allocations, and the Ewens–Pitman formula. Zap.
Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 325 (Teor. Predst.
Din. Sist. Komb. i Algoritm. Metody 12) 127–145, 246. MR2160323
[12] McCullagh, P., Pitman, J. and Winkel, M. (2007). Gibbs fragmentation trees. Preprint.
arXiv:0704.0945.
[13] Miermont, G. (2003). Self-similar fragmentations derived from the stable tree. I. Splitting
at heights. Probab. Theory Related Fields 127 423–454. MR2018924
[14] Pitman, J. (2003). Poisson–Kingman partitions. In Statistics and Science: A Festschrift for
Terry Speed. IMS Lecture Notes Monogr. Ser. 40 1–34. Beachwood, OH: Inst. Math.
Statist. MR2004330
[15] Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875. Lec-
tures from the 32nd Summer School on Probability Theory held in Saint-Flour, July
7–24, 2002. Berlin: Springer. MR2245368
[16] Schroeder, E. (1870). Vier combinatorische Probleme. Z. f. Math. Phys. 15 361–376.
[17] Semple, C. and Steel, M. (2003). Phylogenetics. Oxford Lecture Series in Mathematics and
Its Applications 24. Oxford Univ. Press. MR2060009
[18] Stanley, R.P. (1999). Enumerative Combinatorics. 2. Cambridge Studies in Advanced Math-
ematics 62. Cambridge Univ. Press. MR1676282
Received April 2007 and revised March 2008
http://www.ams.org/mathscinet-getitem?mr=2314353
http://www.ams.org/mathscinet-getitem?mr=1867425
http://www.ams.org/mathscinet-getitem?mr=1954148
http://arxiv.org/math.PR/0511246
http://www.ams.org/mathscinet-getitem?mr=2160320
http://arxiv.org/math.PR/0602091
http://arxiv.org/math.PR/0604350
http://arxiv.org/math.PR/0705.3602
http://www.ams.org/mathscinet-getitem?mr=2160323
http://arxiv.org/math.PR/0704.0945
http://www.ams.org/mathscinet-getitem?mr=2018924
http://www.ams.org/mathscinet-getitem?mr=2004330
http://www.ams.org/mathscinet-getitem?mr=2245368
http://www.ams.org/mathscinet-getitem?mr=2060009
http://www.ams.org/mathscinet-getitem?mr=1676282
	Introduction
	Characterization of binary Gibbs fragmentations
	Consistent binary Gibbs rules
	Growth rules and embedding in continuous time
	Multifurcating Gibbs fragmentations and Poisson–Dirichlet models
	Acknowledgements
	References
