×

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)
PDFBibTeX XMLCite
Full Text: DOI EuDML