We introduce a notion of finite sampling consistency for phylogenetic trees and show that the set of finitely sampling-consistent and exchangeable distributions on n-leaf phylogenetic trees is a polytope. We use this polytope to show that the set of all exchangeable and sampling-consistent distributions on four-leaf phylogenetic trees is exactly Aldous’ beta-splitting model, and give a description of some of the vertices for the polytope of distributions on five leaves. We also introduce a new semialgebraic set of exchangeable and sampling consistent models we call the multinomial model and use it to characterize the set of exchangeable and sampling-consistent distributions. Using this new model, we obtain a finite de Finetti-type theorem for rooted binary trees in the style of Diaconis’ theorem on finite exchangeable sequences.

Motivated by the gene tree/species tree problem from statistical phylogenetics, we extend the class of Markov branching trees to a parametric family of distributions on fragmentation trees that satisfies a generalized Markov branching property. The main theorems establish important statistical properties of this model, specifically necessary and sufficient conditions under which a family of trees can be constructed consistently as sample size grows. We also consider the question of attaching random edge lengths to these trees.