# Continuum asymptotics for tree growth models

David Geldbach

###### Abstract

We classify the forward dynamics of all (plane) tree-valued Markov chains
$(T_{n},n\geq 1)$ with uniform backward dynamics. Every such Markov chain is
classified by a decorated planar real tree. We also show that under an
inhomogeneous rescaling after trimming leaves $(T_{n},n\geq 1)$ converges to a
random real tree in the Gromov–Prokhorov metric. This generalises and sheds
some new light on work by Evans, Grübel and Wakolbinger (2017) on the binary
special case.

##  1 Introduction

We study tree–valued Markov chains $(T_{n},n\geq 1)$ where $T_{n}$ is a plane
tree with $n$ leaves, a root $r_{n}$ and no vertices with degree $2$. We
consider a broad class of such tree–valued Markov chains. We do not make any
assumptions of the forward dynamics, we only assume that $(T_{n},n\geq 1)$ has
_uniform backward dynamics_ , see also Figure 1 for an illustration.

######  Definition 1.1.

The Markov chain $(T_{n},n\geq 1)$ is said to have _uniform backward dynamics_
if for all $n\geq 2$ the following procedure yields a tree with the same
distribution as $T_{n-1}$.

  1. 1.)

Choose a leaf uniformly of $T_{n}$,

  2. 2.)

remove this leaf and its associated edge,

  3. 3.)

remove any vertex with degree $2$ and replace it and its two edges by a single
edge.

Figure 1: An example for the uniform backward dynamics. The red circle
indicates which leaf has been uniformly chosen.

The goal of this article is to classify all tree–valued Markov chains with
uniform backward dynamics. We want to understand the different possible
forward dynamics. We use the classification of forward dynamics to show a
scaling limit. Another viewpoint is that we characterise the _Doob–Martin_
boundary of these Markov chains. This is the goal of Evans, Grübel and
Wakolbinger [8], they characterise the Doob–Martin boundary of Rémy’s tree
growth chain which corresponds to the special case of binary trees. We comment
on the relation to their work in Remark 1.11.

One well–studied one–parameter family of Markov chains that has uniform
backward dynamics is Marchal’s tree growth $(T_{n}^{M}(\alpha),n\geq 1)$ with
$\alpha\in(1,2]$. We construct $T_{n+1}^{M}(\alpha)$ recursively from
$T_{n}^{M}(\alpha)$:

  1. 1.)

Assign weight $\alpha-1$ to each edge of $T_{n}^{M}(\alpha)$ and weight
$k-1-\alpha$ to each branchpoint of $T_{n}^{M}(\alpha)$ with degree $k\geq 3$.
Choose an edge or a branchpoint according to these weights.

  2. 2.)

If an edge $e$ has been chosen, split it into two edges $e_{1},e_{2}$ and
attach a new leaf to the new vertex.

  3. 3.)

If a branchpoint $v$ has been chosen, attach a new leaf to this branchpoint.

  4. 4.)

The new planar order of $T_{n+1}^{M}(\alpha)$ is chosen uniformly at random,
consistently with the planar order of $T_{n}^{M}(\alpha)$.

This has been introduced by Marchal [19] and generalises Rémy’s tree growth
[20] which only grows binary trees, here $\alpha=2$. The fact that the
backward dynamics of Marchal’s tree growth are uniform goes back to Haas,
Miermont, Pitman and Winkel [15].

|
---|---
Figure 2: A realisation of Marchal’s tree growth after $25000$ growth steps
for different values for $\alpha=2$ (left) and $\alpha=1.4$ (right). These
trees approximate the Brownian continuum random tree (left) and the
$1.4$–stable tree (right).

The uniform backward dynamics have an interesting consequence if we want to
condition the Markov chain: let $T$ be a tree such that the event
$\\{T_{n+m}=T\\}$ has positive probability for $n,m\geq 1$. Consider a
conditional distribution of the form

$\mathbb{P}\big{(}T_{m}\in\cdot\big{|}T_{n+m}=T\big{)}.$ (1.1)

We then have a very explicit way of describing the distribution of
$T_{m}^{M}$: we just need to choose $n-m$ distinct uniform leaves of $T$,
remove them iteratively and any vertices of degree $2$ that turn up in the
process of removing leaves. There is another interesting property of Marchal’s
tree growth chain. Let $d^{gr}_{n}$ be the graph metric on $T_{n}^{M}(\alpha)$
and $d_{n}=n^{-1+1/\alpha}d_{n}^{gr}$, a rescaled metric where every edge has
length $n^{-1+1/\alpha}$. Consider $(T_{n}^{M}(\alpha),d_{n})$ as a random
metric space, then there exists a random metric space
$(\mathcal{T}_{\alpha},d_{\alpha})$ such that

$(T_{n}^{M}(\alpha),d_{n})\xrightarrow{a.s.}(\mathcal{T}_{\alpha},d_{\alpha}),$
(1.2)

in the Gromov-Hausdorff-Prokhorov topology, for details we refer to the
literature. The statement in this form goes back to Curien and Haas [4,
Theorem 5]; related statements are [15, Corollary 24], [19, Theorem 3.2] and
[5, Theorem 3.3.3]. The metric space $(\mathcal{T}_{\alpha},d_{\alpha})$ is a
(random) real tree, we require these to be rooted.

######  Definition 1.2 (Real trees).

A real tree ($\mathbb{R}$–tree) is a complete, separable metric space
$(\textbf{T},d_{\textbf{T}})$ with the property that for each
$x,y\in\textbf{T}$, there is a unique non–self–intersecting path from $x$ to
$y$, denoted by $[x,y]_{\textbf{T}}$. This path is isometric to a closed real
interval. We require T to have a marked point $r\in\textbf{T}$ which we call
its root.

A prominent example of a random real tree is the Brownian continuum random
tree introduced by Aldous [1, 2]. This was later generalised by Duquesne and
Le Gall [5] to a family of stable trees $(\mathcal{T}_{\alpha},1<\alpha\leq
2)$ with $\mathcal{T}_{2}$ being the Brownian continuum random tree. For an
introduction to real trees, see for example the book by Evans [7]. Often we
leave the metric $d_{\textbf{T}}$ implicit. Further, if the tree T is clear
from the context, we write $d$ instead of $d_{\textbf{T}}$. Similarly, we
often write $[x,y]$ instead of $[x,y]_{\textbf{T}}$ for the path between two
points. We also want to make precise what we mean when we speak of subtrees.

######  Definition 1.3 (Real subtrees).

Let $(\textbf{T},r)$ be a real tree. Given $x\in\textbf{T}$, we define two
notions of subtrees:

  1. 1.)

The _fringe subtree_ rooted at $x$ is

$F_{\textbf{T}}(x)=\big{\\{}y\in\textbf{T}\mathrel{\mathop{\mathchar
58\relax}}x\in[r,y]_{\textbf{T}}\big{\\}}.$

  2. 2.)

The _subtrees of_ $x$ are the connected components of
$F_{\textbf{T}}(x)\backslash\\{x\\}$. To each of them, we add $x$ and root
them at $x$.

Note that if $x\neq r$, then $r\notin F_{\textbf{T}}(x)$ and $r$ is not
contained in any subtree of $x$.

We also consider a special class of real trees, so called interval partition
trees (IP–trees), introduced by Forman [9]. There, distances in the real tree
relate to masses of a probability measure $\mu$. When we want to stress the
fact that if a real tree T has an associated probability measure $\mu$ defined
on the Borel $\sigma$–algebra, we speak of a _weighted real tree_. We denote
by $\textrm{supp}(\mu)$ the closed support of $\mu$.

######  Definition 1.4 (IP–tree).

A rooted, weighted real tree $(\textbf{T},d,r,\mu)$ is an interval–partition
tree if it possesses the following properties.

  1. 1.)

Spanning. Every leaf is in the support of $\mu$, i.e.
$\textbf{T}=\textrm{span}(\textrm{supp}(\mu))$.

  2. 2.)

Spacing. For $x\in\textbf{T}$, if $x$ is either a branch point or lies in the
support of $\mu$, then

$d(r,x)+\mu(F_{\textbf{T}}(x))=1.$ (1.3)

######  Remark 1.5.

The name originates from a so–called bead crushing construction of IP–trees,
see Forman [9]. There, they consider a leaf $x\in\textbf{T}$ and project $\mu$
onto the interval $[r,x]$ – this gives rise to an interval partition. The
masses of the blocks are given by $\mu(F_{\textbf{T}}(y))-\mu(\textbf{S}_{y})$
for $y\in[r,x]$ and where $\textbf{S}_{y}$ is the subtree of $y$ containing
$x$. We will not use these interval partitions.

To construct forward dynamics of $(T_{n},n\geq 1)$, we need to endow real
trees with additional structure. In particular we introduce a notion of
planarity for real trees as well as decorating functions.

For a real tree $(\textbf{T},d,r)$ we call a family of maps
$\psi=(\psi_{n},n\geq 2)$ a _planar order_ for T if $\psi_{n}$ maps a tuple
$(x_{1},\ldots,x_{n})\in\textbf{T}^{n}$ to a combinatorial, partially
labelled, plane tree consistently when going from $\psi_{n}$ to $\psi_{n+1}$.
We specify the details of this definition and the consistency relations of
$\psi$ in Definition 2.2. Most importantly, we require
$\psi_{n}(x_{1},\ldots,x_{n})$ to be the combinatorial tree corresponding to
$\textrm{span}(x_{1},\ldots,x_{n})$ as non–plane trees for every
$(x_{1},\ldots,x_{n})\in\textbf{T}^{n}$. If $\textbf{S}_{1}$ and
$\textbf{S}_{2}$ are both subtrees of $x\in\textbf{T}$, we say that
$\textbf{S}_{1}$ is to the left of $\textbf{S}_{2}$ if for two arbitrary
points
$y_{1}\in\textbf{S}_{1}\backslash\\{x\\},y_{2}\in\textbf{S}_{2}\backslash\\{x\\}$
the image of $y_{1}$ is to the left of $y_{2}$ in $\psi_{2}(y_{1},y_{2})$ –
see Definition 2.5.

Next, assume that $(\textbf{T},d,r)$ is equipped with a probability measure
$\mu$. Decompose $\mu=\mu_{atoms}+\mu_{s}+\mu_{\ell}$ where $\mu_{atoms}$ is
supported on the atoms of $\mu$, $\mu_{s}$ is supported diffusely on
$\textbf{T}\backslash\\{\text{leaves}\\}$ and $\mu_{\ell}$ is supported
diffusely on the leaves of T. We can choose the supports of
$\mu_{atoms},\mu_{s},\mu_{\ell}$ to be disjoint. Further, we can choose
$supp(\mu_{s})$ in such a way that for every $x\in\ supp(\mu_{s})$ we have
$\deg(x)=2$.

We then call a measurable function $\lambda\mathrel{\mathop{\mathchar
58\relax}}\textbf{T}\rightarrow[0,1]$ a _branch weight function_ when viewed
as an element of $L^{1}(\mu_{s})$. We call $B$ a _branchpoint weight function_
if $B$ maps every element $a$ of $supp\ \mu_{atoms}$ to a function
$\beta_{a}\mathrel{\mathop{\mathchar 58\relax}}[0,1]\to[0,1]$ – note that
$supp\ \mu_{atoms}$ is an at most countable set. For each $a\in\
supp(\mu_{atoms})$, we require that $\beta_{a}$ is non–decreasing,
right–continuous and the cardinality of the range of $\beta_{a}$ is at most
$\deg a$. The degree $\deg a$ is defined as the number of connected components
of $\textbf{T}\backslash\\{a\\}$. Also, we want $\beta_{a}$ to be piece–wise
constant in the following sense. First, enumerate the connected components of
$F_{\textbf{T}}(a)\backslash\\{a\\}$ by
$\textbf{S}_{1},\textbf{S}_{2},\ldots$: we require that
$\mu(\textbf{S}_{1})\geq\mu(\textbf{S}_{2})\geq\ldots$ – if two subtrees have
the same mass, then we enumerate them in such a way that for $i<j$,
$\textbf{S}_{i}$ is to the left of $\textbf{S}_{j}$. We implicitly include the
case that there are only finitely many subtrees.

Secondly, let $c_{i}=\sum\mu(\textbf{S}_{j})/\sum_{k\geq
1}\mu(\textbf{S}_{k})$ where the first sum ranges over all $j$ such that
$\textbf{S}_{j}$ is left of $\textbf{S}_{i}$ and
$\textbf{S}_{j}\neq\textbf{S}_{i}$. We then impose that $\beta_{a}$ is
constant on $[c_{i},\inf_{c_{j}>c_{i}}c_{j})$ for every $i$.

######  Definition 1.6.

We call a collection of objects $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ with the
above properties a _decorated planar real tree_. If $(\textbf{T},d,r,\mu)$ is
an IP–tree, we speak of decorated planar IP–trees.

Furthermore, we call $(\textbf{T},d,r,\psi)$ a _planar real tree_. This notion
is discussed in detail in Section 2.1. With these definitions in hand, we can
construct the forward dynamics for the tree growth process $(T_{n},n\geq 1)$.
See Figure 3 for an illustration.

Figure 3: an example for sampling $T_{13}$. First, we sample $(\xi_{i},i\leq
13)$ from T; secondly we apply $\psi_{13}$ to obtain $S_{13}$ and thirdly we
add leaves to some interior vertices (in red) to obtain $T_{13}$. In the last
step, the planar order is determined by $\lambda$ and $B$ as well as some
additional randomness. Figure 4: an illustration of how to use the branchpoint
weight function $B$ for a given atom $a$. If $U_{i}$ is between two thresholds
corresponding to two different subtrees of $a$, then we attach a leaf between
the different subtrees in the discrete tree $T_{n}$.

######  Construction 1.7.

Assume we are given a decorated planar real tree
$(\textbf{T},d,r,\mu,\psi,\lambda,B)$. To construct a plane tree $T_{n}$, we
proceed as follows:

  1. 1.)

Sample $\xi_{1},\ldots,\xi_{n}\in\textbf{T}$ $i.i.d.$ from $\mu$.

  2. 2.)

Consider the associated plane, partially labelled tree
$S_{n}=\psi_{n}(\xi_{1},\ldots,\xi_{n})$. By the properties imposed on
$\psi_{n}$, $S_{n}$ will contain $n$ vertices labelled by $[n]$, including all
leaves.

  3. 3.)

For every vertex in $S_{n}$ that is labelled but not a leaf, we attach a new
leaf to it and move the label to the new leaf. Call the combinatorial tree
obtained this way $T_{n}^{*}$. We determine the planar order of the new leaves
as follows. Suppose we have attached in $T_{n}$ a leaf labelled $i$ to the
vertex corresponding to $\xi_{i}$ in the real tree T. We need to distinguish
two cases: $\xi_{i}\in\ supp\ \mu_{atoms}$ and $\xi_{i}\in\ supp\ \mu_{s}$.

    1. (a)

If $\xi_{i}\in\ supp\ \mu_{s}$, recall that for $x\in\ supp\ \mu_{s}$ we have
$\deg(x)=2$. Let $X_{i}$ be a conditionally independent Bernoulli random
variable with parameter $\lambda(\xi_{i})$. If $X_{i}=1$, we orient the leaf
labelled $i$ to the left of the subtree of the vertex that was labelled $i$ in
$S_{n}$ and otherwise to the right.

    2. (b)

If $\xi_{i}=a\in supp\ \mu_{atoms}$, we do the following. Enumerate the
subtrees of $a$ and write $\textbf{S}_{j}<\textbf{S}_{k}$ if $\textbf{S}_{j}$
is to the left of $\textbf{S}_{k}$. Now, let $U_{i}$ be an independent $[0,1]$
uniform random variable. In the combinatorial tree $T_{n}^{*}$, we consider
the subtrees of the parent of the leaf $i$, each of these corresponds
naturally to some subtree $\textbf{S}_{j}$ in the real tree. By abuse of
notation, we now orient the leaf labelled $i$ to the left of every subtree
such that $U_{i}<\beta_{a}(\textbf{S}_{j})$ and to the right of every subtree
with $U_{i}\geq\beta_{a}(\textbf{S}_{j})$ where we write

$\beta_{a}(\textbf{S}_{j})=\beta_{a}\left(\frac{1}{Z_{a}}\sum_{k\mathrel{\mathop{\mathchar
58\relax}}\textbf{S}_{k}<\textbf{S}_{j}}\mu(\textbf{S}_{k})\right),$

with the normalising constant $Z_{a}=\sum_{k}\mu(\textbf{S}_{k}).$

    3. (c)

If we have $\xi_{i}=\xi_{j}=a\in supp\ \mu_{atoms}$, i.e. we attach two leaves
to the same branchpoint, then we reuse the uniform random variables
$U_{i},U_{j}$ of the previous step. If $U_{i}<U_{j}$ we orient the leaf
labelled $i$ to the left of the leaf $j$ and vice versa.

  4. 4.)

Delete the leaf labels to obtain a plane tree $T_{n}$.

######  Remark 1.8.

When constructing $T_{n}$ and $T_{m}$ for $n<m$, we reuse the random variables
$(\xi_{i},X_{i},U_{i};i\leq n)$ in the construction of $T_{m}$. This results
in the sequence $(T_{n},n\geq 1)$ being a tree–valued Markov chain with
uniform backward dynamics. Indeed, this is true because a backward step
corresponds to removing $\xi_{n}$ from the construction. Once the labels are
removed, this corresponds to uniformly choosing a point from
$\xi_{1},\ldots,\xi_{n}$ which in turn means choosing a leaf of $T_{n}$
uniformly.

We could keep the leaf labels in step $4.)$ to obtain a Markov chain of
labelled trees.

######  Definition 1.9.

Let $\rho_{\textbf{T}}$ denote the law of $(T_{n},n\geq 1)$ constructed from
$(\textbf{T},d,r,\mu,\psi,\lambda,B)$ by the above Construction 1.7.

We can now state our main theorem. The theorem states that the law of
$(T_{n},n\geq 1)$ can be expressed as a mixture of extremal measures which are
of the form of $\rho_{\textbf{T}}$. This is made rigorous in Section 2.3: the
measure $\nu$ in the following theorem is defined on the Doob-Martin boundary
of the Markov chain $(T_{n},n\geq 1)$. Indeed, this theorem characterises the
Doob-Martin boundary.

######  Theorem 1.10.

For every tree–valued Markov chain $(T_{n},n\geq 1)$ with uniform backward
dynamics there exists a unique probability measure $\nu$ such that

$\mathbb{P}\left((T_{n},n\geq
1)\in\cdot\right)=\int\rho_{\textbf{T}}\left((T_{n},n\geq
1)\in\cdot\right)\nu(d\textbf{T}).$ (1.4)

Here we T is an abbreviation for the decorated planar IP–tree
$(\textbf{T},d,r,\mu,\psi,\lambda,B)$.

This theorem is very similar in spirit to a long list of theorems that seek to
classify exchangeable random objects. The most classical one is de–Finetti’s
theorem that states that the distribution of every sequence of exchangeable
real random variables is a mixture of the distribution of sequences of
$i.i.d.$ random variables. Another notable one is Kingman’s paintbox theorem
that describes every exchangeable partition of $\mathbb{N}$ as a mixture of
paintboxes. The article [10] by Forman et al. also classifies a family of
exchangeable objects, hierarchies in their case, by sampling from real trees
and the work [11] of Foutel-Rodier et al. classifies various exchangeable
objects via combs which are tree–like as well. Gerstenberg [12] classifies
exchangeable interval hypergraphs, trees are a special case here, by sampling
from a random subset of $[0,1]^{2}$. See Kallenberg [17] for the classical
theorems, and in [10] there is a good list of references to similar, modern
theorems.

######  Remark 1.11.

The work [8] of Evans, Grübel and Wakolbinger forms a basis for a lot of the
ideas in this article, in particular Proposition 3.6 corresponds to their main
theorem [8, Theorem 8.2]. In their article, the authors study Rémy’s tree
growth [20] – the case of $\alpha=2$ in Marchal’s tree growth – and binary
tree-valued Markov chains with the same backwards dynamics. They place a great
emphasis on the Doob–Martin boundary of Rémy’s tree growth chain and the
topological properties of the boundary, we discuss these concepts in Section
2.3. This article extends their work as our framework allows for
multi–furcating trees instead of binary trees just like $\alpha$–stable trees
extend the Brownian continuum random tree or like Marchal’s tree growth
extends Rémy’s tree growth. Further, even in the case $\alpha=2$ we believe
that our variation of their construction is more descriptive in the form of
our decorated planar real trees.

######  Remark 1.12.

If $\mu$ is supported on the leaves of T, then $\lambda$ and $B$ are trivial.
Hence, it would suffice to specify $(\textbf{T},d,r,\mu,\psi)$ in these cases.
This in particular is almost surely the case for the Brownian continuum random
tree and $\alpha$–stable trees.

######  Example 1.13.

Assume the decorated planar real tree is given by $\textbf{T}=[0,1],r=0$, the
usual Euclidean distance $d=|\cdot|$ and with $\mu,\psi,\lambda,B$ arbitrary.
We observe:

  1. 1.)

For $(\textbf{T},d,r,\mu)$ to be an IP–tree, if $\mu(x)>0$ for $x\in[0,1]$
then $\mu((x,x+\mu(x)))=0$. Further, if for $x,y\in[0,1]$ the interval $[x,y]$
does not contain any atoms and $\mu([x,y])=y-x$, then $\mu$ restricted to
$[x,y]$ is the Lebesgue measure.

  2. 2.)

There is only one choice for $\psi$, given $n$ distinct points $\psi_{n}$ maps
them to a line graph with $n$ edges while keeping the order of labels.

  3. 3.)

Here $\lambda\mathrel{\mathop{\mathchar 58\relax}}[0,1]\to[0,1]$ is an
arbitrary function viewed as element of $L^{1}(\mu_{s})$ where $\mu_{s}$ is
the diffuse part of $\mu$. For $\xi_{i}$ in $\textrm{supp}(\mu_{s})$ we orient
the corresponding leaf in $T_{n}$ to the left with probability
$\lambda(\xi_{i})$ and to the right otherwise.

  4. 4.)

For any atom $a$, $\beta_{a}$ is determined by a single threshold
$\beta_{a}(1)\in[0,1]$. If we then sample a uniform $[0,1]$ random variable
$U_{i}$, we orient the corresponding leaf to the left if
$U_{i}\leq\beta_{a}(1)$ and to the right otherwise. If $\xi_{i}=\xi_{j}=a$ for
$i\neq j$, we orient the leaf $i$ to the left of $j$ if $U_{i}<U_{j}$ and to
the right otherwise.

Let us construct $T_{n}$ in this case: after sampling $n$ points from T and
applying $\psi_{n}$ we receive a line graph of length $k\leq n$ where $k$ is
the number of distinct points sampled. To every vertex of the line graph – the
spine of $T_{n}$ – except for the two endpoints we attach a one or multiple
leaves. For every leaf corresponding to a point $x\in\textrm{supp}(\mu_{s})$
we flip a coin with parameter $\lambda(x)$ to decide if we attach to the left
or to the right of the spine. Similarly, we flip a coin with parameter
$\beta_{a}(1)$ for every leaf attached to an atom $a$ to decide if we attach
the leaf on the left or on the right. This results in $(T_{n},n\geq 1)$ being
a sequence of growing spines with leaves hanging off on the sides, see Figure
5 for an illustration.

Figure 5: an example for $T_{11}$ if $\textbf{T}=[0,1]$. The red crosses stand
for $(\xi_{i},i\leq 11)$. The red number next to them states the outcome of
the coin-flip that determines if the leaf is attached left or right of the
spine. The blue circle indicates an atom $a$. Here, we have $\beta_{a}(1)=1/2$
which means that if $U_{i}>1/2$ (in red), we orient the corresponding leaf to
the right and to the left otherwise.

######  Example 1.14.

This is the main object of study of [6]: Let $\ell\in\mathbb{N},\ell\geq 2$
and consider $S_{n}^{\ell}$ to be the $\ell$–ary plane tree of height $n$,
here every vertex has $\ell$ offspring. Turn $S_{n}^{\ell}$ into a real tree
$\textbf{S}_{n}^{\ell}$ by assigning intervals of length $2^{-k}$ to the edges
at distance $k$ to the root, gluing them at the branchpoints. Let
$\textbf{T}^{\ell}$ be the completion of $\bigcup_{n\geq
1}\textbf{S}_{n}^{\ell}$. Consider now any diffuse probability measure $\mu$
on the leaves of $\textbf{T}^{\ell}$, [9, Theorem 1.5] states that there
exists a choice of metric $d_{\mu}$ on $\textbf{T}^{\ell}$ that renders
$(\textbf{T}^{\ell},d_{\mu},r,\mu)$ an IP–tree. Note that $\mu$ can be thought
of as a distribution on $[0,1]$ by considering $\ell$–adic expansions. Because
$(S_{n}^{\ell},n\geq 1)$ are plane trees, this induces a natural choice of
planar order for $(\textbf{S}_{n}^{\ell},n\geq 1)$ which induces maps
$(\psi_{n},n\geq 1)$ for $\textbf{T}^{\ell}$.

This corresponding Markov chain is also called the PATRICIA chain, see [6] for
a study of this in the case of binary trees. PATRICIA stands for _"practical
algorithm to retrieve information coded in alphanumeric"_. Given
$z_{1},\ldots,z_{n}\in\\{0,\ldots,\ell-1\\}^{\infty}$, words of infinite
length in the alphabet $\\{0,\ldots,\ell-1\\}$, we can construct words
$y_{i},i\leq n,$ of finite length such that $y_{i}$ is an initial segment of
$z_{i}$ for all $i\leq n$, all $y_{i}$ are distinct and that
$y_{1},\ldots,y_{n}$ are the minimal length words with this property. These
$y_{1},\ldots,y_{n}$ form a tree with $n$ leaves, the so–called radix sort
tree. Consider now $\mu$ as measure on $\\{0,\ldots,\ell-1\\}^{\infty}$ and
let $Z_{1},\ldots,Z_{n}$ be $i.i.d.$ $\mu$–samples. Then $T_{n}$ is the radix
sort tree corresponding to $Z_{1},\ldots,Z_{n}$. See Figure 6 for an
illustration.

Figure 6: an example for $T_{9}$ if $\textbf{T}^{3}$ is a $3$–ary tree. The
red crosses stand for $(\xi_{i},i\leq 9)$, sampled from the leaves of
$\textbf{T}^{3}$.

Recall from (1.2) that Marchal’s tree growth, once properly rescaled,
converges to a random real tree. We show that the same is true for any
tree–valued Markov chain with uniform backward dynamics but we need to change
the rescaling and the topology. We use the Gromov–Prokhorov topology. It was
introduced by Gromov [13], see also the survey by Janson [16].

######  Definition 1.15.

Let $(\textbf{T}_{1},d_{1},r_{1},\mu_{1})$ and
$(\textbf{T}_{2},d_{2},r_{2},\mu_{2})$ be two IP–trees. The Gromov–Prokhorov
distance $d_{\text{GP}}(\textbf{T}_{1},\textbf{T}_{2})$ is the infimum of
$\varepsilon>0$ such that exists a measurable subset
$R\subseteq\textbf{T}_{1}\times\textbf{T}_{2}$ and a coupling $\nu$ of
$\mu_{1}$ and $\mu_{2}$, such that

$\displaystyle\nu(R)\geq
1-\varepsilon\quad\text{and}\quad\sup_{(x,y),(x^{\prime},y^{\prime})\in
R}|d_{1}(x,x^{\prime})-d_{2}(y,y^{\prime})|\leq\varepsilon.$

The map $d_{\text{GP}}$ is indeed a metric on isometry classes of weighted,
complete, separable metric spaces. Further, we want to note that the induced
topology is Polish, see [16, Theorem 3.9]. The induced topology is sometimes
also called Gromov–weak topology and has an alternative formulation using
sampling test–functions, more on this can be found in Athreya et al. [3].

Figure 7: an example of the trimming and rescaling. On the left, there is
$T_{13}$; in the middle is $T_{13}^{trim}$ with a number $k$ indicating an
atom of weight $k/13$ and on the right $T_{13}^{trim}$ is drawn to scale after
the rescaling. The marked edge has length $3/13$.

Next, we define the rescaling. Instead of assigning a length
$n^{\beta},\beta<0$ to every edge, we rescale $T_{n}$ inhomogeneously. Before
we do this, we trim the tree: remove every leaf and its corresponding edge.
This results in a new tree $T_{n}^{\text{trim}}$ which is a subtree of
$T_{n}$. For every leaf $x\in T_{n}$ we distribute mass $1/n$ to the vertex in
$T_{n}^{\text{trim}}$ that is connected to $x$ in $T_{n}$, this defines a
probability measure $\mu_{n}^{\text{trim}}$ on $T_{n}^{\text{trim}}$. Now, we
rescale $T_{n}^{\text{trim}}$. We do this by defining edge lengths according
to an _inhomogenous IP–rescaling_. This means for an edge $(x,y)$ of
$T_{n}^{\text{trim}}$ we set its length to

$d_{n}^{\text{trim}}(x,y)=\left|\mu_{n}^{\text{trim}}\left(F_{T_{n}^{\text{trim}}}(x)\right)-\mu_{n}^{\text{trim}}\left(F_{T_{n}^{\text{trim}}}(y)\right)\right|.$
(1.5)

See Figure 7 for an example. We extend this to a metric $d_{n}^{\text{trim}}$
on $T_{n}^{\text{trim}}$ by adding edge lengths along the unique path between
two vertices. Let $r_{n}$ be the root of $T_{n}^{\text{trim}}$. In this
setting, $(T_{n},n\geq 1)$ satisfies a scaling limit.

######  Theorem 1.16.

Let $(T_{n},n\geq 1)$ be a tree–valued Markov chain with uniform backward
dynamics. Then there exists a random IP–tree $(\textbf{T},d,r,\mu)$ such that

$(T_{n}^{\text{trim}},d_{n}^{\text{trim}},r_{n},\mu_{n}^{\text{trim}})\xrightarrow{n\to\infty}(\textbf{T},d,r,\mu),$
(1.6)

almost–surely in the Gromov–Prokhorov topology. Further, the law of
$(\textbf{T},d,r,\mu)$ is given by

$\mathbb{P}\left((\textbf{T},d,r,\mu)\in\cdot\right)=\int\rho_{\textbf{T}}\left((\textbf{T},d,r,\mu)\in\cdot\right)\nu(d\textbf{T}),$
(1.7)

where $\nu$ is determined by Theorem 1.10.

This answers a question of Forman [9, Question $2$] if IP–trees arise as
scaling limits of suitably rescaled discrete random trees.

######  Remark 1.17.

This theorem is in a sense optimal: both homogeneous rescaling as well as the
Gromov-Hausdorff-Prokhorov topology are unsuitable in general. To see why a
homogeneous rescaling does not work, join two typical realisations of an
$\alpha$–stable tree $\mathcal{T}_{\alpha}$ and an $\alpha^{\prime}$–stable
tree $\mathcal{T}_{\alpha^{\prime}}$ at the root with
$\alpha>\alpha^{\prime}$. If we were to rescale by $n^{\beta}$, then we would
need both $\beta=-1+\frac{1}{\alpha}$ and $\beta=-1+\frac{1}{\alpha^{\prime}}$
according (1.2) for the correct convergence. This is of course not possible.
To see why the Gromov-Hausdorff-Prokhorov topology is too strong, construct a
real tree T in the following way: for $k\geq 1$, let $a_{k}$ be an atom of
weight $2^{-k}$. Connect $a_{k}$ to the root $r$ by an interval segment of
length $1-2^{-k}$. One can see that for all $n\geq 1$ we have
$d_{GHP}(T_{n},\textbf{T})\geq 1/2$. This is because there is $k\in\mathbb{N}$
such that for all $i\leq n$ we have $\xi_{i}\neq a_{k}$. This implies that
$T_{n}$ will not converge after rescaling, in essence this is due to T not
being a compact metric space.

The structure of this paper is as follows: in Section 2 we introduce an
encoding for tree–valued Markov chains, namely dendritic systems. Further, we
discuss our notion of planarity for real trees and some of the measure
theoretic aspects associated with the extremal decomposition of tree–valued
Markov chains. In Section 3 we prove Theorem 1.10 and in Section A we prove an
important auxiliary statement. Lastly in Section 4 we prove Theorem 1.16.

##  2 Preliminaries

###  2.1 Planar real trees

In this section we introduce a notion of planarity for real trees. Let
$\mathbb{T}$ be the space of finite plane trees. Let $\mathbb{T}^{\ell}$ be
the space of finite plane trees with leaves labelled by $[n]$, for some
$n\in\mathbb{N}$. Internal vertices are allowed to be labelled but do not have
to be, in this case there will be fewer than $n$ leaves so that the total
number of labelled vertices is $n$.

While the definition of planar real trees may seem complicated, the idea is
simple. For a given real tree $(\textbf{T},r)$, there already exists a natural
map which takes a sequence $x_{1},\ldots,x_{n}\in\textbf{T}$ to a
combinatorial tree by discretizing the subtree spanned by
$x_{1},\ldots,x_{n}$. We will now enhance these trees to be plane trees and
require the planarity to be suitably consistent as $x_{1},\cdots,x_{n}$ vary.
Further, we want to keep track which $x_{i}$ corresponds to which vertex in
the combinatorial tree. This is done by labelling some of the vertices. See
Figure 8 for an illustration of these ideas which we formalise in the
following definitions.

######  Definition 2.1.

Let $(\textbf{T},r)$ be a real tree and $x_{1},\ldots,x_{n}$ a finite sequence
in T. In the following, $<$ denotes the genealogical partial order in T
induced by $x<y$ if $[r,x]\subsetneq[r,y].$

  1. 1.)

We call $(x_{i},i\leq n)$ totally unordered if for any $i\neq j$ we have
$x_{i}\nless x_{j}$ and $x_{j}\nless x_{i}$.

  2. 2.)

$span(x_{1},\ldots,x_{n},r)$ denotes the minimal connected subset of T which
includes $\\{r,x_{i};i\leq n\\}$. We view $span(x_{1},\ldots,x_{n},r)$ as a
real tree rooted at $r$.

######  Definition 2.2.

We call $(\textbf{T},r,\psi)$ a planar real tree if $(\textbf{T},r)$ is a
rooted real tree and $\psi=\\{\psi_{n},n\geq 2\\}$ is a family of measurable
maps $\psi_{n}\mathrel{\mathop{\mathchar
58\relax}}\textbf{T}^{n}\rightarrow\mathbb{T}^{\ell}$ satisfying the following
properties:

  1. 1.)

As unlabelled non–plane tree, the tree $\psi_{n}(x_{1},\ldots,x_{n})$ is the
combinatorial tree corresponding to
$span(x_{1},\ldots,x_{n},r)$.

  2. 2.)

The vertex of $\psi_{n}(x_{1},\ldots,x_{n})$ corresponding to $x_{i}$ is
labelled $i$.

  3. 3.)

$\psi$ is consistent in the sense that for every $n,m\in\mathbb{N}$ and every
totally unordered $x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}\in\textbf{T}$ we have
that $\psi_{n}(x_{1},\ldots,x_{n})$ embeds into
$\psi_{n+m}(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})$ respecting the planar
order and leaf labels.

  4. 4.)

We extend $\psi_{n}$ to sequences that are not unordered. First, we apply
$\psi_{k},k<n$ to the totally unordered sequence $(x_{i},i\in I)$ with $k=|I|$
that maximises $span(r,x_{i};i\in I)$. Then, for each $i\notin I$ we split the
edge corresponding to $x_{i}$ into two edges and label the middle vertex $i$.
If $x_{i}$ is already a branchpoint in the span, we label the corresponding
vertex $i$. See Figure 8 for an example.

Figure 8: an example for a planar real tree with $13$ marked points and their
image under $\psi_{13}$. Note that not all internal points are labelled.

Besides generalising combinatorial labelled trees, there is another reason for
why this is a fairly natural notion which will be the following proposition.
Recall that a continuous function $g\mathrel{\mathop{\mathchar
58\relax}}[0,t]\rightarrow[0,\infty)$ with $g(0)=g(t)=0$ describes a real tree
$\textbf{T}_{g}$ via a quotient space construction. For $s\leq u$ set

$s\sim_{g}u\quad\text{iff}\quad g(s)=\inf_{r\in[s,u]}g(r)=g(u).$

Define $\textbf{T}_{g}=[0,t]/\sim_{g}$. The metric is then given by

$d_{\textbf{T}_{g}}(x,y)=g(x)+g(y)-2\inf_{z\in[x,y]}g(z),$

for $x,y\in[0,t]$. Here, we abuse notation in this regards to view elements of
$[0,t]$ as elements of $\textbf{T}_{g}$, otherwise we write $x^{*}\in[0,t]$
for a representative of $x\in\textbf{T}_{g}$. See for example Evans [7,
Example 3.14] for more details of this construction.

An example for such a function $g$ is the contour function $C_{T}$ of a finite
plane tree. Informally, this can be defined by a particle tracing the contour
of the tree at unit speed, $C_{T}(t)$ measures the distance to the root at
time $t$. Given $C_{T}$ we can retrieve the planar order: take two leaves
$x,y\in\textbf{T}$, $x,y$ correspond to two unique maxima of $C_{T}$, say
$C_{T}(u)=x,C_{T}(v)=y$. If $u<v$, then the leaf in $T$ corresponding to $x$
is to the left of the leaf corresponding to $y$. This determines the planar
order on $T$ uniquely.

######  Proposition 2.3.

For a given leaf–labelled plane tree $T$ without vertices of degree $2$ there
is a choice of maps $(\psi_{n})_{n\geq 2}$ such that if $T$ has $k$ leaves,
then (after deleting leaf labels) $\psi_{k}(\text{leaves of
}\textbf{T}_{C_{T}})=T$. This renders $\textbf{T}_{C_{T}}$ into a planar real
tree.

We remark that we can do the same for trees with vertices of degree $2$ and
retrieve the information about vertices with degree $2$ by inspecting the
metric on $\textbf{T}_{C_{T}}$.

###### Proof.

We first describe the maps $\psi_{n}$. Denote the leaves of
$\textbf{T}_{C_{T}}$ by $y_{1},\ldots,y_{k}$ and denote the root of
$\textbf{T}_{C_{T}}$ by $\rho$. Let $x_{1},\ldots,x_{n}\in\textbf{T}_{C_{T}}$
be totally unordered.

For $x,y\in\textbf{T}_{C_{T}}$, we denote $x\leftarrow y$ if for all
representatives $x^{*},y^{*}\in[0,t]$ of $x$ and $y$ we have $x^{*}<y^{*}$.
This can only be the case if $x$ and $y$ are unordered in
$\textbf{T}_{C_{T}}$. Let $x_{1},\ldots,x_{n}\in$ be totally unordered and let
$T_{n}$ be the leaf–labelled non–plane tree corresponding to
$span(x_{1},\ldots,x_{n},r)$.

