Mixing time for a Markov chain on cladograms

被引：25

作者：

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 [J].

ALDOUS, D ;

DIACONIS, P .

AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) :333-348

[2] RECURSIVE SELF-SIMILARITY FOR RANDOM TREES, RANDOM TRIANGULATIONS AND BROWNIAN EXCURSION [J].

ALDOUS, D .

ANNALS OF PROBABILITY, 1994, 22 (02) :527-545

[3] THE CONTINUUM RANDOM TREE-III [J].

ALDOUS, D .

ANNALS OF PROBABILITY, 1993, 21 (01) :248-289

[4] SOME INEQUALITIES FOR REVERSIBLE MARKOV-CHAINS [J].

ALDOUS, DJ .

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 →