Phylogenetic trees are commonly used to model the evolutionary relationships among a
collection of biological species. Over the past fifteen years, the convergence properties for
Markov chains defined on phylogenetic trees have been studied, yielding results about the
time required for such chains to converge to their stationary distributions. In this work we
derive an upper bound on the relaxation time of two Markov chains on rooted binary trees:
one defined by nearest neighbor interchanges (NNI) and the other defined by subtree prune …