We need to equip $T_{n}$ with a planar structure to make it into a plane tree.
Because $x_{1},\ldots,x_{n}\in$ is totally unordered, $x_{i}$ is a leaf of
$span(x_{1},\ldots,x_{n},r)$ for every $i$ and corresponds to a leaf in
$T_{n}$. Furthermore, this implies that there is a permutation $\sigma$ on
$[n]$ such that $x_{\sigma(1)}\leftarrow
x_{\sigma(2)}\leftarrow\ldots\leftarrow x_{\sigma(n)}$. We use this
permutation to determine the planar order of leaves of $T_{n}$, for all
$i,j\in[n];i\neq j$ if $\sigma(i)<\sigma(j)$ then we set the leaf labelled $i$
to be on the left of the leaf $j$. The tree structure of $T_{n}$ determines
the planar order of all other vertices, we choose
$\psi_{n}(x_{1},\ldots,x_{n})$ to be the resulting plane tree.

From this we can immediately see that $\psi_{k}(\text{leaves of
}\textbf{T}_{C_{T}})=T$. Indeed, if $x$ and $y$ are two leaves of $T$ such
that $x$ is to the left of $y$, then $x\leftarrow y$ by perceiving them as
elements of $\textbf{T}_{C_{T}}$. Because the left–right ordering of the
leaves of $T$ determines planar structure uniquely, and because the
combinatorial tree corresponding to $\textbf{T}_{C_{T}})$ is $T$ without the
planar order, we have that $T=\psi_{k}(\text{leaves of }\textbf{T}_{C_{T}})$ –
after we have deleted the leaf labels.

Lastly, we need to show that if
$x_{1},\ldots,x_{n},y\in\textbf{T}_{C_{T}})^{n+1}$ is totally unordered, then
$\psi_{n}(x_{1},\ldots,x_{n})$ embeds into $\psi_{n+1}(x_{1},\ldots,x_{n},y)$.
This follows from two facts: Firstly, the combinatorial tree corresponding to
$span(x_{1},\ldots,x_{n},r)$ embeds naturally into the combinatorial tree
corresponding to $span(x_{1},\ldots,x_{n},y,r)$. Secondly, this embedding
respects the planar order of $\psi_{n}(x_{1},\ldots,x_{n})$ and
$\psi_{n+1}(x_{1},\ldots,x_{n},y)$. Indeed if $\sigma^{(n)}$ and
$\sigma^{(n+1)}$ are the two permutations used in the construction of the
trees, then $\sigma^{(n+1)}$ restricted to $[n]$ is $\sigma^{(n)}$ in the
sense that if $\sigma^{(n+1)}(i)<\sigma^{(n+1)}(j)$ then
$\sigma^{(n)}(i)<\sigma^{(n)}(j)$.

∎

######  Remark 2.4.

This construction can be extended to any real tree $\textbf{T}_{g}$ encoded by
some function $g$. This includes continuum random trees like the Brownian
continuum random tree.

In the above proof we made use of referring to leaves being left or right of
one another. We introduce a similar notation for subtrees at a given point in
T, recall our definition of subtrees from Definition 1.3.

######  Definition 2.5.

For a planar real tree $(\textbf{T},r,\psi)$, a point $x\in\textbf{T}$ and any
two subtrees $\textbf{S}_{1},\textbf{S}_{2}$ attached to $x$ we say that
$\textbf{S}_{1}$ is _to the left_ (respectively to the right) of
$\textbf{S}_{2}$ if this is the case for the labelled leaves of
$\psi_{2}(s_{1},s_{2})$ for arbitrary
$s_{1}\in\textbf{S}_{1}\backslash\\{x\\},s_{2}\in\textbf{S}_{2}\backslash\\{x\\}$.
We will write $\textbf{S}_{1}<\textbf{S}_{2}$ to denote that $\textbf{S}_{1}$
is to the left of $\textbf{S}_{2}$.

Note that the choice of $s_{1}\in\textbf{S}_{1}\backslash\\{x\\}$ does not
matter due to the consistency properties of $\psi$.

###  2.2 Dendritic systems

In this section we introduce the notion of dendritic systems. These objects
aim to generalise finite leaf–labelled plane trees to infinitely many labels
with a strong focus on the leaves. The reason for considering dendritic
systems is that they allow us to encode a tree–valued Markov chain as a more
static object. This notion is similar to that of didendritic systems of [8,
Def. 5.8] which was introduced to generalise binary trees. Our notion has the
advantage of accommodating multi–furcating trees as well.

We will surrender the notion of edges and keep only the ancestral relation. By
ancestral relation we mean that $x$ precedes $y$ in a combinatorial tree $T$,
$x\preceq y$, if the path from the root to $y$ contains $x$. Any vertex will
be thought of as a most recent common ancestor of two leaves.

In the following definition, these ideas result in conditions $(C1)$–$(C4)$.
There, $(i,j)$ denotes the most recent common ancestor of two leaves labelled
$i,j$. We require that leaves do not precede any other vertices $(C1)$ and
that leaves are descendants of their ancestors $(C2)$. For two vertices,
$(i,j)$ and $(k,\ell)$, we require that there is another vertex which acts as
most recent common ancestor, phrased a minimal element with respect to
$\preceq$, $(C4)$. $(C3)$ and $(C4)$ act as analogues of the no–cycles
condition of combinatorial trees.

Further, we want to be able to encode the planar order of combinatorial trees
as well. This is again done by specifying a left–right ordering of vertices.
Recall that in the combinatorial tree the left–right order is derived from its
Ulam–Harris encoding, _for example the word $(0,1,1,5,3)$ is to the left of
the word $(0,1,2,1)$_. We encode this left–right ordering by introducing a
planarity function $p$ where $p(x,y)=1$ signifies that $y$ is to the right of
$x$, respectively $p(x,y)=-1$ means that $y$ is to the left of $x$. If $x$ and
$y$ are ordered by the ancestral relation, we do not assign any left–right
ordering. These ideas result in conditions $(P1)$–$(P4)$: $(P1)$ states that
if $x$ is to the right of $y$, then $y$ is to the left of $x$. $(P2)$ states
that there is no left–right relation between vertices that satisfy $x\preceq
y$ or $y\preceq x$. $(P3)$ states that if $y$ is to the right of $x$ and $z$
is to the right of $y$ then $z$ is also to the right of $x$. Lastly, $(P4)$
states that if $y$ is to the right of $x$ then also any descendant of $y$ is
to the right of $x$.

In Lemma 2.8 we will show that this does indeed generalise plane,
leaf–labelled, combinatorial trees.

######  Definition 2.6 (Dendritic system).

Let $L\subset\mathbb{N}$ be a finite or countably infinite set of leaf labels.
A planar dendritic system $\mathcal{D}=(L,\sim,\preceq,p)$ is the collection
of the following objects: an equivalence relation $\sim$ on $L\times L$, we
denote the space of equivalence classes as $T$; a genealogical partial order
$\preceq$ on $T$ and a planarity function $p\mathrel{\mathop{\mathchar
58\relax}}T\times T\rightarrow\\{0,1,-1\\}$ satisfying the following
properties for all $i,j,k,\ell\in L$:

  * (C1)

$(i,j)\sim(j,i)$, and $(i,j)\sim(k,k)$ if and only if $i=j=k$.

  * (C2)

$(i,j)\preceq(i,i)$.

  * (C3)

$(i,j)\preceq(k,\ell)$ and $(k,\ell)\preceq(i,j)$ if and only if
$(i,j)\sim(k,\ell)$.

  * (C4)

$a((i,j),(k,\ell))=\min_{\preceq}\\{(i,j),(k,\ell),(i,\ell),(i,k),(j,\ell),(j,k)\\}$
exists in $T$.

Further, the planarity function $p$ satisfies for all $x,y,z\in T$:

  * (P1)

$p(x,y)=-p(y,x)$.

  * (P2)

$p(x,y)=0$ if and only if $x\preceq y$ or $y\preceq x$.

  * (P3)

If $p(x,y)=1$ and $p(y,z)=1$ then $p(x,z)=1$.

  * (P4)

If $p(x,y)=1$ and $y\preceq z$ then $p(x,z)=1$.

Here $x\prec y$ corresponds to $x\preceq y$ and $x\neq y$. We will always
refer to $\\{(i,i);i\in L\\}$ as the leaves of $\mathcal{D}$. Moreover,
consider two arbitrary vertices $(i,j)$ and $(k,\ell)$. Unless there is an
ancestral relationship between $(i,j)$ and $(k,\ell)$, $(P4)$ allows us to
determine $p((i,j),(k,\ell))$, namely
$p((i,j),(k,\ell))=p(i,k)=p(j,k)=p(i,\ell)=p(j,\ell)$ where we abuse notation
to write $i=(i,i)$. We can rephrase this as follows.

######  Lemma 2.7.

For a dendritic system $(L,\sim,\preceq,p)$, $p$ is uniquely determined by
$\preceq$ and $\\{p(i,j);i,j\in L\\}$ where we write $i=(i,i)$.

In the case where $L$ is finite, dendritic systems precisely correspond to
rooted plane trees:

######  Lemma 2.8.

If $L$ is finite, there is a natural bijection between the set of dendritic
systems $\mathcal{D}=(L,\sim,\preceq,p)$ and the set of leaf–labelled rooted
plane trees $(T,r)$ without vertices of degree $2$ (except for possibly the
root) and leaves labelled by $L$.

######  Remark 2.9.

Similarly to the space of trees, we equip the space of dendritic systems with
the $\sigma$–algebra that is generated by finite projections. In the case of
trees, we project onto a finite ball around the root and in the case of
dendritic systems we restrict the dendritic system to to $[n]\cap L$.

###### Proof of Lemma 2.8..

On the one hand, let $(T,r)$ be a leaf–labelled rooted plane tree, we can
assume that every edge is directed towards the root. For two leaves labelled
$i,j\in T$, we let $b(i,j)\in T$ be their most recent common ancestor. Define
a dendritic system as follows: $(i,j)\sim(k,\ell)$ if $b(i,j)=b(k,\ell)$,
$(i,j)\preceq(k,\ell)$ if there is a directed path from $b(k,\ell)$ to
$b(i,j)$, and $p(i,j)=1$ for two leaves labelled $i,j$ if $i$ precedes $j$ in
lexicographic order of the Ulam–Harris encoding. By Lemma 2.7, this determines
$p$ uniquely.

On the other hand, let $\mathcal{D}=(L,\sim,\preceq,p)$ be a dendritic system.
We want to define a plane leaf–labelled tree $(T,r)$. The equivalence classes
of $(L\times L,\sim)$ are the vertices and we add an edge between $x$ and $y$
if there is no $z$ such that $x\prec z\prec y$. Because $L$ is finite, this
yields a tree. We direct an edge $(x,y)$ to $x$ if $x\prec y$ and to $y$
otherwise. The root $r$ is now the minimal element of this directed tree, it
exists due to $(C3)$ and $(C4)$. Lastly, we need to impose a planar order on
$T$, i.e. a valid Ulam–Harris encoding of the vertices. This is done
iteratively from the root $r$, encoded by $\emptyset$. Then every vertex has
finitely many children $x_{1},\ldots,x_{n}$. Due to $(P3)$ there is a
permutation $\sigma$ such that $p(x_{\sigma(i)},x_{\sigma(j)})=1$ if $i<j$.
$x_{i}$ is then encoded by its parents encoding appended with $\sigma(i)$.
Loosely speaking, $p$ determines a permutation at each branchpoint of $T$
which we use to obtain a planar order.

One can see that the two procedures described above are inverse to each other.
∎

This allows us to illustrate a link between dendritic systems and planar real
trees. Let $(\textbf{T},r,\psi)$ be a planar real tree.

######  Corollary 2.10.

For any totally unordered sequence $(x_{1},x_{2},\ldots)\in\textbf{T}$ there
is a dendritic systems $\mathcal{D}$ on $\mathbb{N}$ such that the restriction
of $\mathcal{D}$ to $[n]$ is isomorphic to $\psi_{n}(x_{1},\ldots,x_{n})$ as
rooted plane leaf–labelled trees.

###### Proof.

By Lemma 2.8 there exists a dendritic system $\mathcal{D}^{(n)}$ with leaves
labelled $[n]$ such that the plane leaf–labelled tree corresponding to
$\mathcal{D}^{(n)}$ is $\psi_{n}(x_{1},\ldots,x_{n})$. Because
$(\textbf{T},r,\psi)$ is a planar real tree $\psi_{n}(x_{1},\ldots,x_{n})$
embeds into $\psi_{n+m}(x_{1},\ldots,x_{n+m})$ which means that we have that
$\mathcal{D}^{(n+m)}$ restricted to $[n]$ is $\mathcal{D}^{(n)}$. This implies
the existence of a dendritic system $\mathcal{D}$ with the desired property. ∎

The corollary above directly yields a method to construct random dendritic
systems: assume $(\textbf{T},d,r,\psi)$ is endowed with a diffuse probability
measure $\mu$ that puts all mass on the leaves. Sample
$(\xi_{1},\xi_{2},\ldots)$ $i.i.d.$ from $\mu$, then
$(\xi_{1},\xi_{2},\ldots)$ gives rise to a random dendritic system.

In light of the main theorem, Theorem 1.10, this already foreshadows how we
want to use dendritic systems:

######  Proposition 2.11.

Any tree–valued Markov chain $(T_{n},n\geq 1)$ with uniform backward dynamics
corresponds to an exchangeable dendritic system and vice versa.

We should specify precisely how we define exchangeability for dendritic
systems. Given a finite permutation $\sigma$ on the leaf labels and a
dendritic system $\mathcal{D}=(L,\sim,\preceq,p)$ we define the dendritic
system $\mathcal{D}^{\sigma}=(L,\sim^{\sigma},\preceq^{\sigma},p^{\sigma})$ by

  1. 1.)

$(i,j)\sim^{\sigma}(k,\ell)$ if and only if
$(\sigma(i),\sigma(j))\sim(\sigma(k),\sigma(\ell))$,

  2. 2.)

$(i,j)\preceq^{\sigma}(k,\ell)$ if and only if
$(\sigma(i),\sigma(j))\preceq(\sigma(k),\sigma(\ell))$,

  3. 3.)

$p^{\sigma}(i,j)=p(\sigma(i),\sigma(j))$.

######  Definition 2.12.

For a random dendritic system $\mathcal{D}$ we say that $\mathcal{D}$ is

  1. 1.)

exchangeable, if $\mathcal{D}$ and $\mathcal{D}^{\sigma}$ have the same
distribution for every finite permutation $\sigma$ on the leaf labels;

  2. 2.)

ergodic, if we have that for any event $A$ we have
$\mathbb{P}(\\{\mathcal{D}\in A\\})\in\\{0,1\\}$ whenever
$\mathbb{P}(\\{\mathcal{D}\in A\\}\Delta\\{\mathcal{D}^{\sigma}\in A\\})=0$
for every finite permutation $\sigma$ on the leaf labels.

###### Proof of Proposition 2.11..

We will write $\mathcal{D}|_{[n]}$ if we restrict a dendritic system to the
leaves labelled by $[n]$, respectively the equivalence classes of
$[n]\times[n]$.

Let us describe how to encode $(T_{n},n\geq 1)$ in a dendritic system. To this
end, we define a sequence of dendritic systems
$(\mathcal{D}_{n}=([n],\sim_{n},\preceq_{n},p_{n}))_{n\in\mathbb{N}}$. For
fixed $n$, label the leaves of $T_{n}$ uniformly by $[n]$ and let
$\mathcal{D}_{n}$ be the corresponding dendritic system by Lemma 2.8. Note
that $\mathcal{D}_{n}$ and $\mathcal{D}_{n+m}|_{[n]}$ agree in law. Indeed,
this is true because of the uniform backward dynamics as restricting
$\mathcal{D}_{n+m}$ to $[n]$ corresponds to $m$ steps backwards in the Markov
chain. Hence $(\mathcal{D}_{n})_{n\in\mathbb{N}}$ forms a consistent family
and by the Daniell–Kolmogorov extension theorem there exists a dendritic
system $\mathcal{D}$ such that $\mathcal{D}|_{[n]}=\mathcal{D}_{n}$ in
distribution, for all $n\in\mathbb{N}$.

On the other hand, if we are given a dendritic system $\mathcal{D}$, then
$(\mathcal{D}|_{[n]},n\geq 1)$ corresponds to a sequence of plane
leaf–labelled trees by Lemma 2.8. Remove the labels to obtain a sequence of
plane leaf–labelled trees $(T_{n},n\geq 1)$. Because $\mathcal{D}$ is
exchangeable, we can see that the backward dynamics of $(T_{n},n\geq 1)$ are
uniform by considering a uniform permutation of the leaf labels. ∎

In the proof of Theorem 1.10 we will decompose the law of $(T_{n},n\geq 1)$
into extremal measures. This is in the sense of convex combinations of
distributions of $(T_{n},n\geq 1)$ for different choices of $(T_{n},n\geq 1)$.
Call $(T_{n},n\geq 1)$ _extremal_ if its distribution is extremal in the space
of probability measures of tree–valued Markov chains with uniform backward
dynamics. These are precisely the tree growth processes that correspond to
ergodic dendritic systems.

######  Proposition 2.13.

The Markov chain $(T_{n},n\geq 1)$ is extremal if and only if the associated
dendritic system is ergodic.

The proof of this proposition is a straightforward generalisation of [8,
Proposition 5.19] and we refer to the book of Kallenberg [18, Theorem A1.4]
for background on ergodic decompositions. Due to the above propositions we
will study exchangeable, ergodic dendritic systems instead of tree–valued
Markov chains with uniform backward dynamics.

###  2.3 Doob–Martin boundary viewpoint

Let use elaborate on the connection of (1.1) and the Doob–Martin boundary. In
the case of Marchal’s tree growth, we neglect the dependence on $\alpha$. If
we consider a conditioned version of Marchal’s tree growth of the form

$\mathbb{P}\big{(}T_{m}^{M}\in\cdot\big{|}T_{n}^{M}=T\big{)},$ (2.1)

for $m<n$, then we do not need to know how exactly the tree growth is defined
to construct $T_{m}^{M}$. Instead, we only need to know that Marchal’s tree
growth possesses uniform backward dynamics. This means iteratively remove
uniform leaves to obtain $(T_{m}^{M},1\leq m\leq n)$ under the conditioned
measure. This means that under the conditioned measure $(T_{m}^{M},1\leq m\leq
n)$ is a tree–valued Markov chain with uniform backward dynamics with finite
time horizon. If we can find a sequence of trees $(T^{(n_{k})},k\geq 1)$ such
that $n_{k}\to\infty$ as $k\to\infty$ and such that

$\lim_{k\to\infty}\mathbb{P}\big{(}T_{m}^{M}\in\cdot\big{|}T_{n_{k}}^{M}=T^{(n_{k})}\big{)}\quad\text{exists,}$
(2.2)

then we obtain a tree–valued Markov chain with infinite time horizon.

The procedure above is related to the Doob–Martin boundary of the Markov chain
$(T_{n}^{M},n\geq 1)$. Our references here are the book of Woess [21, Chapter
7] for the general case and [8, Section 2 and 3] for tree–valued Markov
chains, see also [8] for more references. Recall that we write $\mathbb{T}$
for the space of plane trees so that $(T_{n}^{M},n\geq 1)$ is a
$\mathbb{T}$–valued Markov chain. In the following we abbreviate
$e=T^{M}_{1}$, the unique tree consisting of a single edge. We also write
$\mathbb{P}^{S}$ for the probability measure under which $(T_{n}^{M},n\geq 1)$
is Marchal’s tree growth with $T_{1}^{M}=S$, $\mathbb{P}^{S}$–almost surely.
For two trees $S,T$ with $m<n$ leaves respectively we define the probability
that starting from $S$ we will ever see $T$

