×

Mixing time for a random walk on rooted trees. (English) Zbl 1206.05092

Summary: 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.

MSC:

05C81 Random walks on graphs
05C05 Trees
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS