zbMATH — the first resource for mathematics

Random walks on trees and matchings. (English) Zbl 1007.60071
Summary: We give sharp rates of convergence for a natural Markov chain on the space of phylogenetic trees and dually for the natural random walk on the set of perfect matchings in the complete graph on $$2n$$ vertices. Roughly, the results show that $$\frac {1}2 n \log n$$ steps are necessary and suffice to achieve randomness. The proof depends on the representation theory of the symmetric group and a bijection between trees and matchings.

MSC:
 60J10 Markov chains (discrete-time Markov processes on discrete state spaces) 60B15 Probability measures on groups or semigroups, Fourier transforms, factorization 62F10 Point estimation 62F15 Bayesian inference 65C05 Monte Carlo methods 82C80 Numerical methods of time-dependent statistical mechanics (MSC2010)
Full Text: