TY - JOUR

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

AU - Evans, Steven N.

AU - Grübel, Rudolf

AU - Wakolbinger, Anton

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2017.

PY - 2017/1

Y1 - 2017/1

N2 - Rémy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the nth 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 nth 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 ℝ-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the R-tree that allows us to make sense of sampling points from it, and a kernel on the R-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. Two such ensembles represent the same point in the boundary if for each m the random, rooted, planar, binary trees spanned by m + 1 independent points chosen according to the respective probability measures have the same distribution. Also, the Doob-Martin boundary corresponds bijectively to the set of extreme point of the closed convex set of nonnegative harmonic functions that take the value 1 at the binary tree with 3 vertices; 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.

AB - Rémy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the nth 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 nth 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 ℝ-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the R-tree that allows us to make sense of sampling points from it, and a kernel on the R-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. Two such ensembles represent the same point in the boundary if for each m the random, rooted, planar, binary trees spanned by m + 1 independent points chosen according to the respective probability measures have the same distribution. Also, the Doob-Martin boundary corresponds bijectively to the set of extreme point of the closed convex set of nonnegative harmonic functions that take the value 1 at the binary tree with 3 vertices; 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.

KW - Binary tree

KW - Bridge

KW - Catalan number

KW - Continuum random tree

KW - Doob-Martin compactification

KW - Exchangeability

KW - Graph limit

KW - Graphon

KW - Partial order

KW - Poisson boundary

KW - Real tree

KW - Tail σ-field

UR - http://www.scopus.com/inward/record.url?scp=85011290538&partnerID=8YFLogxK

U2 - 10.48550/arXiv.1411.2526

DO - 10.48550/arXiv.1411.2526

M3 - Article

AN - SCOPUS:85011290538

VL - 45

SP - 225

EP - 277

JO - Annals of Probability

JF - Annals of Probability

SN - 0091-1798

IS - 1

ER -