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

DOI10.1214/16-AOP1112zbMATH Open1387.60119arXiv1411.2526MaRDI QIDQ516121FDOQ516121

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)

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.

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

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

zbMATH Keywords

Doob-Martin boundaryRémy's tree

Mathematics Subject Classification ID

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

Cited In (12)

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

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)