$p(S,T)\mathrel{\mathop{\mathchar
58\relax}}=\mathbb{P}^{S}(T^{M}_{\ell}=T\text{ for some
}\ell)=\mathbb{P}^{S}(T^{M}_{n-m+1}=T).$

Indeed, because we add a leaf in every step of the Markov chain, this can only
happen after $n-m$ steps. We use this to define the Doob–Martin kernel $K$ of
$T^{M}$ for $S,T\in\mathbb{T}$ by

$K(S,T)\mathrel{\mathop{\mathchar 58\relax}}=\frac{p(S,T)}{p(e,T)}$

whenever $p(e,T)>0$. Implicitly we now restrict our space $\mathbb{T}$ to
$\\{T\in\mathbb{T}\mathrel{\mathop{\mathchar 58\relax}}p(e,T)>0\\}$, if
$p(e,T)=0$ we define $K(S,T)=0$ for all $S$. Let $\Pi$ be the transition
matrix of Marchal’s tree growth. We then have for $S\neq T$,

$\sum_{T^{\prime}\in\mathbb{T}}\Pi(S,T^{\prime})K(T^{\prime},T)=K(S,T).$ (2.3)

This is not true for $S=T$. Hence, $K(\cdot,T)$ is almost a harmonic function.
Observe for $S$ with $m$ leaves and $T$ with $n>m$ leaves:

$K(S,T)=\frac{1}{\mathbb{P}^{e}(T_{m}^{M}=S)}\mathbb{P}^{e}\big{(}T_{m}^{M}=S\big{|}T_{n}^{M}=T\big{)}=\frac{1}{C(S)}\mathbb{P}^{e}\big{(}T_{m}^{M}=S\big{|}T_{n}^{M}=T\big{)},$

where the constant $C(S)$ depends on $S$ but not on $T$. This illustrates the
connection between the kernel $K$ and (2.1).

One can then show that $K(\cdot,T)\neq K(\cdot,T^{\prime})$ whenever $T\neq
T^{\prime}$. Indeed, if $S$ has the same number of leaves as $T$ then
$K(S,T)\neq 0$ if and only if $S=T$. This yields a bijection between
$\mathbb{T}$ and $\\{K(\cdot,T),T\in\mathbb{T}\\}$. The advantage is that
$\\{K(\cdot,T),T\in\mathbb{T}\\}\subset\mathbb{R}_{+}^{\mathbb{T}}$ and that
it turns out to be precompact under the induced topology. We let
$\overline{\mathbb{T}}$ be the closure of $\mathbb{T}$ in
$\mathbb{R}_{+}^{\mathbb{T}}$, the so–called _Doob–Martin compactification_ of
$\mathbb{T}$. The set
$\partial\mathbb{T}=\overline{\mathbb{T}}\backslash\mathbb{T}$ is called the
_Doob-Martin boundary_ of the Markov chain $T^{M}$. We equip
$\overline{\mathbb{T}}$ with its Borel–$\sigma$–algebra. We write $K(\cdot,b)$
for an element $b\in\partial\mathbb{T}$ of the boundary. These considerations
lead to the following statement, for more details see [8, Section 2 and 3].

######  Proposition 2.14.

[8, Corollary 3.10] For a sequence of trees $(T^{(n_{k})},k\geq 1)$ where
$T^{(n_{k})}$ has $n_{k}$ leaves and $n_{k}\to\infty$, the limit in (2.2)
exists if and only if $(T^{(n_{k})},k\geq 1)$ converges in the Doob–Martin
boundary $\partial\mathbb{T}$.

By choosing $T^{(n)}=T_{n}$ where $(T_{n},n\geq 1)$ has uniform backward
dynamics, we immediately obtain the following consequence.

######  Theorem 2.15 (Boundary convergence).

A tree–valued Markov chain $(T_{n},n\geq 1)$ with uniform backward dynamics
converges almost surely in $\overline{\mathbb{T}}$, the limit is supported in
$\partial\mathbb{T}$. In particular this is the case for Marchal’s tree
growth.

This is true because $(T_{n},n\geq 1)$ has the same backwards dynamics as
Marchal’s tree growth and hence the same Doob–Martin boundary. This is a
general fact in the abstract setting, see [21, Theorem 7.19].

A natural consequence of this statement is that we want to identify the
limiting distribution in a more tractable object. This is done in our main
theorem, Theorem 1.10. There is a second, general statement related to the
Doob–Martin boundary. It concerns itself with $\Pi$–harmonic functions, recall
from (2.3) that $K$ is closely connected to harmonic functions. In fact, for
fixed $b\in\partial\mathbb{T}$ the function $K(\cdot,b)$ is harmonic. Every
other harmonic function can be decompositioned as follows, in the general
setting this is [21, Theorem 7.45].

######  Theorem 2.16 (Integral representation).

For a harmonic function $h\mathrel{\mathop{\mathchar
58\relax}}\mathbb{T}\to\mathbb{R}_{+}$ with $h(e)=1$ there exists an unique
probability measure $\nu^{h}$ on $\partial\mathbb{T}$ such that for every
$T\in\mathbb{T}$ we have

$h(T)=\int_{\partial\mathbb{T}}K(T,b)\nu^{h}(db).$

Recall that the set of probability distributions of tree growth processes is a
convex set. A distribution is called extremal if it cannot be written as a
non–trivial convex combination of two other distributions. To conclude this
section, we state that any probability measure on tree–valued Markov chains
can be decomposed into its extremal elements. Due to this statement, it
suffices to consider tree growth processes $(T_{n},n\geq 1)$ whose
distribution is extremal.

######  Corollary 2.17.

The set of extremal distributions can be parameterised by
$\\{\mu^{b},b\in\partial\mathbb{T}\\}$. Further, for any Markov chain
$(T_{n},n\geq 1)$ with uniform backward dynamics there exists a probability
measure $\hat{\nu}$ such that

$\mathbb{P}\left((T_{n},n\geq
1)\in\cdot\right)=\int_{\partial\mathbb{T}}\mu^{b}\left((T_{n},n\geq
1)\in\cdot\right)\hat{\nu}(db).$

###### Proof.

This will follow from Theorem 2.16 once we show that there is a correspondence
between harmonic functions and Markov chains.

Given $(T_{n},n\geq 1)$ denote its limit in $\partial\mathbb{T}$ by $B$,
according to Theorem 2.15 this exists almost surely. We define a harmonic
function by

$h(T)=\int_{\partial\mathbb{T}}K(T,b)\mathbb{P}(B\in db).$ (2.4)

On the other hand, given a harmonic function $h^{\prime}$, we define a new
Markov chain on the set $\\{T\in\mathbb{T}\mathrel{\mathop{\mathchar
58\relax}}h^{\prime}(T)>0\\}$ by its transition matrix,

$\Pi^{h^{\prime}}(S,T)=\frac{1}{h^{\prime}(S)}\Pi(S,T)h^{\prime}(T),$

where $\Pi$ is the transition matrix of Marchal’s tree growth. This is a Doob
$h$–transform. If we now choose $h^{\prime}=h$ as in (2.4), we obtain the
distribution of the Markov chain $(T_{n},n\geq 1)$. This follows from a
computation that when we condition on $\\{T_{N}=T\\}$, the distribution of the
initial segment $(T_{n},n\leq N)$ is given by an $h$–transform with
$K(\cdot,T)$. This computation is straight–forward and can be found in [8,
Chapter 2]. By then taking the limit $N\to\infty$ and Theorem 2.15 we obtain
the correspondence between Markov chains and harmonic functions. We leave it
to the reader to check that a convex combination of harmonic functions
translates to a convex combination of the distributions associated to the
Markov chains.

The corollary now follows from Theorem 2.16, $h$ corresponds to an extremal
distribution if and only if $\nu^{h}=\delta_{b}$ for some
$b\in\partial\mathbb{T}$. ∎

##  3 Proof of Theorem 1.10

Recall that we can encode a tree–valued Markov chain $(T_{n},n\geq 1)$ with
uniform backward dynamics in an exchangeable dendritic system in Proposition
2.11, recall the definition of dendritic systems from Definition 2.6. Recall
also that extremal tree growth processes correspond to ergodic dendritic
systems. The proof of Theorem 1.10 consists of three steps: we decompose the
distribution of $(T_{n},n\geq 1)$ into extremal measures with Corollary 2.17,
we then show that for every extremal distribution there is _some_ decorated
planar real tree and lastly we show that this can be chosen to be a IP–tree.
The latter two steps are made up of Propositions 3.3 and 3.4.

First, we will state how to sample a dendritic system
$\mathcal{D}=(\mathbb{N},\sim,\preceq,p)$ from a decorated planar real tree
$(\textbf{T},d,r,\mu,\psi,\lambda,B)$. Recall that $\psi$ is a planar order
for the rooted, weighted real tree $(\textbf{T},d,r,\mu)$, $\lambda$ a branch
weight function and $B$ a branchpoint weight function. We split the
construction into two parts, sampling $(\mathbb{N},\sim,\preceq)$ from the
tree and determining the planarity function $p$ using $(\psi,\lambda,B)$ and
extra randomness.

######  Construction 3.1.

Sample a sequence $\\{\xi_{i}\\}_{i\in\mathbb{N}}$ $i.i.d.$ from $\mu$. We
then define for $i,j,k,\ell\in\mathbb{N}$:

  1. 1.)

$(i,i)\sim(k,\ell)$ if and only if $i=k=\ell$.

  2. 2.)

$(i,j)\sim(k,\ell)$ for $i\neq j,k\neq l$ if and only if
$[r,\xi_{i}]\cap[r,\xi_{j}]=[r,\xi_{\ell}]\cap[r,\xi_{k}]$.

  3. 3.)

A partial order $\preceq$ on $\mathbb{N}^{2}/\sim$ is inherited from the
genealogical partial order $<$ on T and adding $(i,j)\prec(i,i)$ for $i\neq
j$. This means for distinct $i,j,k,\ell\in\mathbb{N}$ we set

$(k,\ell)\prec(i,j)\quad\text{ if and only if
}\quad[r,\xi_{k}]\cap[r,\xi_{\ell}]\subsetneq[r,\xi_{i}]\cap[r,\xi_{j}].$

######  Construction 3.2.

In the setting of Construction 3.1, we now sample
$\\{U_{i}\\}_{i\in\mathbb{N}}$ $i.i.d.$ uniform random variables from $[0,1]$
independently from $\\{\xi_{i}\\}_{i\in\mathbb{N}}$.

  1. 1.)

To determine the planarity function $p$, we distinguish four cases. Recall
that we decomposed $\mu=\mu_{atoms}+\mu_{s}+\mu_{\ell}$ into the mass on the
atoms, the skeleton (diffusely) and the leaves (diffusely).

    1. (a)

If neither $\xi_{i}<\xi_{j}$ nor $\xi_{j}<\xi_{i}$, then $p$ is determined by
$\psi_{2}(\xi_{i},\xi_{j})$, see Figure 9 for an illustration. More precisely,
there is a unique plane tree with two leaves and one root, we need to check
which of the two leaves is labelled $i$ and which is labelled $j$. We set

$p(i,j)=\begin{cases}1\quad&\text{if the left leaf is labelled $i$ and the
right leaf is labelled $j$ in }\psi_{2}(\xi_{i},\xi_{j}),\\\
-1&\text{otherwise}.\end{cases}$

    2. (b)

If $\xi_{i}<\xi_{j}$ we distinguish two cases.

      1. i.

In the case that $\xi_{i}\in supp\ \mu_{s}$, we set

$p(i,j)=\begin{cases}1\quad&\text{if }U_{i}<\lambda(\xi_{i}),\\\ -1&\text{if
}U_{i}\geq\lambda(\xi_{i}).\end{cases}$

      2. ii.

In the case that $\xi_{i}\in supp\ \mu_{atoms}$, we first need to identify the
subtree of $\xi_{i}$ in which $\xi_{j}$ is located – see Definition 1.3 for
our notion of subtree and Definition 2.5 for subtrees being left or right of
each other. Denote by $\textbf{S}_{j}$ the unique subtree which contains
$\xi_{j}$. Let

$\beta_{\xi_{i}}(\textbf{S}_{j})=\beta_{\xi_{i}}\left(\mu(\textbf{S}_{j})+\sum_{\textbf{S}^{\prime}<\textbf{S}_{j}}\mu(\textbf{S}^{\prime})\right).$

We then set

$p(i,j)=\begin{cases}1\quad&\text{if
}U_{i}<\beta_{\xi_{i}}(\textbf{S}_{j}),\\\ -1&\text{if
}U_{i}\geq\beta_{\xi_{i}}(\textbf{S}_{j}).\end{cases}$

    3. (c)

If $\xi_{i}>\xi_{j}$, we do the same as above with reversed roles for $i$ and
$j$.

    4. (d)

If $\xi_{i}=\xi_{j}$, we set

$p(i,j)=\begin{cases}1\quad&\text{if }U_{i}<U_{j},\\\ -1&\text{if }U_{i}\geq
U_{j}.\end{cases}$

Note that the value of $p((i,j),(k,\ell))$, where $(i,j),(k,\ell)$ are not
leaves, is uniquely determined by the values of $p$ on the leaves by imposing
the consistency relations $(P1)$–$(P4)$, see Lemma 2.7.

Figure 9: How $\psi$ is used to determine $p$ in the sampling construction.
Given two (random) points $\xi_{i}$ and $\xi_{j}$ which do not satisfy
$\xi_{i}\prec\xi_{j}$ nor $\xi_{j}\prec\xi_{i}$, $\psi_{2}$ maps these points
to the unique tree with two leaves. The two options to label the leaves
correspond to $p(i,j)=\pm 1$ respectively.

In the following sections we will show these two propositions.

######  Proposition 3.3.

For every ergodic dendritic system $\mathcal{D}$ there exists a deterministic
decorated planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ such that the
distribution of $\mathcal{D}$ equals the one sampled from Constructions 3.1
and 3.2.

######  Proposition 3.4.

The decorated planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ in
Proposition 3.3 can be uniquely chosen as a decorated planar IP–tree up to
measure and root preserving isometry of $(\textbf{T},d,r,\mu)$.

We prove Theorem 1.10 from these propositions.

###### Proof of Theorem 1.10..

Let $(T_{n},n\geq 1)$ be a tree–valued Markov chain with uniform backward
dynamics.

Suppose that $(T_{n},n\geq 1)$ is extremal in the sense of Section 2.3. Then
by Proposition 2.13 it corresponds to an ergodic dendritic system
$\mathcal{D}$. By Propositions 3.3 and 3.4 there exists a decorated planar
IP–tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ – unique up to measure and root
preserving isometry of $(\textbf{T},d,r,\mu)$ – such that $\mathcal{D}$ has
the same distribution as the dendritic system obtained through Constructions
3.1 and 3.2. By Proposition 2.13 the same is true for the Markov chain
$(T_{n},n\geq 1)$.

In the case that $(T_{n},n\geq 1)$ is not extremal, the desired statement
follows from the decomposition into extremal distribution in Corollary 2.17
and the above considerations for extremal tree–growth chains. ∎

###  3.1 Existence of a sampling representation

In this section we will prove Proposition 3.3. A key step in this proof is the
following Proposition 3.6. The proposition deals with the following
construction.

######  Construction 3.5.

Assume that we are given a weighted, rooted real tree $(\textbf{T},d,r,\mu)$
and a function $F\mathrel{\mathop{\mathchar
58\relax}}(\textbf{T}\times[0,1])^{2}\times[0,1]\rightarrow\\{\pm 1\\}$. Let
$Leb$ be the Lebesgue measure on $[0,1]$. Assume that $F$ satisfies the
following consistency relations for $\mu$–almost every $x,y,z$ and
$Leb$–almost every $u,v,w,a,b,c$.

  1. (F1)

$F(x,u,y,v,a)=-F(y,v,x,u,a)$,

  2. (F2)

if $F(x,u,y,v,a)=F(y,v,z,w,b)$ then also $F(x,u,z,w,c)=F(x,u,y,v,a)$,

  3. (F3)

if $[r,x]\cap[r,y]\notin\\{[r,x],[r,y]\\}$ and $[r,y]\subsetneq[r,z]$ then
$F(x,u,y,v,a)=F(x,u,z,w,b)$,

  4. (F4)

if $[r,x]\subsetneq[r,y]\subsetneq[r,z]$ then $F(x,u,y,v,a)=F(x,u,z,w,c)$.

Then, in the context of Construction 3.1, sample $i.i.d.$ uniform random
variables $\\{U_{i},U_{ij}\\}_{i,j\in\mathbb{N},i<j}$ from $[0,1]$. We define
a planarity function $p$ by

$p(i,j)=F(\xi_{i},U_{i},\xi_{j},U_{j},U_{i,j}),$

abusing notation to write $i=(i,i)$. The value of $p((i,j),(k,\ell))$, where
$(i,j),(k,\ell)$ are not leaves, is uniquely determined by the values of $p$
on the leaves by imposing the consistency relations $(P1)$–$(P4)$, see Lemma
2.7.

######  Proposition 3.6.

Every ergodic, exchangeable dendritic system $\mathcal{D}$ can be represented
by a real tree $(\textbf{T},d,r)$, a probability measure $\mu$ on T and a
measurable function $F\mathrel{\mathop{\mathchar
58\relax}}(\textbf{T}\times[0,1])^{2}\times[0,1]\rightarrow\\{\pm 1\\}$ in
such a way that we have $\textbf{T}=span(supp(\mu))$, $F$ is satisfies the
consistency relations stated in Construction 3.5 and $\mathcal{D}$ is then
equal in distribution to the dendritic system constructed through
Constructions 3.1 and 3.5.

Its proof is analogous to the proof of [8, Theorem 8.2] but makes use of the
full generality of a theorem of Gufler [14]. We will prove Proposition 3.6 in
Section A. The consistency conditions on $F$ correspond naturally to the
consistency conditions of $p$, see Section A.3. We also note that in Theorem
[8, Theorem 8.2] similar consistency relations are imposed.

Remark that it suffices to describe the dendritic system restricted to $[n]$
for every $n$ to determine the distribution of the dendritic system uniquely.
We prove Proposition 3.3 assuming that Proposition 3.6 is given. This means
that this proposition provides the tree T and the measure $\mu$, hence we can
consider specific trees and measures. We first consider three special cases
for T as a warm–up: when the mass is distributed diffusely on the skeleton,
when it is supported diffusely on the leaves and when it has atoms. Note that
these cases arise naturally as we can decompose
$\mu=\mu_{atoms}+\mu_{\ell}+\mu_{s}$ into measures that place mass only on
atoms, diffusely on leaves and diffusely on the branches (the tree without the
leaves) respectively.

Before doing that, we will state an elementary lemma.

######  Lemma 3.7.

Assume $X,Y,Z$ are independent random variables with laws
$\lambda_{1},\lambda_{2},\lambda_{3}$ respectively and $f$ a measurable
function. If $f(X,Y)=f(X,Z)$ $\mathbb{P}$–$a.s.$ then $f(x,Y)$ is
$\mathbb{P}$–$a.s.$ constant for $\lambda_{1}$–$a.e.$ $x$. We then have
$f(X,Y)=g(X)$ $\mathbb{P}$–$a.s.$ for some measurable function $g$.

###### Proof.

