Random walks on trees and matchings

By Persi Diaconis, Susan P. Holmes. 2002

62 citations recorded by the source corpus.

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 $(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.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b496dc8ffa00329089b38058acaa23fe1268fd21

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Bootstrapping Phylogenetic Trees: Theory and Methods (2003, background): “Diaconis and Holmes (1998, 2002) showed that the space of all combinatorial trees on n leaves T n can be represented as the quotient of the symmetric group on 2(n − 1) by the subgroup B 2(n−1) that leaves the pairs This is called the matching representation of trees, where the tree is replaced by…”
SUBTREE PRUNE AND REGRAFT: A REVERSIBLE REAL TREE-VALUED MARKOV PROCESS (2005, background): “Chains based on other moves are investigated in [5, 14, 29].”
On fixed points of permutations (2007, background): “Connections with phylogenetic trees and further references are in [DH1, DH2 ].”