An O(n2) bound for the relaxation time of a Markov chain on cladograms
An O(n2) bound for the relaxation time of a Markov chain on cladograms
复制标题
分支图上马尔可夫链弛豫时间的 O(n2) 界限
DOI：
10.1002/rsa.1029
复制
发表时间：
2002
影响因子：
1
通讯作者：
Jason Schweinsberg
中科院分区：
文献类型：
--
作者：
Jason Schweinsberg
一个梯形图是一个无根的树，有标记的叶子和未标记的3度内部分支点。Aldous研究了n叶形图集合上的马尔可夫链，其中每次转移都包括从树中移除随机的叶子及其关联边，然后将叶子重新连接到剩余树的随机边上。通过耦合方法，Aldous证明了该链的弛豫时间（即谱隙的倒数）为O（n3）。在这里，我们使用基于区分路径的方法证明了松弛时间的O（n2）界，建立了Aldous猜想。©2002 John Wiley & Sons, Inc. Random structure。Alg。， 20, 59-70, 2002
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. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 59–70, 2002