Mixing time for a Markov chain on cladograms

被引：24

作者：

Aldous, DJ ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2000年 / 9卷 / 03期

关键词：

D O I：

10.1017/S096354830000417X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A cladogram is a tree with labelled leaves and unlabelled degree-3 branchpoints. A certain Markov chain on the set of n-leaf cladograms consists of removing a random leaf (and its incident edge) and re-attaching it to a random edge. We show that the mixing time (time to approach the uniform stationary distribution) for this chain is at least O(n(2)) and at most O(n(3)).

引用

页码：191 / 204

页数：14

共 21 条

[1] SHUFFLING CARDS AND STOPPING-TIMES
ALDOUS, D
DIACONIS, P
[J]. AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) : 333 - 348
[2] RECURSIVE SELF-SIMILARITY FOR RANDOM TREES, RANDOM TRIANGULATIONS AND BROWNIAN EXCURSION
ALDOUS, D
[J]. ANNALS OF PROBABILITY, 1994, 22 (02) : 527 - 545
[3] THE CONTINUUM RANDOM TREE-III
ALDOUS, D
[J]. ANNALS OF PROBABILITY, 1993, 21 (01) : 248 - 289
[4] SOME INEQUALITIES FOR REVERSIBLE MARKOV-CHAINS
ALDOUS, DJ
[J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1982, 25 (JUN): : 564 - 576
[5] [Anonymous], REVERSIBLE MARKOV CH
[6] [Anonymous], 1992, Combinatorics, Probability Computing
[7] BARKER D, LVB 1 0 RECONSTRUCTI
[8] Bayer D., 1992, Ann. Appl. Probab, V2, P294, DOI [10.1214/aoap/1177005705, DOI 10.1214/AOAP/1177005705]
[9] CHARLESTON MA, LANDSCAPE CHARACTERI
[10] Diaconis P., 1991, Ann. Appl. Probab., P36

← 1 2 3 →