UC Berkeley

Exchangeability -- the probabilistic symmetry meaning ``invariance under the action of the symmetric group,'' or less formally, ``irrelevance of labels or indices'' -- has been the subject of continuing interest to probabilists and statisticians since de Finetti's celebrated characterization of infinite exchangeable sequences of Bernoulli random variables as mixtures of IID sequences. The topic of this dissertation is exchangeability as it pertains to random partitions and trees.

The main result is a de Finetti-type theorem characterizing a class of exchangeable trees called hierarchies <\italic> which arise in connection with fragmentation processes and hierarchical clustering problems. The other results are somewhat related in that they involve consideration of moments of statistics of exchangeable partitions or trees. One of these concerns random trees with leaves labeled by consecutive natural numbers which are exchangeable in the sense that deterministic permutation of the leaf labels does not change the distribution of the tree. In such trees, the set of interleaf distances is exchangeable, and so, for example, the distance between leaf 1 and leaf 2 is equal in distribution to the distance between leaf 2 and leaf 3. Distributional constraints of this type arising from exchangeability can be used to characterize finite dimensional marginals of well-understood trees such as the Brownian CRT. As an application we show that the Brownian CRT is the scaling limit of uniform random hierarchies. Another result is the characterization of the two-parameter family of Ewens-Pitman partitions by a kind of deletion property: speaking loosely, the Ewens-Pitman family is the class of exchangeable partitions in which the block containing 1 carries no information about the rest of the partition.