Mixing Time for a Markov Chain on Cladograms

Source abstract

A cladogram is a tree with labelled leaves and unlabelled 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 re-attaching 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 ).