Paperlane

no. 8 · Wednesday 4 November 2026

The Aldous chain on cladograms mixes in order $n^2$ steps

Valentin Féray and Lucas Teyssier

math.PR · v2 · 12 pp

Abstract

Cladograms of size $n$ are unrooted binary trees whose leaves are labelled from 1 to $n$. Aldous introduced in 2000 a Markov chain on cladograms, a step of which consists of removing a leaf uniformly at random and reinserting it on a uniformly chosen edge. We introduce a coupling for this walk, which follows multiple colored subtrees in parallel. We go around the lack of independence of the colored components by finding a relevant statistic, namely the sum of the squares of the sizes of all colored components, which we prove has a drift. We deduce that the mixing time of the walk is of order $n^2$, solving a conjecture of Aldous.

comments
12 pages, 6 figures, comments welcome!
fields
Probability, Combinatorics
pdf ↗ page arXiv:2609.16955 ↗