View source for Brownian tree

{{Short description|Concept in probability theory}}
{{About|the Continuum Random Tree obtained from a Brownian excursion|the computer art developed in the 90s|Diffusion-limited aggregation}}
{{Multiple issues|
{{refimprove|date=December 2022}}
{{original research|date=December 2022}}
}}

In [[probability theory]], the '''Brownian tree''', or '''Aldous tree''', or '''Continuum Random Tree (CRT)'''<ref>{{Cite book |last=Le Gall |first=Jean-François |title=Spatial branching processes, random snakes, and partial differential equations |publisher=Springer Science \& Business Media |year=1999}}</ref> is a random [[real tree]] that can be defined from a [[Brownian excursion]]. The Brownian tree was defined and studied by [[David Aldous]] in three articles published in 1991 and 1993. This tree has since then been generalized.

This random tree has several equivalent definitions and constructions:<ref>{{cite web|title=The continuum random tree|url=http://www.stat.berkeley.edu/~aldous/Research/research-crt.html|author=David Aldous|access-date=2012-02-10|publication-date=}}</ref> using sub-trees generated by finitely many leaves, using a Brownian excursion, Poisson separating a straight line or as a limit of Galton-Watson trees.

Intuitively, the Brownian tree is a binary tree whose nodes (or branching points) are [[Dense set|dense]] in the tree; which is to say that for any distinct two points of the tree, there will always exist a node between them. It is a [[fractal]] object which can be approximated with computers<ref>{{cite web|title=Une simulation de l'arbre continu aléatoire brownien|url=http://www.math.u-psud.fr/~miermont/simul.php|author=[[Grégory Miermont]]|access-date=2012-02-10|publication-date=|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303172928/http://www.math.u-psud.fr/~miermont/simul.php|url-status=dead}}</ref> or by physical processes with [[Dendrite (crystal)|dendritic structures]].

== Definitions ==
The following definitions are different characterisations of a Brownian tree, they are taken from Aldous's three articles.<ref>{{Cite journal |last=Aldous |first=David |date=1991 |title=The Continuum Random Tree I |journal=The Annals of Probability |volume=19 |issue=1 |pages=1–28|doi=10.1214/aop/1176990534 |doi-access=free }}</ref><ref>{{Cite journal |last=Aldous |first=David |date=1991-10-25 |title=The continuum random tree. II. An overview |url=https://books.google.com/books?id=FerdFlyRS8oC&dq=info:arqXCCYZRZAJ:scholar.google.com&pg=PA23 |journal=Stochastic Analysis |volume=167 |pages=23–70|doi=10.1017/CBO9780511662980.003 |isbn=9780521425339 }}</ref><ref>{{Cite journal |last=Aldous |first=David |date=1993 |title=The Continuum Random Tree III |journal=The Annals of Probability |volume=21 |issue=1 |pages=248–289 |doi=10.1214/aop/1176989404 |jstor=2244761 |s2cid=122616896 |issn=0091-1798|doi-access=free }}</ref> The notions of ''leaf, node, branch, root'' are the intuitive notions on a tree (for details, see [[real tree]]s).

=== Finite-dimensional laws ===
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 <math>k</math> leaves numbered from <math>1</math> to <math>k</math>. These trees have <math>2k-1</math> edges with lengths <math>(\ell_1,\dots,\ell_{2k-1})\in \R_+^{2k-1}</math>. A tree is then defined by its shape <math>\tau</math> (which is to say the order of the nodes) and the edge lengths. We define a [[Probability theory|probability law]] <math>\mathbb{P}</math> of a random variable <math>(T,(L_i)_{1\leq i\leq 2k-1})</math> on this space by:{{what|reason = This measure is not normalized|date=July 2023}}

: <math>\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}</math>

where <math>\textstyle s = \sum \ell_i</math>.

In other words, <math>\mathbb P</math> depends not on the shape of the tree but rather on the total sum of all the edge lengths.
{{Math theorem
| math_statement = Let <math>X</math> be a random metric space with the tree property, meaning there exists a unique path between two points of <math>X</math>. Equip <math>X</math>  with a probability measure <math>\mu</math>. Suppose the sub-tree of <math>X</math> generated by <math>k</math> points, chosen randomly under <math>\mu</math>, has law <math>\mathbb P</math>. Then <math>X</math> is called a '''Brownian tree'''.
| name = Definition
}}
In other words, the Brownian tree is defined from the laws of all the finite sub-trees one can generate from it.

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

Let <math>e=(e(x),0\leq x\leq 1)</math>be a Brownian excursion. Define a [[Metric space|pseudometric]] <math>d</math> on <math>[0,1]</math> with

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

We then define an [[equivalence relation]], noted <math>\sim_e</math> on <math>[0,1]</math> which relates all points <math>x,y</math> such that <math>d(x,y)=0</math> .

: <math> x\sim_e y \Leftrightarrow d(x,y)=0.</math>

<math>d</math> is then a distance on the [[Quotient space (topology)|quotient space]] <math>[0,1]\,/\!\sim_e</math>. 
{{Math theorem
| math_statement = The random metric space <math>\big([0,1]\,/\!\sim_e,\, d\big)</math> is called a '''Brownian tree'''.
| name = Definition
}}
It is customary to consider the excursion <math>e/2</math> rather than <math>e</math>.

=== Poisson line-breaking construction ===
This is also called ''stick-breaking construction''.

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

* (''initialisation'') The first step is to pick a random point <math>u</math> [[Continuous uniform distribution|uniformly]] on the interval <math>[0,C_1]</math>. Then we glue the segment <math>]C_1,C_2]</math> to <math>u</math> (mathematically speaking, we define a new distance). We obtain a tree <math>T_1</math> with a root (the point 0), two leaves (<math>C_1</math> and <math>C_2</math>), as well as one binary branching point (the point <math>u</math>).
* (''iteration'') At step {{mvar|k}}, the segment <math>]C_k,C_{k+1}]</math> is similarly glued to the tree <math>T_{k-1}</math>, on a uniformly random point of <math>T_{k-1}</math>.
{{Math theorem
| math_statement = The [[Closure (topology)|closure]] <math>\overline{\bigcup_{k\geq 1}T_k}</math>, equipped with the distance previously built, is called a '''Brownian tree'''.
| name = Definition
}}
This algorithm may be used to simulate numerically Brownian trees.

=== Limit of Galton-Watson trees ===
Consider a [[Galton-Watson tree]] whose reproduction law has finite non-zero variance, conditioned to have <math>n</math> nodes. Let <math>\tfrac{1}{\sqrt{n}}G_n</math> be this tree, with the edge lengths divided by <math>\sqrt{n}</math>. In other words, each edge has length <math>\tfrac{1}{\sqrt{n}}</math>. The construction can be formalized by considering the Galton-Watson tree as a metric space or by using renormalized [[Galton-Watson tree|contour processes]].
{{Math theorem
| math_statement = <math>\frac{1}{\sqrt{n}}G_n</math> converges in distribution to a random real tree, which we call a '''Brownian tree'''.
| name = Definition and Theorem
}}

Here, the limit used is the [[convergence in distribution]] of [[stochastic process]]es 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).

== References ==
{{Reflist}}

[[Category:Wiener process]]
[[Category:Fractals]]