Note first that $f(x,Y)=g(x,Z)$ for $\lambda_{1}$–a.e. $x$,
$\mathbb{P}$–almost surely. Fix $x$ such that $f(x,Y)=f(x,Z)$
$\mathbb{P}$–$a.s.$ and let $f_{x}(\cdot)=f(x,\cdot)$. Then
$f_{x}(Y)=f_{x}(Z)$ almost surely. Because $Y\perp\\!\\!\\!\perp Z$,
$Y\perp\\!\\!\\!\perp f_{x}(Y)$ and hence $f_{x}(Y)\perp\\!\\!\\!\perp
f_{x}(Y)$ which implies that $f_{x}(Y)$ is $\mathbb{P}$–$a.s.$ constant –
define $g(x)$ to be this constant, i.e. $g(x)=\int f(x,y)\lambda_{2}(dy)$
which is measurable. This completes the proof because
$\lambda_{1}\big{(}\big{\\{}x\mathrel{\mathop{\mathchar
58\relax}}f(x,Y)=f(x,Z)\big{\\}}\big{)}=1$. ∎

######  Lemma 3.8.

Assume that from Proposition 3.6 we get $(\textbf{T},d,r,\mu,F)$ so that
$\textbf{T}=[0,1],r=0,\mu=Leb$ with $F$ being arbitrary. Then there exists a
decorated planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ so that the
dendritic systems constructed by Constructions 3.2 and 3.5 have the same
distribution. Here, $\psi$ is the only possible planar order for $[0,1]$ and
$\lambda$ is determined by $F$. Because $Leb$ has no atoms, $B$ is trivial.

Note that in this case $\mu$ is supported diffusely on branches. There is only
one planar order for this tree in this case: given $n$ distinct points and the
root in T, $\psi_{n}$ maps them to a discrete line segment of length $n$.

Here the sampling representation is very concise: sample $n$ uniform $iid$
points $\xi_{1},\ldots,\xi_{n}$ on $[0,1]$. For each $\xi_{i}$, sample a
Bernoulli random variable with parameter $\lambda(\xi_{i})$ independently and
attach a leaf labelled $i$ to the left of $\xi_{i}$ – if the Bernoulli random
variable equals $1$ – or to the right of $\xi_{i}$ otherwise. $T_{n}$ is then
the plane combinatorial tree spanned by $r$ and the added leaves. This means
that $T_{n}$ is a binary tree consisting of a spine with leaves hanging off
the spine left and right.

###### Proof of Lemma 3.8..

Due to the special structure of the tree and the probability measure we are
almost surely always in the case where $\\{\xi_{i}<\xi_{j}\\}$ or
$\\{\xi_{i}>\xi_{j}\\}$. This leaves us to show that on the event
$\\{\xi_{i}<\xi_{j}\\}$ we have almost surely

$p(i,j)=\begin{cases}1\quad&\text{if }U_{i}<\lambda(\xi_{i}),\\\ -1&\text{if
}U_{i}\geq\lambda(\xi_{i})\end{cases}$

for a suitable branch weight function $\lambda$.

Without loss of generality we always condition on the event
$\\{\xi_{i}<\xi_{j}\\}$ in the following. By Proposition 3.6 we have:

$p(i,j)=F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij}).$

We sample a second copy of $(\xi_{j},U_{j},U_{ij})$ independently of
$(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})$ and denote it by
$(\xi_{j}^{*},U_{j}^{*},U_{ij}^{*})$ and we restrict ourselves to the event
$\\{\xi_{i}<\xi_{j}^{*}\\}$. Due to the consistency properties of $F$, more
precisely $(F4)$, we almost surely have

$F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})=F(\xi_{i},U_{i},\xi_{j}^{*},U_{j}^{*},U_{ij}^{*}).$

Consider the family of regular conditional distribution
$\mathbb{P}(\cdot|\xi_{i}=x,\xi_{j}>\xi_{i},\xi_{j}^{*}>\xi_{i})$ under which
for all $x\in(0,1)$, both $\xi_{j}$ and $\xi_{j}^{*}$ are $Uniform((x,1))$
distributed and $U_{i},\xi_{j},U_{j},U_{ij},\xi_{j}^{*},U_{j}^{*},U_{ij}^{*}$
are independent of each other. This means we can apply Lemma 3.7 which tells
us that there exists some measurable function
$V^{\prime}\mathrel{\mathop{\mathchar 58\relax}}[0,1]^{2}\to\\{\pm 1\\}$ such
that $F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})=V^{\prime}(x,U_{i})$,
$\mathbb{P}(\cdot|\xi_{i}=x,\xi_{j}>\xi_{i},\xi_{j}^{*}>\xi_{i})$–almost
surely for $Leb$–almost every $x$. Integrating over $x$ and reversing the
roles for $i$ and $j$ already gives us the following description of $p$:

$p(i,j)=\begin{cases}V^{\prime}(\xi_{i},U_{i})\quad&\text{if}\quad\xi_{i}<\xi_{j},\\\
V^{\prime}(\xi_{j},U_{j})\quad&\text{if}\quad\xi_{j}<\xi_{i}.\end{cases}$

Let us now define the branch weight function $\lambda$ by
$\lambda(x)=\mathbb{P}(V^{\prime}(x,U)=1)$ for $x\in[0,1]$. We use this to
define:

$\tilde{p}(i,j)=\begin{cases}V(\xi_{i},U_{i})\quad&\text{if}\quad\xi_{i}<\xi_{j},\\\
V(\xi_{j},U_{j})\quad&\text{if}\quad\xi_{j}<\xi_{i}.\end{cases}$

where $V(x,u)=\mathds{1}_{\lambda(x)<u}-\mathds{1}_{\lambda(x)>u}$. If we
manage to show

$\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}1\leq i\neq j\leq
n\\}\overset{d}{=}\\{\tilde{p}(i,j)\mathrel{\mathop{\mathchar 58\relax}}1\leq
i\neq j\leq n\\}$ (3.1)

for every $n\in\mathbb{N}$ then we have completed the proof the lemma. To this
end, fix $2\leq n\in\mathbb{N}$. Denote
$\mathbb{P}(\cdot|\xi_{1}<\ldots<\xi_{n},\xi_{1},\ldots,\xi_{n})$ by
$\mathbb{P}^{\xi}$ and let $a_{1},\ldots,a_{n-1}\in\\{\pm 1\\}^{n-1}$. To show
(3.1), it suffices to show that we $\mathbb{P}^{\xi}$–a.s. have

$\mathbb{P}^{\xi}\big{(}\forall i<n\mathrel{\mathop{\mathchar 58\relax}}\
p(i,i+1)=a_{i}\big{)}=\mathbb{P}^{\xi}\big{(}\forall
i<n\mathrel{\mathop{\mathchar 58\relax}}\ \tilde{p}(i,i+1)=a_{i}\big{)}.$
(3.2)

Indeed, assume we are given $b=\\{b_{ij}\\}_{i,j\leq n,i\neq j}\in\\{\pm
1\\}^{n(n-1)}$ with $b_{ij}=-b_{ji}$ and $b_{ij}=b_{in}$ for $i<n$. If we are
given $b$ that does not satisfy these assumptions, then

$\mathbb{P}^{\xi}\big{(}\forall i,j\leq n,i\neq j\mathrel{\mathop{\mathchar
58\relax}}\ p(i,j)=b_{ij}\big{)}=0,$

due to $b$ violating the consistency properties required in $(P1)$ or $(P4)$.
The same holds for $\tilde{p}$. Now if $b$ satisfies the assumptions stated
above, we then have

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i,j\leq n,i\neq
j\mathrel{\mathop{\mathchar 58\relax}}\
p(i,j)=b_{ij}\big{)}\overset{(P1)}{=}\mathbb{P}^{\xi}\big{(}\forall i,j\leq
n,i<j\mathrel{\mathop{\mathchar 58\relax}}\
p(i,j)=b_{ij}\big{)}\overset{(P4)}{=}\mathbb{P}^{\xi}\big{(}\forall
i<n\mathrel{\mathop{\mathchar 58\relax}}\ p(i,i+1)=b_{in}\big{)},$

where both equalities hold $\mathbb{P}$–almost surely. We can apply $(P4)$
here because for $i+1<j$ we have $(j,(i+1))\prec(j,j)$ due to
$\xi_{i}<\xi_{i+1}<\xi_{j}$, hence $p(i,i+1)=p(i,(j,i+1))=p(i,j)$. The same is
true for $\tilde{p}$, which means that it suffices to only check (3.2).
Consider now (3.2), due to our definition of $\lambda$ and the independence of
$U_{1},\ldots,U_{n}$, we $\mathbb{P}$–almost surely have

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i<n\mathrel{\mathop{\mathchar
58\relax}}\ p(i,n)=a_{i})$ $\displaystyle=\mathbb{P}^{\xi}\big{(}\forall
i<n\mathrel{\mathop{\mathchar
58\relax}}V^{\prime}(\xi_{i},U_{i})=a_{i}\big{)}$
$\displaystyle=\prod_{i=1}^{n-1}\mathbb{P}^{\xi}\big{(}V^{\prime}(\xi_{i},U_{i})=a_{i}\big{)}$
$\displaystyle=\prod_{i=1}^{n-1}\big{(}\lambda(\xi_{i})\mathds{1}_{a_{i}=1}+(1-\lambda(\xi_{i}))\mathds{1}_{a_{i}=-1}\big{)}$
$\displaystyle=\prod_{i=1}^{n-1}\mathbb{P}^{\xi}\big{(}V(\xi_{i},U_{i})=a_{i}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i<n\mathrel{\mathop{\mathchar
58\relax}}\ \tilde{p}(i,n)=a_{i}\big{)}.$

This implies (3.1) which completes the proof of the lemma. ∎

As the second warm–up case, we consider the case where T is arbitrary but
$\mu$ is supported only on the leaves of T. In this case $\lambda$ and $B$ are
trivial, but we do need to define $\psi$.

######  Lemma 3.9.

Assume that from Proposition 3.6 we get $(\textbf{T},d,r,\mu,F)$ so that $\mu$
is supported diffusely on the leaves of T. Then there exists a decorated
planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ so that the dendritic
systems constructed by Constructions 3.2 and 3.5 have the same distribution.
$\lambda$ and $B$ are trivial.

###### Proof.

Our main concern is to define the planar order $\psi$, recall the definition
from Definition 2.2. More concretely, we need to define
$\psi_{n}(x_{1},\ldots,x_{n})$ for any totally unordered
$x=(x_{1},\ldots,x_{n})\in\textbf{T}^{n}$. Note that we need to do this for
all $(x_{1},\ldots,x_{n})$ and not just on the support of $\mu$. Hence we fix
totally unordered $(x_{1},\ldots,x_{n})\in\textbf{T}^{n}$.

We let $\textbf{S}_{i}$ be the subtree corresponding to $x_{i}$ in the
following sense: let $\overline{x_{i}}$ be the most recent branchpoint in
$span(r,x_{1},\ldots,x_{n})$. Let $y_{i}$ be the middle point of the segment
$[\overline{x_{i}},x_{i}]_{\textbf{T}}$. We set
$\textbf{S}_{i}=F_{\textbf{T}}(y_{i})$, the fringe subtree of $y_{i}$, see
Figure 10 for an illustration. The reason for using $F_{\textbf{T}}(y_{i})$
instead of $F_{\textbf{T}}(x_{i})$ is that we always have
$\mu(F_{\textbf{T}}(y_{i}))>0$ but not necessarily
$\mu(F_{\textbf{T}}(x_{i}))>0$. This is true because we have
$\textbf{T}=span(supp(\mu))$ by Proposition 3.6. Note that if $x_{i}$ is a
leaf, then $\mu(F_{\textbf{T}}(x_{i}))=\mu(\\{x_{i}\\})=0$ because we assumed
$\mu$ to be diffuse.

Define now
$\mathbb{P}^{x}=\bigotimes_{i=1}^{n}\frac{1}{\mu(\textbf{S}_{i})}\mu|_{\textbf{S}_{i}}$.
Sampling $(\xi_{1},\ldots,\xi_{n})$ from $\mathbb{P}^{x}$ is equivalent to
sampling $(\xi_{1},\ldots,\xi_{n})$ from $\mathbb{P}$ and conditioning on
$\\{\xi_{i}\in\textbf{S}_{i}\\}$ for every $i$. Using
$(\xi_{1},\ldots,\xi_{n})$ sampled from $\mathbb{P}^{x}$ in Construction 3.1
and 3.5 (instead of $i.i.d.$ $\mu$ samples) yields a random dendritic system
$\mathcal{D}_{n}=([n],\sim_{n},\preceq_{n},p_{n})$ with leaves labelled by
$[n]$. We claim that $\mathcal{D}_{n}$ is in fact almost surely constant. If
this is the case, then $\mathcal{D}_{n}$ will correspond to a non–random tree
$T_{n}$ by Lemma 2.8 which is a combinatorial, leaf–labelled and plane tree.
We then set

$\psi_{n}(x_{1},\ldots,x_{n})=T_{n}.$

Next we need to prove the claim than $\mathcal{D}_{n}$ is almost surely
constant. Let $(\xi_{i},U_{i},U_{ij};i,j\leq n)$ be the random variables
involved in the construction of $\mathcal{D}_{n}$, let
$(\xi_{i}^{*},U_{i}^{*},U_{ij}^{*};i,j\leq n)$ be an independent copy with the
same distribution, extending the probability space. For every $i\neq j$ we
have

$F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})=F(\xi_{i}^{*},U_{i}^{*},\xi_{j}^{*},U_{j}^{*},U_{ij}^{*})$

due to the consistency properties $(F2)$ and $(F3)$ of Proposition 3.6 and the
fact that $\xi_{i},\xi_{i}^{*}\in\textbf{S}_{i}$ whereas
$\xi_{j},\xi_{j}^{*}\in\textbf{S}_{j}$. Informally, sampling once from
$\textbf{S}_{i}$ and $\textbf{S}_{j}$ already determines which subtree is to
the left of the other subtree, hence the second sample must agree with the
left–right prescription of the first sample. More formally,
$(\xi_{i},U_{i},U_{ij};i,j\leq n)$ and
$(\xi_{i}^{*},U_{i}^{*},U_{ij}^{*};i,j\leq n)$ are independent and hence $F$
restricted to
$\textbf{S}_{i}\times[0,1]\times\textbf{S}_{j}\times[0,1]\times[0,1]$ is
$\mathbb{P}^{x}$–almost surely constant for any $i\neq j$ by Lemma 3.7. This
proves the claim that $\mathcal{D}_{n}$ is constant and thus yields the map
$\psi_{n}$. By construction we also have the property that
$\psi_{n}(x_{1},\ldots,x_{n})$ as non–plane combinatorial tree is the
combinatorial tree corresponding to $\textrm{span}(r,x_{1},\ldots,x_{n})$.

Figure 10: The subsets of T involved in the proof of Lemma 3.9.

What remains to be shown is that $\psi_{n}(x_{1},\ldots,x_{n})$ embeds into
$\psi_{n+1}(x_{1},\ldots,x_{n},y)$ for any $y\in\textbf{T}$ such that
$(x_{1},\ldots,x_{n},y)$ is still totally unordered. Let
$(\textbf{S}_{1},\ldots,\textbf{S}_{n})$ denote the trees used in the
construction of $\psi_{n}(x_{1},\ldots,x_{n})$ and
$(\textbf{S}_{1}^{\prime},\ldots,\textbf{S}_{n}^{\prime},\textbf{S}_{y})$ the
trees used in the construction of $\psi_{n+1}(x_{1},\ldots,x_{n},y)$.

We need to observe that in general we have
$\textbf{S}_{i}\neq\textbf{S}_{i}^{\prime}$. This is because either
$y\in\textbf{S}_{i}$ for some $i$ or because including $y$ introduces new
branchpoints in $\textrm{span}(r,x_{1},\ldots,x_{n},y)$ which change
$\overline{x_{i}}$ and hence $\textbf{S}_{i}$. Nevertheless, we always have

$\textbf{S}_{i}^{\prime}\subseteq\textbf{S}_{i}\quad\forall i\leq n.$

Recall that in the first part of the proof we sampled $\xi_{i}$ from
$\mu_{i}$, i.e. from $\mu$ conditioned on $\xi_{i}\in\textbf{S}_{i}$ to
determine $\psi_{n}(x_{1},\ldots,x_{n})$. It is easy to see that we can a
posteriori replace $\textbf{S}_{i}$ with $\textbf{S}_{i}^{\prime}$ in the
construction and still obtain the same $\psi_{n}(x_{1},\ldots,x_{n})$. This is
because we concluded that $F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})$ is almost
surely constant for every $i,j\leq n$ so we can condition $\xi_{i},i\leq n$ to
be in the smaller sets $\textbf{S}^{\prime}_{i}$ for every $i\leq n$ and
deduce the required constancy on these sets.

There is a distinct advantage to using $(\textbf{S}_{i}^{\prime},i\leq n)$
instead of $(\textbf{S}_{i},i\leq n)$ as these are the subsets of T used in
the construction of $\psi_{n+1}(x_{1},\ldots,x_{n},y)$. This then yields the
embedding of $\psi_{n}(x_{1},\ldots,x_{n})$ into
$\psi_{n+1}(x_{1},\ldots,x_{n},y)$. There is a unique edge or branchpoint in
$\psi_{n}(x_{1},\ldots,x_{n})$ to which we attach the leaf corresponding to
$y$, determined by where $\overline{y}$ is located in
$\textrm{span}(r,x_{1},\ldots,x_{n})$ because Definition 2.2 requires that
$\psi_{n+1}(x_{1},\ldots,x_{n},y)$ without the planar order is the
combinatorial tree corresponding to $\textrm{span}(r,x_{1},\ldots,x_{n},y)$.
There also is a determined way for the planar order of the new leaf
corresponding to $y$ which is compatible with the planar order of
$\psi_{n}(x_{1},\ldots,x_{n})$ because we used the same sets
$\textbf{S}_{i},i\leq n$, respectively identically distributed random
variables, to construct the planar orders.

To conclude the proof of this lemma, note that the choice of $\lambda$ is
trivial. Indeed, recall that we view $\lambda$ as an element of
$L^{1}(\mu_{s})$. Here $\mu_{s}=0$, so $L^{1}(\mu_{s})$ contains only a single
element. Similarly, we need not define $B$ as $\mu$ does not have any atoms,
hence $B$ is trivial.

We have to check that the distribution of the dendritic system constructed via
Constructions 3.1 and 3.2 using $\psi$ is the same as the distribution of the
dendritic system in Proposition 3.6. By construction of $\psi$, this is the
case on the event where $(\xi_{i},i\geq 1)$ is a totally unordered sequence in
T. Because $\mu$ is diffusely supported on the leaves of T, this happens with
probability $1$. This concludes the proof. ∎

It is important to note that we used the fact that $\mu$ is supported
diffusely on the leaves only in the conclusion of the proof but not in the
construction of $\psi$. Hence we can also repeat this construction in the
general setting of Proposition 3.6.

######  Corollary 3.10.

In the setting of Proposition 3.6, $F$ induces a deterministic planar order
$\psi$ for T. In the context of Construction 3.1, consider the event that
$(\xi_{i};i\in I)$ are totally unordered for some finite set
$I\subset\mathbb{N}$. Then on this event the planarity function $p$
constructed in Construction 3.2 (which uses this $\psi$) restricted to $I$ has
the same distribution as the planarity function of Construction 3.5 restricted
to $I$.

As the third warm–up case, we consider the case where T is a single point.
Note that in that case $\lambda$ and $B$ are necessarily trivial and there is
again only one choice for the planar order $\psi$.

