A sharp analysis of the mixing time for random walk on rooted trees
arXiv:0908.1141
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.
13 pages
References in corpus (5)
- Hopf Algebras, Renormalization and Noncommutative Geometry
- Hopf algebras, cyclic cohomology and the transverse index theory
- Separation cut-offs for birth and death chains
- Infinite-dimensional diffusions as limits of random walks on partitions
- A Two-Parameter Family of Infinite-Dimensional Diffusions in the Kingman Simplex