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 $\mathcal{H}$ on $[0,1]$ and a family $(U_j)$ of IID uniform [0,1] random variables independent of $\mathcal{H}$: let $\mathcal{H}$ comprise all sets of the form $\{j:U_j\in B\}$ as $B$ ranges over the members of $\mathcal{H}$.

29 pages, 6 figures

References in corpus (5)

• Random trees and applications
• Small-time behavior of beta coalescents
• Spinal partitions and invariance under re-rooting of continuum random trees
• Bayesian Rose Trees
• Ranked Fragmentations

Cited by in corpus (4)

• On the Aldous diffusion on Continuum Trees. I
• Mass-structure of weighted real trees
• On trees invariant under edge contraction
• Regenerative tree growth: structural results and convergence