######  Lemma 3.11.

Assume that from Proposition 3.6 we get $(\textbf{T},d,r,\mu,F)$ so that
$\textbf{T}=\\{0\\}$, $r=0$ and $\mu=\delta_{0}$. Then there exists a
decorated planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ so that the
dendritic systems constructed by Constructions 3.2 and 3.5 have the same
distribution. $\psi,\lambda$ and $B$ need not be specified due to the special
structure of T.

###### Proof.

The only tree with $n$ leaves that can arise in this case is the tree where
all $n$ leaves are attached directly to the root. This tree also has a unique
planar order. We are left with distributing the leaf labels, but due to
exchangeability they form a uniform permutation on $\\{1,\ldots,n\\}$. This
means we have to assign them in a consistent way which can be realised by
$p(i,j)=\mathds{1}_{U_{i}<U_{j}}-\mathds{1}_{U_{j}>U_{i}}$. ∎

Finally, we will prove Proposition 3.3 in the general case by combining the
ideas of the preceding lemmas.

###### Proof of Proposition 3.3..

Let $(\textbf{T},d,r,\mu,F)$ as in Proposition 3.6. The proof consists of two
steps: constructing the planar order $\psi$, the branch weight function
$\lambda$, the branchpoint weight function $B$, and then checking that the
distribution of the sampled dendritic system agrees with the distribution of
Proposition 3.6.

Step $1$: constructing $(\psi,\lambda,B)$. First, we define
$\psi_{n}(x_{1},\ldots,x_{n})$ for any totally unordered
$(x_{1},\ldots,x_{n})\in\textbf{T}$ as in the proof of Lemma 3.9 and Corollary
3.10. This is then extended to arbitrary $(x_{1},\ldots,x_{n})$ by part $4$ of
Definition 2.2.

Recall the definition of a branch weight function $\lambda$ from the
introduction. Hence, fix $x\in supp(\mu_{s})$, i.e. $x$ is located on the
diffuse mass on the branches. By our convention, we can assume $\deg(x)=2$.
Define $\mu^{x}=\frac{1}{\mu(F_{\textbf{T}}(x))}\mu|_{F_{\textbf{T}}(x)}$,
$\mu$ restricted to $F_{\textbf{T}}(x)$ and normalised. Let
$U_{1},U_{2},U_{3}$ be independent, uniform $[0,1]$ random variables and let
$\xi$ be an independent $\mu^{x}$–distributed random variable. $\xi$ can also
be seen as a $\mu$–distributed random variable conditioned on $\xi\in
F_{\textbf{T}}(x)$. We can now define $\lambda(x),$

$\lambda(x)=\mathbb{P}\big{(}F(x,U_{1},\xi,U_{2},U_{3})=1\big{)}.$ (3.3)

Note that this defines a measurable function $\lambda$ because $F$ is
measurable. On an informal level, $\lambda(x)$ is the probability that a leaf
attached to $x$ will be to the left of the subtree $F_{\textbf{T}}(x)$ of $x$.

Recall the definition of branchpoint weight function $B$ from the
introduction. Fix an atom $a$ of $\mu$. We need to define
$\beta_{a}\mathrel{\mathop{\mathchar 58\relax}}[0,1]\to[0,1]$ so that
$\beta_{a}$ is non–decreasing, right–continuous and the cardinality of the
range of $\beta_{a}$ is at most $\deg a\in\mathbb{N}\cup\\{\infty\\}$. Also,
we want $\beta_{a}$ to be piece–wise constant in the following sense:
enumerate the connected components of $F_{\textbf{T}}(a)\backslash\\{a\\}$ by
$\textbf{S}_{1},\textbf{S}_{2},\ldots$ and let
$c_{i}=\sum\mu(\textbf{S}_{j})/\sum_{k\geq 1}\mu(\textbf{S}_{k})$ where the
first sum ranges over all $j$ such that $\textbf{S}_{j}$ is left of
$\textbf{S}_{i}$ (see Definition 2.5) and $\textbf{S}_{j}\neq\textbf{S}_{i}$.
We then impose that $\beta_{a}$ is constant on
$[c_{i},\inf_{c_{j}>c_{i}}c_{j})$ for every $i$.

Fix $i$ and consider
$\mu^{i}=\frac{1}{\mu(\textbf{S}_{i})}\mu|_{\textbf{S}_{i}}$, i.e. $\mu$
restricted to $\textbf{S}_{i}$ and normalised. Let $U_{1},U_{2},U_{3}$ be
independent, uniform $[0,1]$ random variables and let $\xi^{i}$ be an
independent $\mu^{i}$–distributed random variable. $\xi$ can also be seen as
$\mu$–distributed random variable conditioned on $\xi^{i}\in\textbf{S}_{i}$.
We can now define

$b_{i}=\mathbb{P}\big{(}F(a,U_{1},\xi^{i},U_{2},U_{3})=1\big{)}.$ (3.4)

On an informal level, this corresponds to the probability that a leaf attached
to $a$ is left of the subtree $\textbf{S}_{i}$. We use this to define
$\beta_{a}$. On the interval $[c_{i},\inf_{c_{j}>c_{i}}c_{j})$, we set
$\beta_{a}$ to be $b_{i}$,

$\beta_{a}\big{|}_{[c_{i},\inf_{c_{j}>c_{i}}c_{j})}=b_{i}.$

For completeness, we set $\beta_{a}(1)=\sup_{j\in\mathbb{N}}b_{j}$ and
$\beta_{a}(x)=\lim_{z\downarrow x}\beta_{a}(z)$ for every $x\in[0,1)$ where
$\beta_{a}(x)$ has not been defined yet. All the claimed properties of
$\beta_{a}$ (as described in Construction 1.7) follow from this construction,
in particular note that $\beta_{a}$ is non–decreasing due to the consistency
property $(F2)$.

Step $2$: equivalence in distribution. We need to check that the dendritic
system $\mathcal{D}^{*}=(\mathbb{N},\sim^{*},\prec^{*},p^{*})$ constructed by
Constructions 3.1 and 3.2 using $(\psi,\lambda,B)$ constructed in steps
$1$–$3$ has the same distribution as the dendritic system
$\mathcal{D}=(\mathbb{N},\sim,\prec,p)$ constructed by Constructions 3.1 and
3.5. We consider them under a partial coupling which is obtained by using the
same sequence $(\xi_{i},i\leq 1)$ of $i.i.d.$ $\mu$–random variables for
Construction 3.1. This means that $\sim=\sim^{*}$ and $\preceq=\preceq^{*}$
$\mathbb{P}$–almost surely. Condition on $(\xi_{i},i\leq n)$, let
$\mathbb{P}^{\xi}$ be a regular conditional probability of $\mathbb{P}$ given
$(\xi_{i},i\geq n)$. It now suffices to check that the restrictions of
$\mathcal{D}$ and $\mathcal{D}^{*}$ to the leaves labelled by $[n]$ have the
same distribution for all $n\in\mathbb{N}$. Due to the coupling, it suffices
to show that $\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}i\neq j\in[n]\\}$
and $\\{p^{*}(i,j)\mathrel{\mathop{\mathchar 58\relax}}i\neq j\in[n]\\}$ have
the same distribution under $\mathbb{P}^{\xi}$, $\mathbb{P}$–almost surely.

We partition $[n]$: Choose a set $I_{1}\subset[n]$ such that $(\xi_{i},i\in
I_{1})$ is totally unordered and such that $\textrm{span}(r,\xi_{i},i\in
I_{1})=\textrm{span}(r,\xi_{i},i\in[n])$. Next, let

$I_{2}=\left\\{i\in[n]\mathrel{\mathop{\mathchar
58\relax}}\xi_{i}\in\textrm{supp}(\mu_{s})\quad\text{and}\quad i\notin
I_{1}\right\\}.$

Lastly, for every atom $a$ of $\mu$, we let

$I_{3}^{a}=\left\\{i\in[n]\mathrel{\mathop{\mathchar
58\relax}}\xi_{i}=a\quad\text{and}\quad i\notin I_{1}\right\\}.$

Figure 11: The three sets $I_{1},I_{2}$ and $I_{3}$. The big, blue circles
signify atoms of T.

By construction, $I_{1},I_{2}$ and $(I_{3}^{a},a\ \text{atom})$ are disjoint
and $I_{1}\cup I_{2}\cup\bigcup_{a}I_{3}^{a}=[n]$. See Figure 11 for an
illustration of these sets. We show

$\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in[n];i\neq
j\\}\overset{d}{=}\\{p^{*}(i,j)\mathrel{\mathop{\mathchar
58\relax}}i,j\in[n];i\neq j\\}\quad\mathbb{P}-a.s.$ (3.5)

in three steps. First with $[n]$ replaced by $I_{1}$, then by $I_{1}\cup
I_{2}$ and lastly for $[n]$ itself. We do these in three steps – _a,b,c_ – for
$I_{1}$, $I_{1}\cup I_{2}$ and $[n]$ respectively.

_Step $2a$._ By construction, $\\{\xi_{i},i\in I_{1}\\}$ is a totally
unordered set and hence

$\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in I_{1};i\neq
j\\}\overset{d}{=}\\{p^{*}(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in
I_{1};i\neq j\\}\quad\mathbb{P}-a.s.$ (3.6)

by Corollary 3.10.

_Step $2b$._ Consider now $I_{2}$. For $i\in I_{2}$ we let
$s(i)=\min\\{i^{\prime}\mathrel{\mathop{\mathchar 58\relax}}i^{\prime}\in
I_{1},\xi_{i}<\xi_{i^{\prime}}\\}$ – by construction of $I_{2}$ the set
$\\{i^{\prime}\mathrel{\mathop{\mathchar 58\relax}}i^{\prime}\in
I_{1},\xi_{i}<\xi_{i^{\prime}}\\}$ is never empty for every $i\in I_{2}$ and
thus $s(i)$ is well–defined. The idea behind considering $\xi_{s(i)}$ is
similar to the proof of Lemma 3.8, it suffices to consider only one other leaf
to determine the orientation of leaf $i$. Here we use $s(i)$, in the lemma we
used the smallest leaf above. Let $i,j\in I_{2}$ with $i\neq j$. We then have
$3$ cases: either $\xi_{i}<\xi_{j}$, $\xi_{j}<\xi_{i}$ or
$\xi_{i}\nleq\xi_{j},\xi_{j}\nleq\xi_{i}$. If $\xi_{i}<\xi_{j}$, then
$(i,j)=(i,s(i))\prec(j,s(i))$. By $(P4)$ we then almost surely have

$p(i,j)=p(i,(j,s(i))=p(i,s(i)).$ (3.7)

Similarly, if $\xi_{j}<\xi_{i}$ we almost surely have
$p(i,j)=p(s(j),j)=-p(j,s(j))$ where the second equality follows from $(P1)$.
If $\xi_{i}\nleq\xi_{j}$ and $\xi_{j}\nleq\xi_{i}$ we have
$(i,j)=(s(i),s(j))\prec(i,s(i))$ and $(i,j)\prec(j,s(j))$. Hence we almost
surely have

$p(i,j)=p(i,s(j))=p(s(i),s(j)),$ (3.8)

again by $(P4)$. The same reasoning works for $p^{*}$ as well, so that we have
analogues of (3.7) and (3.8) for $p^{*}$ as well. This implies that to show

$\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in I_{1}\cup I_{2};i\neq
j\\}\overset{d}{=}\\{p^{*}(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in
I_{1}\cup I_{2};i\neq j\\}\quad\mathbb{P}-a.s.,$ (3.9)

it suffices to show that

$\\{p(i,j)\mathrel{\mathop{\mathchar 58\relax}}i,j\in
I_{1}\mathrel{\mathop{\mathchar 58\relax}}i\neq j\ \text{or}\ i\in
I_{2},j=s(i)\\}\overset{d}{=}\\{p^{*}(i,j)\mathrel{\mathop{\mathchar
58\relax}}i,j\in I_{1}\mathrel{\mathop{\mathchar 58\relax}}i\neq j\ \text{or}\
i\in I_{2},j=s(i)\\}\quad\mathbb{P}-a.s..$ (3.10)

Consider now $i\in I_{2}$ and $j=s(i)\in I_{1}$. Let $\pi(\xi_{j})$ be either
the branchpoint in $\textrm{span}(r,\xi_{\ell};\ell\in I_{1})$ closest to
$\xi_{j}$ or the closest $\xi_{k},k\in[n]$ – whichever is closer. Denote by
$\tilde{\xi_{j}}$ the midpoint of the interval $[\pi(\xi_{j}),\xi_{j}]$. Let
$\textbf{S}_{j}=F_{\textbf{T}}(\tilde{\xi_{j}})$, by construction
$\xi_{j}\in\textbf{S}_{j}$ and $\xi_{i}\notin\textbf{S}_{j}$. Now let
$\zeta_{j},\zeta_{j}^{\prime}$ be sampled from
$\frac{1}{\mu(\textbf{S}_{j})}\mu|_{\textbf{S}_{j}}$ – we assume that they are
all independent under $\mathbb{P}^{\xi}$ and independent of all uniform
variables. Here we note again that $\mu(\textbf{S}_{j})>0$, but not
necessarily $\mu(F_{\textbf{T}}(\xi_{j}))>0$. Let
$V_{j},V_{j}^{\prime},V_{ij},V_{ij}^{\prime}$ be additional uniform random
variables. We then $\mathbb{P}^{\xi}$–almost surely have

$p(i,j)=F(\xi_{i},U_{i},\xi_{j},U_{j},U_{ij})=F(\xi_{i},U_{i},\zeta_{j},V_{j},V_{ij})=F(\xi_{i},U_{i},\zeta_{j}^{\prime},V_{j}^{\prime},V_{ij}^{\prime}).$

The first equality is how $p(i,j)$ is constructed, the other two inequalities
follow from $\xi_{i},\zeta_{i},\zeta_{i}^{\prime}\in\textbf{S}_{i}$ and the
consistency properties $(F3)$ and $(F4)$. By Lemma 3.7, this means that there
is a function $G_{i}$ such that

$p(i,s(i))=G_{i}(\xi_{i},U_{i}).$ (3.11)

Note that this is how we have defined $\lambda(\xi_{i})$ in (3.3),
$\lambda(\xi_{i})=\mathbb{P}^{\xi}(G_{i}(\xi_{i},U_{i})=1)$. Now let
$\gamma=(\gamma_{ij})_{i,j\in I_{1}\cup I_{2}}\in\\{\pm 1\\}^{I_{1}\cup
I_{2}}$ be in such a way that

$\mathbb{P}^{\xi}\big{(}\forall i,j\in I_{1}\cup
I_{2}\mathrel{\mathop{\mathchar 58\relax}}i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}>0.$

Informally, this means we only consider $c$ which does not break the
consistency relations of $p$ in an obvious way, for example by not satisfying
$\gamma_{ij}=-\gamma_{ji}$. Any such $\gamma$ would have probability $0$, both
for the above expression and the same expression with $p$ replaced by $p^{*}$.
Using the observations we have made so far, i.e. we only need to show (3.10)
for (3.9) and (3.11), we get

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i,j$ $\displaystyle\in I_{1}\cup
I_{2};i\neq j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in
I_{2}\mathrel{\mathop{\mathchar 58\relax}}p(i,s(i))=\gamma_{i,s(i)};\forall
i,j\in I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in
I_{2}\mathrel{\mathop{\mathchar
58\relax}}p(i,s(i))=\gamma_{i,s(i)}\big{|}\forall i,j\in I_{1};i\neq
j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{1};i\neq j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in
I_{2}\mathrel{\mathop{\mathchar
58\relax}}G_{i}(\xi_{i},U_{i})=\gamma_{i,s(i)}\big{|}\forall i,j\in
I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{1};i\neq j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\bigg{(}\prod_{i\in
I_{2}}\mathbb{P}^{\xi}\big{(}G_{i}(\xi_{i},U_{i})=\gamma_{i,s(i)}\big{)}\bigg{)}\mathbb{P}^{\xi}\big{(}\forall
i,j\in I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}$ $\displaystyle=(*).$

In the last step, we have used the independence of the $U_{i},i\in I_{2}$. As
we have noted above, the distribution of $G_{i,s(i)}(\xi_{i},U_{i})$ is the
same as the distribution of $p^{*}(i,j)$. Combining this with (3.6), we have

$(*)=\prod_{i\in
I_{2}}\mathbb{P}^{\xi}\big{(}p^{*}(i,s(i))=\gamma_{i,s(i)}\big{)}\mathbb{P}^{\xi}\big{(}\forall
i,j\in I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}=(**).$

We reduce this expression with the same reasoning as above, this time for
$p^{*}$ instead of $p$,

$\displaystyle(**)$ $\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in
I_{2}\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,s(i))=\gamma_{i,s(i)}\big{|}\forall i,j\in I_{1};i\neq
j\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in
I_{2}\mathrel{\mathop{\mathchar 58\relax}}p^{*}(i,s(i))=\gamma_{ij};\forall
i,j\in I_{1};i\neq j\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij})$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i,j\in I_{1}\cup I_{2};i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}.$

Because $\gamma$ was arbitrary, we have shown (3.9).

_Step $2c$._ Lastly, we want to show (3.5), given (3.9). Fix an atom $a$ such
that $I_{3}^{a}\neq\emptyset$. Note there can be the case where there is $i\in
I_{1}$ with $\xi_{i}=a$. To deal with this case and to include this index, we
define $\tilde{I}_{3}^{a}=\\{i\mathrel{\mathop{\mathchar
58\relax}}\xi_{i}=a\\}$. Further, there are $d(a)\geq 1$ and
$i_{1}^{a},\ldots,i_{d(a)}^{a}\in I_{1}$ such that $a\leq\xi_{i_{j}^{a}}$ for
$1\leq j\leq d(a)$ and such that $\textrm{span}(r,\xi_{i};i\in[n])$ and
$\textrm{span}(r,\xi_{i_{1}^{a}},\ldots,\xi_{i^{a}_{d(a)}})$ are the same in a
small neighbourhood of $a$. This means that we choose as many of the leaves in
$\textrm{span}(r,\xi_{i};i\in I_{1})$ that sit above $a$ as needed to realise
the degree of $a$ in $\textrm{span}(r,\xi_{i};i\in[n])$. The case of $d(a)=1$
can also happen if there is $i\in I_{1}$ with $\xi_{i}=a$. We can choose them
in such a way that $p(i^{a}_{k},i^{a}_{k+1})=1$ for $k\leq d(a)-1$, i.e. they
are indexed from left to right in an increasing manner. Let now be
$i\in\tilde{I}_{3}^{a}$ and $j\in[n]$, i.e. a leaf which is attached to $a$
and another leaf. We consider $p(i,j)$. There are three cases, $\xi_{j}<a$, or
$a<\xi_{j}$, or $a\nless\xi_{j}$ and $\xi_{j}\nless a$. We show that in all
three cases we have

$p(i,j)=p(i^{a}_{k},j),$ (3.12)

$\mathbb{P}^{\xi}$–almost surely for an appropriate choice of $1\leq k\leq
d(a)$. If $\xi_{j}<a$ or if $a\nless\xi_{j},\xi_{j}\nless a$, we choose
$i_{k}^{a}=i_{1}^{a}$ – (3.12) then holds by the consistency property $(P4)$
of $p$. If $a<\xi_{j}$, then there exists some $k$ such that $\xi_{j}$ and
$\xi_{i^{a}_{k}}$ are in the same subtree of $a$. (3.12) again holds by
$(P4)$. This means that for an appropriate $\gamma=(\gamma_{ij})_{i\neq
j\in[n]}\in\\{\pm 1\\}^{n(n-1)}$ that does not violate the consistency
conditions we have

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i,j\in[n],i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)$
$\displaystyle=\gamma_{ij}\big{)}=\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{1}\cup I_{2},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij};$ $\displaystyle\forall a\forall
i\in\tilde{I}_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}p(i,i^{a}_{k})=\gamma_{i,i_{k}^{a}};\forall a\forall
i,j\in\tilde{I}_{3}^{a},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}.$ (3.13)

