Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Mixing Time for a Markov Chain on Cladograms

Published Web Location

https://doi.org/10.1017/s096354830000417x
Abstract

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).

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View


Top