Diaconis, Persi; Holmes, Susan Random walks on trees and matchings. (English) Zbl 1007.60071 Electron. J. Probab. 7, Paper No. 6, 17 p. (2002). 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. Cited in 1 ReviewCited in 23 Documents 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) Keywords:Markov chain; matchings; phylogenetic tree; Fourier analysis; zonal polynomials; coagulation-fragmentation PDFBibTeX XMLCite \textit{P. Diaconis} and \textit{S. Holmes}, Electron. J. Probab. 7, Paper No. 6, 17 p. (2002; Zbl 1007.60071) Full Text: DOI EuDML