Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-11T06:37:02.187Z Has data issue: false hasContentIssue false
  • English
  • Français

Mixing Time for a Markov Chain on Cladograms

Published online by Cambridge University Press:  01 May 2000

DAVID J. ALDOUS
DAVID J. ALDOUS
Affiliation:
University of California, Department of Statistics, 367 Evans Hall # 3860, Berkeley CA 94720-3860, USA (e-mail: aldous@stat.berkeley.edu, http://www.stat.berkeley.edu/users/aldous)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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(n2) and at most O(n3).

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 3 , May 2000 , pp. 191 - 204
Copyright
2000 Cambridge University Press