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

DOI10.1002/RSA.20930MaRDI QIDQ5136932zbMATH OpenOpenAlexFDO

Authors Soumik Pal, Douglas Rizzolo, Matthias Winkel, Noah Mills Forman

Publication date 30 November 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.00862

zbMATH Keywords

Aldous diffusiondown-up chainintertwiningMarkov chains on binary treesRémy tree growthstrings of beadstrees with edge-weights

Mathematics Subject Classification ID

Trees (05C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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 $1lek<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 $klen$. 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 $nightarrowinfty$ continuum analogue of the Aldous chain and will be taken up elsewhere. Some of our results have been generalized to Ford's alpha model trees.

Recommendations

• The Aldous chain on cladograms in the diffusion limit
• Rayleigh processes, real trees, and root growth with re-grafting
• The continuum random tree. I
• The continuum random tree. III
• On a result of David Aldous concerning the trees in a conditioned excursion

Cited in

(5)

• Diffusions on a space of interval partitions: Poisson-Dirichlet stationary distributions
• The leftmost column of ordered Chinese restaurant process up-down chains: intertwining and convergence
• Diffusive limits of two-parameter ordered Chinese restaurant process up-down chains
• A down‐up chain with persistent labels on multifurcating trees
• Where do (random) trees grow leaves?

This page was built for publication: Projections of the Aldous chain on binary trees: intertwining and consistency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136932)