Projections of the Aldous chain on binary trees: Intertwining and consistency. Issue 3 (23rd May 2020)

• Record Type: Journal Article
• Authors: Forman, Noah; Pal, Soumik; Rizzolo, Douglas; Winkel, Matthias
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 745
• Page End: 769
• Publication Date: 2020-05-23
• Subjects: Aldous diffusion -- down‐up chain -- intertwining -- Markov chains on binary trees -- Rémy tree growth -- strings of beads -- trees with edge‐weights; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20930
• Languages: English
• ISSNs: 1042-9832

Abstract

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.