Projections of the Aldous chain on binary trees: Intertwining and consistency

Abstract

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k < n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k ‐tree with total mass n .” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k ‐trees evolve as Markov chains themselves, and are projectively consistent over k . The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n → ∞ continuum analog of the Aldous chain and will be taken up elsewhere.

Locations

• arXiv (Cornell University) - View - PDF
• Oxford University Research Archive (ORA) (University of Oxford) - View - PDF
• Random Structures and Algorithms - View - PDF