The same statement holds if we replace $p$ by $p^{*}$. Note that in the case
where there is $i\in I_{1}$ with $\xi_{i}=a$ there is some redundancy in the
above statement. There we have $d(a)=1$ and $i_{1}^{a}\in\tilde{I}_{3}^{a}$.

Consider the case where $a<\xi_{i_{k}^{a}}$ for all $k\leq d(a)$ (this is true
for all $k$ unless $d(a)=1$ and $\xi_{i_{1}^{a}}=a$). Then every $k$
corresponds to a subtree $\textbf{S}_{k}$ of $a$, see Definition 1.3 for the
relevant definition. We necessarily have $\mu(\textbf{S}_{k})>0$ for every
$1\leq k\leq d(a)$. Let $\zeta_{k},\zeta_{k}^{\prime}$ be sampled from
$\frac{1}{\mu(S_{k})}\mu|_{S_{k}}$ and let
$V_{k},V_{k}^{\prime},V_{ik},V_{ik}^{\prime}$ be uniform random variables, all
of them are assumed to be independent under $\mathbb{P}^{\xi}$ and independent
of any other uniform random variables. Let $i\in I_{3}^{a}$, we then
$\mathbb{P}^{\xi}$–almost surely have

$p(i,i_{k}^{a})=F(a,U_{i},\xi_{i_{k}^{a}},U_{i_{k}^{a}},U_{i,i_{k}^{a}})=F(a,U_{i},\zeta_{k},V_{k},V_{ik})=F(a,U_{i},\zeta_{k}^{\prime},V_{k}^{\prime},V_{ik}^{\prime}).$

The first equality is Construction 3.5, the latter two equalities follow from
the consistency properties $(F3)$ and $(F4)$. By Lemma 3.7 we get that there
is a function $G^{a}_{k}$ such that $\mathbb{P}^{\xi}$–almost surely

$p(i,i_{k}^{a})=G^{a}_{k}(U_{i}).$

Using this, we continue the considerations of (3.13). We restrict ourselves to
the case where $I_{3}^{a}=\tilde{I}_{3}^{a}$.

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i,j\in[n],$ $\displaystyle i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i,j\in I_{1}\cup I_{2},i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij};\forall a\forall i\in
I_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}p(i,i^{a}_{k})=\gamma_{i,i_{k}^{a}};$
$\displaystyle\quad\quad\forall a\forall i,j\in I_{3}^{a},i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall a\forall i\in I_{3}^{a}\forall
k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}p(i,i^{a}_{k})=\gamma_{i,i_{k}^{a}};\forall a\forall i,j\in
I_{3}^{a},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{|}$ $\displaystyle\quad\quad\forall i,j\in
I_{1}\cup I_{2},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{1}\cup I_{2},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\prod_{a}\mathbb{P}^{\xi}\big{(}\forall i\in I_{3}^{a}\forall
k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}G_{k}^{a}(U_{i})=\gamma_{i,i_{k}^{a}};\forall i,j\in I_{3}^{a},i\neq
j\mathrel{\mathop{\mathchar
58\relax}}F(a,U_{i},a,U_{j},U_{ij})=\gamma_{ij}\big{)}$
$\displaystyle\quad\quad\cdot\mathbb{P}^{\xi}\big{(}\forall i,j\in I_{1}\cup
I_{2},i\neq j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
(3.14)

For the last equality, we have used that due to (3.5), the uniform variables
used at different atoms are independent because for $a\neq a^{\prime}$ the
sets $I_{3}^{a}$ and $I_{3}^{a^{\prime}}$ are disjoint. Consider now

$\mathbb{P}^{\xi}\big{(}\forall i\in I_{3}^{a}\forall k\leq
d(a)\mathrel{\mathop{\mathchar
58\relax}}G_{k}^{a}(U_{i})=\gamma_{i,i_{k}^{a}};\forall i,j\in I_{3}^{a},i\neq
j\mathrel{\mathop{\mathchar
58\relax}}F(a,U_{i},a,U_{j},U_{ij})=\gamma_{ij}\big{)},$

for a fixed atom $a$.

Note that we have defined the thresholds of $\beta_{a}$ exactly so that
$\mathbb{P}(G_{k}^{a}(U_{i})=1)=b_{k}$, compare to (3.4). Let $b_{d(a)+1}=1$.
For every $i\in I_{3}^{a}$ there is a unique $k(i)$ such that $a_{ki}=1$ for
$k\leq k(i)$ and $a_{ki}=-1$ for $k>k(i)$. The possible values for $k(i)$
reach from $0$ to $d(a)$ where $0$ and $d(a)$ correspond to the extremal cases
where the leaf $i$ is to the left or to the right of all subtrees. This
implies that

$\displaystyle\mathbb{P}^{\xi}\big{(}$ $\displaystyle\forall i\in
I_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}G_{k}^{a}(U_{i})=\gamma_{i,i_{k}^{a}};\forall i,j\in I_{3}^{a},i\neq
j\mathrel{\mathop{\mathchar
58\relax}}F(a,U_{i},a,U_{j},U_{ij})=\gamma_{ij}\big{)}$
$\displaystyle=\bigg{(}\prod_{i\in
I_{3}^{a}}(b_{k(i)+1}-b_{k(i)})\bigg{)}\mathbb{P}^{\xi}\big{(}\forall i,j\in
I_{3}^{a},i\neq j\mathrel{\mathop{\mathchar
58\relax}}F(a,U_{i},a,U_{j},U_{ij})=\gamma_{ij}\big{|}\forall i\in
I_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}G_{k}^{a}(U_{i})=\gamma_{i,i_{k}^{a}}\big{)}$
$\displaystyle=\bigg{(}\prod_{i\in
I_{3}^{a}}(b_{k(i)+1}-b_{k(i)})\bigg{)}\bigg{(}\prod_{k=0}^{d(a)}\frac{1}{|\\{i\in
I_{3}^{a}\mathrel{\mathop{\mathchar 58\relax}}k(i)=k\\}|!}\bigg{)}$

The last equality holds because the leaves with indices in the set $\\{i\in
I_{3}^{a}\mathrel{\mathop{\mathchar 58\relax}}k(i)=k\\}$ form a uniform random
permutation by exchangeability. We have chosen Construction 3.2 in such a way
that

$\displaystyle\bigg{(}\prod_{i\in I_{3}^{a}}(b_{k(i)+1}-b_{k(i)})\bigg{)}$
$\displaystyle\bigg{(}\prod_{k=0}^{d(a)}\frac{1}{|\\{i\in
I_{3}^{a}\mathrel{\mathop{\mathchar 58\relax}}k(i)=k\\}|!}\bigg{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i\in I_{3}^{a}\forall k\leq
d(a)\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,i_{k}^{a})=\gamma_{i,i_{k}^{a}};\forall i,j\in
I_{3}^{a},i\neq j\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}.$ (3.15)

Before (3.14) we assumed $I_{3}^{a}=\tilde{I}_{3}^{a}$. Consider now the case
where $I_{3}^{a}\neq\tilde{I}_{3}^{a}$ which happens when there is $i\in
I_{1}$ with $\xi_{i}=a$. In this case the computations (3.14) – (3.15) become
easier. The reason for this is that we do not need to consider the terms of
the form

$\left\\{\forall i\in I_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}p(i,i^{a}_{k})=\gamma_{i,i_{k}^{a}}\right\\}.$

This is because $d(a)=1$ and $\xi_{i^{a}_{1}}\in\tilde{I}_{3}^{a}$. Besides
that we consider $\tilde{I}_{3}^{a}$ instead of $I_{3}^{a}$. The computations
then proceed as above.

Recall that we have already shown (3.9), this means that

$\mathbb{P}^{\xi}\big{(}\forall i\neq j\in I_{1}\cup
I_{2}\mathrel{\mathop{\mathchar
58\relax}}p(i,j)=\gamma_{ij}\big{)}=\mathbb{P}^{\xi}\big{(}\forall i\neq j\in
I_{1}\cup I_{2}\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}.$ (3.16)

Going back to (3.14), with (3.16) we have that

$\displaystyle\mathbb{P}^{\xi}\big{(}\forall i,j\in[n],$ $\displaystyle i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i,j\in I_{1}\cup I_{2},i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p^{*}(i,j)=\gamma_{ij};\forall a\forall
i\in I_{3}^{a}\forall k\leq d(a)\mathrel{\mathop{\mathchar
58\relax}}p^{*}(i,i^{a}_{k})=\gamma_{i,i_{k}^{a}};$
$\displaystyle\quad\quad\forall a\forall i,j\in I_{3}^{a},i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}$
$\displaystyle=\mathbb{P}^{\xi}\big{(}\forall i,j\in[n],i\neq
j\mathrel{\mathop{\mathchar 58\relax}}p^{*}(i,j)=\gamma_{ij}\big{)}.$

This completes showing that $p$ and $p^{*}$ have the same distribution under
$\mathbb{P}^{\xi}$ which completes the proof. ∎

###  3.2 Uniqueness of a canonical representation

So far we have proven Proposition 3.3 which states that there is _some_
decorated planar real tree that corresponds to our dendritic system. This
means we have the following collection of objects: a rooted, weighted real
tree $(\textbf{T},d,r,\mu)$, a planar order $\psi$ on T, a branch weight
function $\lambda$ and a branchpoint weight function $B$. In this section we
want to find a more canonical representation for this in the form of IP–trees,
see Definition 1.4. This will lead to us proving Proposition 3.4. The notion
of IP–trees has been introduced by Forman [9].

######  Definition 3.12 (Special points).

For a weighted, rooted real tree $(\textbf{T},d,r,\mu)$ the special points are

  1. 1.)

the locations of atoms of $\mu$,

  2. 2.)

the branch points of T, and

  3. 3.)

the isolated leaves of $\textrm{span}(\textrm{supp}(\mu))$, by which we mean
leaves of $\textrm{span}(\textrm{supp}(\mu))$ that are not limit points of the
branch points of $\textrm{span}(\textrm{supp}(\mu))$.

######  Definition 3.13 (mass–structural isomorphism).

Let $\mathscr{S}_{i}$ be the sets of special points of weighted, rooted real
trees $(\textbf{T}_{i},d_{i},r_{i},\mu_{i})$ for $i=1,2$. A measurable map
$\phi\mathrel{\mathop{\mathchar
58\relax}}\textbf{T}_{1}\rightarrow\textbf{T}_{2}$ is a mass–structural
isomorphism if it has the following properties.

  1. 1.)

Mass preserving. For every $x\in\mathscr{S}_{1}$,
$\mu_{1}([r_{1},x]_{\textbf{T}_{1}})=\mu_{2}([r_{2},\phi(x)]_{\textbf{T}_{2}})$,
$\mu_{1}(\\{x\\})=\mu_{2}(\\{\phi(x)\\})$, and
$\mu_{1}(F_{\textbf{T}_{1}}(x))=\mu_{2}(F_{\textbf{T}_{2}}(\phi(x)).$

  2. 2.)

Structure preserving. For $x,y\in\mathscr{S}_{1}$ we have
$x\in[r_{1},y]_{\textbf{T}_{1}}$ if and only if
$\phi(x)\in[r_{2},\phi(y)]_{\textbf{T}_{2}}.$

We call two rooted, weighted real trees mass–structurally equivalent if there
exists a mass–structural isomorphism between the two. This is an equivalence
relation. We then have the following two theorems of Forman [9], the second
one concern itself with hierarchies. A hierarchy on $\mathbb{N}$
$(\mathcal{H}_{n},n\geq 1)$ [9, Definition 1.6] is an object such that for
every $n\geq 1$, $\mathcal{H}_{n}$ is a collection of subsets of $[n]$
satisfying certain consistency assumptions – we do not recall these here. To
every IP–tree $(\textbf{T},d,r,\mu)$ we associate a hierarchy, $(\xi_{i},i\geq
1)$ are $i.i.d.$ $\mu$–random variables,

$\mathcal{H}_{n}=\left\\{\left\\{i\in[n]\mathrel{\mathop{\mathchar
58\relax}}\xi_{i}\in F_{\textbf{T}}(x)\right\\}\mathrel{\mathop{\mathchar
58\relax}}x\in\textbf{T}\right\\}\cup\left\\{\left\\{i\right\\}\mathrel{\mathop{\mathchar
58\relax}}i\in[n]\right\\}\quad\quad\text{for }n\geq 1.$ (3.17)

Observe that this is very similar to the first two steps of Construction 1.7.
For a given $n$, $\mathcal{H}_{n}$ as above can be represented as a discrete
tree, therefore we can think of a hierarchy $(\mathcal{H}_{n},n\geq 1)$ as a
sequence of growing trees.

######  Theorem 3.14.

[9, Theorem 1.5] Each mass–structural equivalence–class of rooted, weighted
real trees contains exactly one isomorphism class of IP–trees.

######  Theorem 3.15.

[9, Theorem 1.7] Two IP–trees are mass–structurally equivalent if and only if
the induced hierarchies in (3.17) have the same law.

Before we can apply this to our setting, we make sure that we can also pass
the planar order $\psi$, the branch weight function $\lambda$ and the
branchpoint weight function $B$ through a mass–structural isomorphism.

######  Lemma 3.16.

A mass–structural isomorphism $\phi$ induces a new planar order $\phi(\psi)$,
a new branch weight function $\phi(\lambda)$ and a new branchpoint weight
function $\phi(B)$.

###### Proof.

Assume we have $\phi\mathrel{\mathop{\mathchar
58\relax}}(\textbf{T},d,r,\mu)\rightarrow(\textbf{T}^{\prime},d^{\prime},r^{\prime},\mu^{\prime})$
and that $\psi$, $\lambda$ and $B$ are a planar order, branch weight function
and branchpoint weight function for $(\textbf{T},d,r,\mu)$.

For a totally unordered sequence
$x_{1}^{\prime},\ldots,x_{n}^{\prime}\in\textbf{T}^{\prime}$, we define

$\phi(\psi)_{n}(x_{1}^{\prime},\ldots,x_{n}^{\prime})=\psi_{n}(\phi^{-1}(x_{1}^{\prime}),\ldots,\phi^{-1}(x_{n}^{\prime})).$

Because $\phi$ is structure preserving in the sense of Definition 3.13 we
obtain a totally unordered sequence
$\phi^{-1}(x_{1}^{\prime}),\ldots,\phi^{-1}(x_{n}^{\prime})$. The same
property and the fact that $\psi$ is a planar order also implies that we can
embed $\phi(\psi)_{m}(x_{1}^{\prime},\ldots,x_{m}^{\prime})$ into
$\phi(\psi)_{n}(x_{1}^{\prime},\ldots,x_{n}^{\prime})$ for $m<n$ respecting
the planar structure.

For any $x^{\prime}\in\textbf{T}^{\prime}$, define
$\phi(\lambda)(x^{\prime})=\lambda(\phi^{-1}(x^{\prime}))$ which is again a
branch weight function. Similarly, if $a^{\prime}\in\textbf{T}^{\prime}$ is an
atom of $\mu^{\prime}$, then $a=\phi^{-1}(a^{\prime})$ is an atom of $\mu$
because $\phi$ is mass–preserving. We can then define
$B(a^{\prime})=\beta_{a}$. Because $\phi$ is structure–preserving, this is a
valid branchpoint weight function which is compatible with $\phi(\psi)$. ∎

With Lemma 3.16 in hand, we can prove Proposition 3.4.

###### Proof of Proposition 3.4.

Let
$(\textbf{T}_{i},d_{i},r_{i},\mu_{i},\psi^{(i)},\lambda_{i},B_{i}),i\in\\{1,2\\}$
be two decorated planar real trees such that the induced Markov chains
$(T_{n}^{(i)},n\geq 1),i\in\\{1,2\\}$ have the same distribution. We show the
uniqueness of $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ in multiple steps.

_Uniqueness of $(\textbf{T},d,r,\mu)$:_ Observe that applying a
mass–structural isomorphism using the induced maps of Lemma 3.16 does not
change the distribution of the sampled dendritic system: More precisely,
assume we are given a mass–structural isomorphism
$\phi\mathrel{\mathop{\mathchar
58\relax}}(\textbf{T}_{1},d_{1},r_{1},\mu_{1})\rightarrow(\textbf{T}_{2},d_{2},r_{2},\mu_{2})$
and a planar order $\psi$, branch weight function $\lambda$ and branchpoint
weight function $B$ for $\textbf{T}_{1}$. Sample
$\\{\xi_{i}\\}_{i\in\mathbb{N}}$ independently from $\mu_{1}$ in
$\textbf{T}_{1}$, then $\\{\phi(\xi_{i})\\}_{i\in\mathbb{N}}$ is an
$i.i.d.$–$\mu_{2}$ sequence. Using these random variables and the same
sequence of independent uniform random variables
$\\{U_{i}\\}_{i\in\mathbb{N}}$ we can construct two dendritic systems
$\mathcal{D}_{1}=(\mathbb{N},\sim_{1},\prec_{1},p_{1})$ and
$\mathcal{D}_{2}=(\mathbb{N},\sim_{2},\prec_{2},p_{2})$ via Construction 1.7.
Because $\phi$ is structure preserving, $\sim_{1}$ and $\sim_{2}$,
respectively $\prec_{1}$ and $\prec_{2}$, are almost surely the same. Further,
because we defined $\phi(\psi)$, $\phi(\lambda)$ and $\phi(B)$ by pullback,
$p_{1}$ and $p_{2}$ are almost surely the same. In particular, the
distribution of $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ is identical.

On the other hand, observe that if in Construction 1.7 we do not add planarity
to $T_{n}$ and keep the leaf labels, we retrieve the hierarchy given by
(3.17). Now, by Theorem 3.15 and because the induced Markov chains
$(T_{n}^{(i)},n\geq 1),i\in\\{1,2\\}$ have the same distribution, the trees
$(\textbf{T}_{1},d_{1},r_{1},\mu_{1})$ and
$(\textbf{T}_{2},d_{2},r_{2},\mu_{2})$ are mass–structurally isomorphic.
Having also shown that the distribution of a dendritic system is invariant
under mass–structural isomorphism of the decorated planar real tree, this and
Theorem 3.14 then yield the desired uniqueness of $(\textbf{T},d,r,\mu)$.

_Uniqueness of $\psi$:_ Assume now that $(\textbf{T},d,r,\mu)$ is fixed and
that we are given two planar orders $\psi^{(1)}$ and $\psi^{(2)}$ with the
distribution of the Markov chain being the same. In particular, we assume that
the distributions of $(\psi_{n}^{(1)}(\xi_{1},\ldots,\xi_{n}),n\geq 2)$ and
$(\psi_{n}^{(2)}(\zeta_{1},\ldots,\zeta_{n}),n\geq 2)$ are the same where
$(\xi_{i},i\geq 1)$ and $(\zeta_{i},i\geq 1)$ are $i.i.d.$ $\mu$–random
variables. We will show that there is an isometry
$\varphi\mathrel{\mathop{\mathchar 58\relax}}\textbf{T}\to\textbf{T}$ such
that $\varphi(\psi^{(1)})=\psi^{(2)}$.

