A representation of exchangeable hierarchies by sampling from real trees
Abstract
A hierarchy on a set $S$, also called a total partition of $S$, is a
collection $\mathcal{H}$ of subsets of $S$ such that $S \in \mathcal{H}$, each
singleton subset of $S$ belongs to $\mathcal{H}$, and if $A, B \in \mathcal{H}$
then $A \cap B$ equals either $A$ or $B$ or $\varnothing$. Every exchangeable
random hierarchy of positive integers has the same distribution as a random
hierarchy $\mathcal{H}$ associated as follows with a random real tree
$\mathcal{T}$ equipped with root element $0$ and a random probability
distribution $p$ on the Borel subsets of $\mathcal{T}$: given
$(\mathcal{T},p)$, let $t_1,t_2, ...$ be independent and identically
distributed according to $p$, and let $\mathcal{H}$ comprise all singleton
subsets of $\mathbb{N}$, and every subset of the form $\{j: t_j \in F_x\}$ as
$x$ ranges over $\mathcal{T}$, where $F_x$ is the fringe subtree of
$\mathcal{T}$ rooted at $x$. There is also the alternative characterization:
every exchangeable random hierarchy of positive integers has the same
distribution as a random hierarchy $\mathcal{H}$ derived as follows from a
random hierarchy $\mathscr{H}$ on $[0,1]$ and a family $(U_j)$ of IID uniform
[0,1] random variables independent of $\mathscr{H}$: let $\mathcal{H}$ comprise
all sets of the form $\{j: U_j \in B\}$ as $B$ ranges over the members of
$\mathscr{H}$.