Skip to content
DraconiticResearch
Search Sources API
197,761 studies31 sourcesUpdated 41 min ago
PreprintCC0HAL

The Aldous chain on cladograms mixes in order n2 steps

  • Valentin Féray
  • Lucas Teyssier
Open at sourcePDFDOICite

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 n2, solving a conjecture of Aldous.

Related

  1. Kac's Walk on Rotation Matrices Mixes in Θ(n2) Steps: A Proof Discovered with AI
    Tianle Liu
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous-Broder Theorem
    Hugh Zheng
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  3. Second-Order Steps, Spectral Accuracy: Discrete Parallel Transport of Invariant Subspaces
    Hanwen Zhang
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
  4. AdHImEx: Adaptively High-Order Implicit-Explicit Transport for Large Time Steps
    Amber J. te Winkel, Hilary Weller, Christian Kühnlein +1
    arXivPreprintCC BY-NC-ND 4.0Full textNumerical analysis & scientific computingComputational physicsarXiv
  5. GORENSTEIN FANO POLYTOPES ARISING FROM ORDER POLYTOPES AND CHAIN POLYTOPES
    Takayuki Hibi, Kazunori Matsuda, Akiyoshi Tsuchiya
    Journal of Commutative AlgebraPeer-reviewedLicence not statedFull text13 citedCombinatorics & discrete mathematicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{feray2026aldous,
  title = {{The Aldous chain on cladograms mixes in order $n^2$ steps}},
  author = {Valentin Féray and Lucas Teyssier},
  howpublished = {HAL},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16955},
  eprint = {2609.16955},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05772585v1},
  note = {CC0},
}
RIS
TY  - UNPB
TI  - The Aldous chain on cladograms mixes in order n^2 steps
AU  - Valentin Féray
AU  - Lucas Teyssier
PY  - 2026
DA  - 2026/09/15
PB  - HAL
DO  - 10.48550/arxiv.2609.16955
UR  - https://hal.science/hal-05772585v1
AB  - 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.
ER  -