Title: Mixing Time for a Markov Chain on Cladograms
Author: David J. Aldous
A cladogram is a tree with labeled leaves and unlabeled
degree-3 branchpoints.
A certain Markov chain on the set of $n$-leaf cladograms
consists of removing a random leaf (and its incident edge)
and reattaching it to a random edge.
We show that the mixing time (time to approach the uniform
stationary distribution) for this chain is at least $O(n^2)$ and at most
$O(n^3)$.