Doob-Martin boundary of Rémy's tree growth chain

DOI10.1214/16-AOP1112MaRDI QIDQ516121zbMATH OpenFDO

Authors Steven Neil Evans, Rudolf Grübel, Anton Wakolbinger

Publication date 22 March 2017

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2526, https://projecteuclid.org/euclid.aop/1485421333

zbMATH Keywords

Doob-Martin boundaryRémy's tree

Mathematics Subject Classification ID

Exchangeability for stochastic processes (60G09) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Boundary theory for Markov processes (60J50) Analysis of algorithms (68W40)

Abstract: R'emy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the $n^{mathrmth}$ tree is uniformly distributed over the set of rooted, planar, binary trees with $2n+1$ vertices. We obtain a concrete characterization of the Doob--Martin boundary of this transient Markov chain and thereby delineate all the ways in which, loosely speaking, this process can be conditioned to "go to infinity" at large times. A (deterministic) sequence of finite rooted, planar, binary trees converges to a point in the boundary if for each $m$ the random rooted, planar, binary tree spanned by $m+1$ leaves chosen uniformly at random from the $n^{mathrmth}$ tree in the sequence converges in distribution as $n$ tends to infinity -- a notion of convergence that is analogous to one that appears in the recently developed theory of graph limits. We show that a point in the Doob--Martin boundary may be identified with the following ensemble of objects: a complete separable $mathbbR$-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the $mathbbR$-tree that allows us to make sense of sampling points from it, and a kernel on the $mathbbR$-tree that describes the probability that the first of a given pair of points is below and to the left of their most recent common ancestor while the second is below and to the right. The Doob--Martin boundary corresponds bijectively to the set of extreme points of the closed convex set of normalized nonnegative harmonic functions, in other words, the minimal and full Doob--Martin boundaries coincide. These results are in the spirit of the identification of graphons as limit objects in the theory of graph limits.

Review text

The present paper is an extended study of the Doob-Martin boundary of \textit{J.-L. Rémy}'s tree growth chain [RAIRO, Inf. Théor. 19, 179--195 (1985; Zbl 0565.05037)] in the spirit of the identification of graphons as limit objects in the theory of graph limits. Rémy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a manner that the \(n\)th tree is uniformly distributed over the set of rooted, planar binary trees with \(2n+1\) vertices.

Recommendations

• Random recursive trees: a boundary theory approach
• Rayleigh processes, real trees, and root growth with re-grafting
• The continuum random tree. I
• Scaling limits of k-ary growing trees
• Scaling limits for some random trees constructed inhomogeneously

Cited in

(13)

• A representation of exchangeable hierarchies by sampling from random real trees
• A representation for exchangeable coalescent trees and generalized tree-valued Fleming-Viot processes
• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• The Aldous chain on cladograms in the diffusion limit
• Doeblin trees
• Doob-Martin compactification of a Markov chain for growing random words sequentially
• Growing random uniform d-ary trees
• Trickle-down processes and their boundaries
• Noncommutative boundaries arising in dynamics and representations of the Cuntz relations
• Spaces of algebraic measure trees and triangulations of the circle
• Models of random subtrees of a graph
• Continuum asymptotics for tree growth models with uniform backward dynamics
• Exchangeable interval hypergraphs and limits of ordered discrete structures

This page was built for publication: Doob-Martin boundary of Rémy's tree growth chain

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