Brownian tree

This definition gives the finite-dimensional laws of the subtrees generated by finitely many leaves.

Let us consider the space of all binary trees with ${\displaystyle k}$ leaves numbered from ${\displaystyle 1}$ to ${\displaystyle k}$. These trees have ${\displaystyle 2k-1}$ edges with lengths ${\displaystyle (\ell _{1},\dots ,\ell _{2k-1})\in \mathbb {R} _{+}^{2k-1}}$. A tree is then defined by its shape ${\displaystyle \tau }$ (which is to say the order of the nodes) and the edge lengths. We define a probability law ${\displaystyle \mathbb {P} }$ of a random variable ${\displaystyle (T,(L_{i})_{1\leq i\leq 2k-1})}$ on this space by:

${\displaystyle \mathbb {P} (T=\tau \,,\,L_{i}\in [\ell _{i},\ell _{i}+d\ell _{i}],\forall 1\leq i\leq 2k-1)=s\exp(-s^{2}/2)\,d\ell _{1}\ldots d\ell _{2k-1}}$

where ${\displaystyle \textstyle s=\sum \ell _{i}}$.

In other words, ${\displaystyle \mathbb {P} }$ depends not on the shape of the tree but rather on the total sum of all the edge lengths.

In other words, the Brownian tree is defined from the laws of all the finite sub-trees one can generate from it.

The Brownian tree is a real tree defined from a Brownian excursion (see characterisation 4 in Real tree).

Let ${\displaystyle e=(e(x),0\leq x\leq 1)}$be a Brownian excursion. Define a pseudometric ${\displaystyle d}$ on ${\displaystyle [0,1]}$ with

${\displaystyle d(x,y):=e(x)+e(y)-2\min {\big \{}e(z)\,;z\in [x,y]{\big \}},}$ for any ${\displaystyle x,y\in [0,1]}$

We then define an equivalence relation, noted ${\displaystyle \sim _{e}}$ on ${\displaystyle [0,1]}$ which relates all points ${\displaystyle x,y}$ such that ${\displaystyle d(x,y)=0}$ .

${\displaystyle x\sim _{e}y\Leftrightarrow d(x,y)=0.}$

${\displaystyle d}$ is then a distance on the quotient space ${\displaystyle [0,1]\,/\!\sim _{e}}$.

It is customary to consider the excursion ${\displaystyle e/2}$ rather than ${\displaystyle e}$.

This is also called stick-breaking construction.

Consider a non-homogeneous Poisson point process N with intensity ${\displaystyle r(t)=t}$. In other words, for any ${\displaystyle t>0}$, ${\displaystyle N_{t}}$ is a Poisson variable with parameter ${\displaystyle t^{2}}$. Let ${\displaystyle C_{1},C_{2},\ldots }$ be the points of ${\displaystyle N}$. Then the lengths of the intervals ${\displaystyle [C_{i},C_{i+1}]}$ are exponential variables with decreasing means. We then make the following construction:

• (initialisation) The first step is to pick a random point ${\displaystyle u}$ uniformly on the interval ${\displaystyle [0,C_{1}]}$. Then we glue the segment ${\displaystyle ]C_{1},C_{2}]}$ to ${\displaystyle u}$ (mathematically speaking, we define a new distance). We obtain a tree ${\displaystyle T_{1}}$ with a root (the point 0), two leaves (${\displaystyle C_{1}}$ and ${\displaystyle C_{2}}$), as well as one binary branching point (the point ${\displaystyle u}$).
• (iteration) At step k, the segment ${\displaystyle ]C_{k},C_{k+1}]}$ is similarly glued to the tree ${\displaystyle T_{k-1}}$, on a uniformly random point of ${\displaystyle T_{k-1}}$.

This algorithm may be used to simulate numerically Brownian trees.

Consider a Galton-Watson tree whose reproduction law has finite non-zero variance, conditioned to have ${\displaystyle n}$ nodes. Let ${\displaystyle {\tfrac {1}{\sqrt {n}}}G_{n}}$ be this tree, with the edge lengths divided by ${\displaystyle {\sqrt {n}}}$. In other words, each edge has length ${\displaystyle {\tfrac {1}{\sqrt {n}}}}$. The construction can be formalized by considering the Galton-Watson tree as a metric space or by using renormalized contour processes.

Here, the limit used is the convergence in distribution of stochastic processes in the Skorokhod space (if we consider the contour processes) or the convergence in distribution defined from the Hausdorff distance (if we consider the metric spaces).