An O(n 2 ) bound for the relaxation time of a Markov chain on cladograms
An O(n 2 ) bound for the relaxation time of a Markov chain on cladograms
复制标题
分支图上马尔可夫链弛豫时间的 O(n 2 ) 界限
DOI：
10.1002/rsa.10000
复制
发表时间：
2002
影响因子：
1
通讯作者：
Jason Schweinsberg
中科院分区：
文献类型：
--
作者：
Jason Schweinsberg
一个分支图是一个无根树，有标记的叶子和未标记的3度内部分支点。奥尔德斯研究了一个在n叶分支图集合上的马尔可夫链，其中每个转移都包括从树中删除一个随机的叶子及其关联边，然后将叶子重新连接到剩余树的随机边。使用耦合方法，Aldous表明弛豫时间（即，对于这个链，谱间隙的倒数）是O（n3）。在这里，我们使用的方法的基础上区分路径证明了O（n2）界的弛豫时间，建立一个猜想Aldous。
A cladogram is an unrooted tree with labeled leaves and unlabeled internal branchpoints of degree 3. Aldous has studied a Markov chain on the set of n-leaf cladograms in which each transition consists of removing a random leaf and its incident edge from the tree and then reattaching the leaf to a random edge of the remaining tree. Using coupling methods, Aldous showed that the relaxation time (i.e., the inverse of the spectral gap) for this chain is O(n3). Here, we use a method based on distinguished paths to prove an O(n2) bound for the relaxation time, establishing a conjecture of Aldous.