Mixing Time for a Random Walk on Rooted Trees

Abstract

We define an analog of Plancherel measure for the set of rooted unlabeled trees on $n$ vertices, and a Markov chain which has this measure as its stationary distribution. Using the combinatorics of commutation relations, we show that order $n^2$ steps are necessary and suffice for convergence to the stationary distribution.