By [17, Theorem 3.4 (i)] there exists a kernel $K_{1}$ such that for
appropriate events $A,B$ we have

$\mathbb{P}\left((\xi_{i},i\geq 1)\in
A,(\psi_{n}^{(1)}(\xi_{1},\ldots,\xi_{n}),n\geq 2)\in
B\right)=\int_{B}K_{1}(S,A)\mathbb{P}\left((\psi_{n}^{(1)}(\xi_{1},\ldots,\xi_{n}),n\geq
2)\in dS\right).$

The same is true for $\psi^{(2)}$ with another kernel $K_{2}$. This means that
we can work on a probability space such that
$\psi_{n}^{(1)}(\xi_{1},\ldots,\xi_{n})=\psi_{n}^{(2)}(\zeta_{1},\ldots,\zeta_{n})$
for all $n\geq 2$ while keeping the joint distribution of $(\xi_{i},i\geq 1)$
and $(\psi^{(1)}_{n}(\xi_{1},\ldots,\xi_{n}),n\geq 2)$ the same. Abbreviate
$S_{n}=\psi_{n}^{(1)}(\xi_{1},\ldots,\xi_{n})$. We use this to define a map
$\varphi\mathrel{\mathop{\mathchar 58\relax}}\textbf{T}\to\textbf{T}$. First,
for all $i\geq 1$ we define $\varphi(\xi_{i})=\zeta_{i}$. For any $i\geq 1$
and $n\geq i$, $\xi_{i}$ and $\varphi(\xi_{i})$ correspond to the same vertex
$x^{n}_{i}$ in $S_{n}$. Next, let $\xi_{i}\wedge\xi_{j}$ be the most recent
common ancestor of $\xi_{i}$ and $\xi_{j}$ and similarly let $x_{i}^{n}\wedge
x_{j}^{n}$ be the most recent common ancestor of $x_{i}^{n}$ and $x_{j}^{n}$.
Define $\varphi(\xi_{i}\wedge\xi_{j})=\varphi(\xi_{i})\wedge\varphi(\xi_{j})$,
both $\xi_{i}\wedge\xi_{j}$ and $\varphi(\xi_{i}\wedge\xi_{j})$ correspond to
$x_{i}^{n}\wedge x_{j}^{n}$ in $S_{n}$. Observe that for
$i,j,k,\ell\in\mathbb{N}$ if $\xi_{i}\wedge\xi_{j}=\xi_{k}\wedge\xi_{\ell}$
then
$\varphi(\xi_{i})\wedge\varphi(\xi_{j})=\varphi(\xi_{k})\wedge\varphi(\xi_{\ell})$,
hence $\varphi(\xi_{i}\wedge\xi_{j})$ is well defined. This defines $\varphi$
on $\\{\xi_{i},i\geq 1\\}$ as well as all branchpoints of T. Let
$\mu_{n}=\sum_{i=1}^{n}\delta_{x_{i}^{n}}$ on $S_{n}$ and we observe that
$\lim_{n\to\infty}\frac{1}{n}\mu_{n}(F_{S_{n}}(x_{i}^{n}))=\mu(F_{\textbf{T}}(\xi_{i}))$,
almost–surely by the strong law of large numbers applied to
$\\{\xi_{j},j>i\\}$. Similarly,
$\lim_{n\to\infty}\frac{1}{n}\mu_{n}(F_{S_{n}}(x_{i}^{n}\wedge
x_{j}^{n}))=\mu(F_{\textbf{T}}(\xi_{i}\wedge\xi_{j}))$ for all $i$ and $j$.
This allows us to show that $\varphi$ restricted to $\\{\xi_{i},i\geq 1\\}$ is
an isometry, we use the IP–spacing (1.3),

$\displaystyle d(\varphi(\xi_{i}),\varphi(\xi_{j}))$
$\displaystyle=\left|\mu(F_{\textbf{T}_{2}}(\varphi(\xi_{i}\wedge\xi_{j})))-\mu(F_{\textbf{T}}(\varphi(\xi_{i})))\right|+\left|\mu(F_{\textbf{T}}(\varphi(\xi_{i}\wedge\xi_{j})))-\mu(F_{\textbf{T}}(\varphi(\xi_{j})))\right|$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\left|\mu_{n}(F_{S_{n}}(x_{i}^{n}\wedge
x_{j}^{n}))-\mu_{n}(F_{S_{n}}(x_{i}^{n}))\right|+\lim_{n\to\infty}\frac{1}{n}\left|\mu_{n}(F_{S_{n}}(x_{i}^{n}\wedge
x_{j}^{n}))-\mu_{n}(F_{S_{n}}(x_{j}^{n}))\right|$
$\displaystyle=\left|\mu(F_{\textbf{T}}(\xi_{i}\wedge\xi_{j}))-\mu(F_{\textbf{T}}(\xi_{i}))\right|+\left|\mu(F_{\textbf{T}_{1}}(\xi_{i}\wedge\xi_{j}))-\mu(F_{\textbf{T}}(\xi_{j}))\right|$
$\displaystyle=d(\xi_{i},\xi_{j}).$

The same is true for branchpoints. In particular, this means that $\varphi$
maps Cauchy–sequences to Cauchy–sequences. Hence, assume that for
$y\in\textrm{supp}\ \mu$ there is a sequence $y_{k},k\geq 1$ with
$\lim_{k\to\infty}y_{k}=y$ and for every $k$ we have either
$y_{k}\in\\{\xi_{i},i\geq 1\\}$ or $y_{k}$ is a branchpoint in T. We then
define $\varphi(y)=\lim_{k\to\infty}\varphi(y_{k})$. Due to the aforementioned
properties of $\varphi$ and because T is a complete metric space, this limit
exists and is well–defined, i.e. does not depend on the choice of sequence
$(y_{k})_{k}$.

The map $\varphi$ can be extended to an isometry. Indeed, because T is an
IP–tree, it suffices to show that $\varphi$ restricted to special points
($\textrm{supp}\ \mu$ and branchpoints) is a mass–structural isomorphism.
Theorem 3.14 then tells us that there is an isometry, and by checking the
proof in [9] we can see that this isometry is an extension of the underlying
mass–structural isomorphism between special points. Let us now check that
$\varphi$ is a mass–structural isomorphism. Clearly, $\varphi$ is structure
preserving because $\psi^{(1)}_{n}(x_{1},\ldots,x_{n})$ corresponds to
$\textrm{span}(x_{1},\ldots,x_{n})$ as combinatorial trees. Further, $\varphi$
is mass preserving: consider $z\in\textbf{T}$, both $z$ and $\varphi(z)$
correspond to the same point in $S_{n}$, call it $z_{n}$. We then have

$\mu(F_{\textbf{T}}(z))=\lim_{n\to\infty}\frac{1}{n}\mu_{n}(F_{S_{n}}(z_{n}))=\mu(F_{\textbf{T}}(\varphi(z)),\quad\quad\text{almost
--surely},$

where we applied the strong law of large numbers twice. The same approach
works for atoms and segments. Hence the $\varphi$ is a mass–structural
isomorphism and thus can be extended to an isometry on the whole tree T.

Next, we show that $\varphi(\psi^{(1)})=\psi^{(2)}$. For this, let $n\geq 2$
and let $x_{1},\ldots,x_{n}\in\\{\zeta_{i},i\geq
1\\}\cup\\{\text{branchpoints}\\}$ and therefore also
$\varphi^{-1}(x_{1}),\ldots,\varphi^{-1}(x_{n})\in\\{\xi_{i},i\geq
1\\}\cup\\{\text{branchpoints}\\}$. Observe that for $N$ large enough
$\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{n})$ and
$\psi^{(2)}_{n}(x_{1},\ldots,x_{n})$ are subtrees of $S_{N}$. Moreover due to
the coupling they are the same, i.e.
$\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{n})=\psi^{(2)}_{n}(x_{1},\ldots,x_{n})$.
This can be extended to $x_{1},\ldots,x_{n}\in\textrm{supp}\ \mu$ by density
of $\\{\zeta_{i},i\geq 1\\}$. Because
$\textrm{span}(\textrm{supp}(\mu))=\textbf{T}$ this is also true for all
$x_{1},\ldots,x_{n}\in\textbf{T}$. Indeed, it suffices to specify
$\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{n})$ for totally unordered
$x_{1},\ldots,x_{n}$. If for some $i\in[n]$, $x_{i}\notin\textrm{supp}(\mu)$,
then we can choose any leaf $x_{i}^{\prime}$ with $x_{i}<x_{i}^{\prime}$ to
obtain
$\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{i},\ldots,x_{n})=\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{n})$.
Because all leaves are in the support of $\mu$, this determines
$\varphi(\psi^{(1)})_{n}(x_{1},\ldots,x_{n})$ – the same argument works for
$\psi_{n}^{(2)}$. Hence we have shown that
$\varphi(\psi^{(1)})_{n}=\psi^{(2)}_{n}$, doing this for all $n$ shows that
$\varphi(\psi^{(1)})=\psi^{(2)}$. This completes showing the uniqueness of
$\psi$.

_Uniqueness of $\lambda$:_ Assume now that $(\textbf{T},d,r,\mu,\psi)$ is
fixed and we are given two different branch weight functions
$\lambda^{(1)},\lambda^{(2)}\in L^{1}(\mu_{s})$. Let $T_{n}^{(1)}$ and
$T_{n}^{(2)}$ be the trees obtained from using $\lambda^{(1)}$ and
$\lambda^{(2)}$ respectively while sampling from $(\textbf{T},d,r,\mu)$. There
exists a segment $[x,y]\subset\textbf{T}$ such that
$\int_{[x,y]}\lambda^{(1)}d\mu_{s}\neq\int_{[x,y]}\lambda^{(2)}d\mu_{s}$. The
segment $[x,y]\subset\textbf{T}$ corresponds to segments
$[x_{n}^{(1)},y_{n}^{(1)}]$ and $[x_{n}^{(2)},y_{n}^{(2)}]$ in $T_{n}^{(1)}$
and $T_{n}^{(2)}$ respectively. Let $L_{n}^{(1)}$ be the proportion of leaves
directly attached to the left of $[x_{n}^{(1)},y_{n}^{(1)}]$ – here we only
count vertices of degree $2$ in T to avoid counting atoms. Define
$L_{n}^{(2)}$ similarly. By the strong law of large numbers, we almost surely
have as $n\to\infty$

$L_{n}^{(1)}\longrightarrow\int_{[x,y]}\lambda^{(1)}d\mu_{s}\quad\quad\text{and}\quad\quad
L_{n}^{(2)}\longrightarrow\int_{[x,y]}\lambda^{(2)}d\mu_{s}.$

By assumption, these two integrals are different and thus the distributions of
$\big{(}T_{n}^{(1)},n\geq 1\big{)}$ and $\big{(}T_{n}^{(2)},n\geq 1\big{)}$
are different. This shows the uniqueness of $\lambda$.

_Uniqueness of $B$:_ Assume now that $(\textbf{T},d,r,\mu,\psi)$ is fixed and
we are given two different branchpoint weight functions $B^{(1)},B^{(2)}$.
Then there exists an atom $a$ such that $\beta_{a}^{(1)}\neq\beta_{a}^{(2)}$.
Hence there is $t\in(0,1)$ such that
$\beta_{a}^{(1)}(t)\neq\beta_{a}^{(2)}(t)$ and such that – by the requirements
that we pose on branchpoint weight functions – this $t$ without loss of
generality corresponds to one subtree S of $a$. Let $T_{n}^{(1)}$ and
$T_{n}^{(2)}$ be the trees obtained from using $B^{(1)}$ and $B^{(2)}$
respectively. For $n$ sufficiently large, the atom $a$ corresponds to
$a_{n}^{(1)}\in T_{n}^{(1)}$ and to $a_{n}^{(2)}\in T_{n}^{(2)}$ respectively,
similarly S corresponds to subtrees $S_{n}^{(1)},S_{n}^{(2)}$ of $a_{n}^{(1)}$
and $a_{n}^{(2)}$ respectively. Let $K_{n}^{(1)}$ be the proportion of leaves
directly attached to $a_{n}^{(1)}$ on the left of $S_{n}^{(1)}$, as compared
to the right of $S_{n}^{(1)}$. Define $K_{n}^{(2)}$ similarly. By the strong
law of large numbers, we almost surely have as $n\to\infty$

$K_{n}^{(1)}\longrightarrow\beta_{a}^{(1)}(t)\quad\quad\text{and}\quad\quad
K_{n}^{(2)}\longrightarrow\beta_{a}^{(2)}(t).$

By assumption, these two values are different and thus the distributions of
$\big{(}T_{n}^{(1)},n\geq 1\big{)}$ and $\big{(}T_{n}^{(2)},n\geq 1\big{)}$
are different. This shows the uniqueness of $B$. ∎

##  4 Scaling Limits

In the following, let $(T_{n},n\geq 1)$ be an extremal tree–valued Markov
chain with uniform backward dynamics corresponding to the decorated planar
real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ where $(\textbf{T},d,r,\mu)$
is an IP-tree. The goal of this section is to show that $T_{n}$ – trimmed and
appropriately rescaled – converges to T almost surely in the Gromov–Prokhorov
topology. Recall the rescaling from (1.5) and the Gromov-Prokhorov metric from
Definition 1.15.

######  Remark 4.1.

One might ask why it is necessary to trim $T_{n}$ before rescaling it.
Consider the decorated planar real tree that is made up from a single atom $a$
of weight $1$, here $d,\psi,\lambda,B$ are all trivial. For any $n\geq 2$ the
tree $T_{n}$ is a star tree with $n$ leaves directly connected to the root. In
the IP–rescaling (1.5), all these edges have length $1-1/n$. From Definition
1.15 we can see that $d_{\text{GP}}(\textbf{T},T_{n})=1$ for all $n\geq 2$,
hence we have no convergence. This problem is solved by trimming.

An important idea in the proof will be that $T_{n}^{\text{trim}}$ corresponds
to a subtree of T. Recall that $T_{n}$ is constructed by sampling
$(\xi_{1},\ldots,\xi_{n})$ from T and that $T_{n}$ corresponds to
$\textrm{span}(r,\xi_{1},\ldots,\xi_{n})$ plus additional leaves added through
$B$ and $\lambda$. The trimming removes all additional leaves but also leaves
which were not added through $B$ and $\lambda$. Let us define a function
$\eta^{n}\mathrel{\mathop{\mathchar 58\relax}}\textbf{T}^{n}\to\textbf{T}^{n}$
which corresponds to trimming on the level of real trees. First, consider the
set of all most recent common ancestors of $\xi_{1},\ldots,\xi_{n}$:

$M_{n}=\left\\{\xi_{i}\wedge\xi_{j},1\leq i\neq j\leq n\right\\}.$

where $\xi_{i}\wedge\xi_{j}$ is the most recent common ancestor of $\xi_{i}$
and $\xi_{j}$. We then set

$\eta_{i}^{n}(\xi_{1},\ldots,\xi_{n})=\text{argmin}_{y\in
M_{n},y\in[r,\xi_{i}]}d_{\textbf{T}}(y,\xi_{i});\quad\forall i\leq n,$ (4.1)

which is the closest element of $M_{n}$ that is an ancestor of $\xi_{i}$. We
write $\eta_{i}^{n}(\xi_{1},\ldots,\xi_{n})$ for the $i$–th coordinate of
$\eta^{n}(\xi_{1},\ldots,\xi_{n})$ and we will abuse notation by writing
$\eta^{n}(\xi_{i})=\eta_{i}^{n}(\xi_{1},\ldots,\xi_{n})$. Equip
$\textrm{span}(r,\eta^{n}(\xi_{1},\dots,\xi_{n}))$ with a probability measure
$\mu_{n}^{\eta}$ by placing weight $1/n$ on $\eta^{n}(\xi_{i})$ for every
$i\leq n$ and with a metric $d^{\eta}$ according to an IP–rescaling as in
(1.5). By construction, we then have the following lemma.

######  Lemma 4.2.

As rooted, weighted metric spaces,
$(T_{n}^{\text{trim}},d_{n}^{\text{trim}},r_{n},\mu_{n}^{\text{trim}})$ and
$(\textrm{span}(r,\eta^{n}(\xi_{1},\dots,\xi_{n})),d_{n}^{\eta},r,\mu_{n}^{\eta})$
are isomorphic.

We will implicitly use this representation of
$(T_{n}^{\text{trim}},d_{n}^{\text{trim}},r_{n},\mu_{n}^{\text{trim}})$.

Figure 12: The different operations involved in trimming, this diagram
commutes. The double–headed arrow is the correspondence of Lemma 4.2. A number
$k$ next to a vertex signifies an atom of weight $k/13$ for $\mu_{13}^{\eta}$
and $\mu_{13}^{trim}$ respectively.

We can now state the main theorem of this section.

######  Theorem 4.3.

Let $(T_{n},n\geq 1)$ be an extremal tree–valued Markov chain corresponding to
the decorated planar real tree $(\textbf{T},d,r,\mu,\psi,\lambda,B)$ where
$(\textbf{T},d,r,\mu)$ is an IP-tree. Let
$(T_{n}^{\text{trim}},d_{n}^{\text{trim}},r_{n},\mu_{n}^{\text{trim}})$ be the
trimmed and rescaled version of $T_{n}$. We then have

$(T_{n}^{\text{trim}},d_{n}^{\text{trim}},r_{n},\mu_{n}^{\text{trim}})\xrightarrow{n\to\infty}(\textbf{T},d,r,\mu),$

almost surely in the Gromov–Prokhorov topology.

From this we prove Theorem 1.16.

###### Proof of Theorem 1.16..

This follows immediately from Theorem 4.3, the decomposition into extremal
distribution in Corollary 2.17 and the classification of tree–valued Markov
chains with uniform backward dynamics in Theorem 1.10. ∎

The proof of the above theorem proceeds by comparing $T_{n}^{\text{trim}}$ and
T with $\textrm{span}(r,\xi_{1},\ldots,\xi_{n})$. For this purpose, let
$\textbf{S}_{n}=\textrm{span}(r,\xi_{1},\ldots,\xi_{n})$ and choose
$\mu_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\xi_{i}}$. We then construct a
metric $d_{n}$ for $\textbf{S}_{n}$ by again considering the inhomogenous
IP–rescaling (1.5) with respect to the root $r$. The proof of Theorem 4.3
consists of showing that both
$d_{\text{GP}}(T_{n}^{\text{trim}},\textbf{S}_{n})$ and
$d_{\text{GP}}(\textbf{S}_{n},\textbf{T})$ are small for $n$ sufficiently
large.

Before we can do this, we will show some general statements about IP–trees. In
Lemma 4.4 we show some small auxiliary statements and in Lemma 4.5 we
construct a partition of T that helps us to approximate subtrees, i.e. sets of
the form $F_{\textbf{T}}(x)$ for $x\in\textbf{T}$.

######  Lemma 4.4.

Let $(\textbf{T},d,r,\mu)$ be an IP–tree.

  1. (i)

For all $x\in\textbf{T}$ we have

$d(r,x)\leq 1-\mu(F_{\textbf{T}}(x)).$

  2. (ii)

For any $c<1$ the set

$\left\\{x\in\textbf{T}\mathrel{\mathop{\mathchar
58\relax}}d(r,x)=c\right\\},$

is at most countably infinite.

  3. (iii)

Suppose $(\textbf{T}^{\prime},d^{\prime},r^{\prime},\mu^{\prime})$ is another
IP–tree and $\varphi\mathrel{\mathop{\mathchar 58\relax}}\text{dom}\
\varphi\to\textrm{supp}(\mu^{\prime})$ is an injective map respecting the tree