Brownian tree

Last updated December 02, 2023

In probability theory, the Brownian tree, or Aldous tree, or Continuum Random Tree (CRT)^[1] 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.

Intuitively, the Brownian tree is a binary tree whose nodes (or branching points) are 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^[3] or by physical processes with dendritic structures.

Definitions

The following definitions are different characterisations of a Brownian tree, they are taken from Aldous's three articles.^[4]^[5]^[6] The notions of leaf, node, branch, root are the intuitive notions on a tree (for details, see real trees).

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 $k$ leaves numbered from $1$ to $k$ . These trees have $2k-1$ edges with lengths $(\ell _{1},\dots ,\ell _{2k-1})\in \mathbb {R} _{+}^{2k-1}$ . A tree is then defined by its shape $\tau$ (which is to say the order of the nodes) and the edge lengths. We define a probability law $\mathbb {P}$ of a random variable $(T,(L_{i})_{1\leq i\leq 2k-1})$ on this space by:^{[ clarification needed ]}

\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 $\textstyle s=\sum \ell _{i}$ .

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

Definition — Let $X$ be a random metric space with the tree property, meaning there exists a unique path between two points of $X$ . Equip $X$ with a probability measure $\mu$ . Suppose the sub-tree of $X$ generated by $k$ points, chosen randomly under $\mu$ , has law $\mathbb {P}$ . Then $X$ is called a Brownian tree.

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 $e=(e(x),0\leq x\leq 1)$ be a Brownian excursion. Define a pseudometric $d$ on $[0,1]$ with

d(x,y):=e(x)+e(y)-2\min {\big \{}e(z)\,;z\in [x,y]{\big \}},

for any

x,y\in [0,1]

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

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

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

Definition — The random metric space ${\big (}[0,1]\,/\!\sim _{e},\,d{\big )}$ is called a Brownian tree.

It is customary to consider the excursion $e/2$ rather than $e$ .

Poisson line-breaking construction

This is also called stick-breaking construction.

Consider a non-homogeneous Poisson point process $N$ with intensity $r(t)=t$ . In other words, for any $t>0$ , $N_{t}$ is a Poisson variable with parameter $t^{2}$ . Let $C_{1},C_{2},\ldots$ be the points of $N$ . Then the lengths of the intervals $[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 $u$ uniformly on the interval $[0,C_{1}]$ . Then we glue the segment $]C_{1},C_{2}]$ to $u$ (mathematically speaking, we define a new distance). We obtain a tree $T_{1}$ with a root (the point 0), two leaves ( $C_{1}$ and $C_{2}$ ), as well as one binary branching point (the point $u$ ).
(iteration) At step $k$ , the segment $]C_{k},C_{k+1}]$ is similarly glued to the tree $T_{k-1}$ , on a uniformly random point of $T_{k-1}$ .

Definition — The closure ${\overline {\bigcup _{k\geq 1}T_{k}}}$ , equipped with the distance previously built, is called a Brownian tree.

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 $n$ nodes. Let ${\tfrac {1}{\sqrt {n}}}G_{n}$ be this tree, with the edge lengths divided by ${\sqrt {n}}$ . In other words, each edge has length ${\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.

Definition and Theorem — ${\frac {1}{\sqrt {n}}}G_{n}$ converges in distribution to a random real tree, which we call a Brownian tree.

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).

Related Research Articles

In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well-defined limit that is within the space.

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In mathematics, the Wiener process is a real-valued continuous-time stochastic process named in honor of American mathematician Norbert Wiener for his investigations on the mathematical properties of the one-dimensional Brownian motion. It is often also called Brownian motion due to its historical connection with the physical process of the same name originally observed by Scottish botanist Robert Brown. It is one of the best known Lévy processes and occurs frequently in pure and applied mathematics, economics, quantitative finance, evolutionary biology, and physics.

In mathematics, Fatou's lemma establishes an inequality relating the Lebesgue integral of the limit inferior of a sequence of functions to the limit inferior of integrals of these functions. The lemma is named after Pierre Fatou.

In mathematics, real trees are a class of metric spaces generalising simplicial trees. They arise naturally in many mathematical contexts, in particular geometric group theory and probability theory. They are also the simplest examples of Gromov hyperbolic spaces.

In abstract algebra and multilinear algebra, a multilinear form on a vector space $over a field is a map$

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

In mathematics, especially functional analysis, a Fréchet algebra, named after Maurice René Fréchet, is an associative algebra $over the real or complex numbers that at the same time is also a Fréchet space. The multiplication operation for is required to be jointly continuous. If is an increasing family of seminorms for the topology of, the joint continuity of multiplication is equivalent to there being a constant and integer for each such that for all . Fréchet algebras are also called B 0 -algebras.$

In metric geometry, the metric envelope or tight span of a metric space M is an injective metric space into which M can be embedded. In some sense it consists of all points "between" the points of M, analogous to the convex hull of a point set in a Euclidean space. The tight span is also sometimes known as the injective envelope or hyperconvex hull of M. It has also been called the injective hull, but should not be confused with the injective hull of a module in algebra, a concept with a similar description relative to the category of R-modules rather than metric spaces.

In the theory of probability and statistics, the Dvoretzky–Kiefer–Wolfowitz–Massart inequality bounds how close an empirically determined distribution function will be to the distribution function from which the empirical samples are drawn. It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz, who in 1956 proved the inequality

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

In mathematics, uniform integrability is an important concept in real analysis, functional analysis and measure theory, and plays a vital role in the theory of martingales.

In theoretical computer science, a small-bias sample space is a probability distribution that fools parity functions. In other words, no parity function can distinguish between a small-bias sample space and the uniform distribution with high probability, and hence, small-bias sample spaces naturally give rise to pseudorandom generators for parity functions.

In graph theory and statistics, a graphon is a symmetric measurable function $, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.$

In statistics and in probability theory, distance correlation or distance covariance is a measure of dependence between two paired random vectors of arbitrary, not necessarily equal, dimension. The population distance correlation coefficient is zero if and only if the random vectors are independent. Thus, distance correlation measures both linear and nonlinear association between two random variables or random vectors. This is in contrast to Pearson's correlation, which can only detect linear association between two random variables.

In stochastic analysis, a rough path is a generalization of the notion of smooth path allowing to construct a robust solution theory for controlled differential equations driven by classically irregular signals, for example a Wiener process. The theory was developed in the 1990s by Terry Lyons. Several accounts of the theory are available.

Exponential Tilting (ET), Exponential Twisting, or Exponential Change of Measure (ECM) is a distribution shifting technique used in many parts of mathematics. The different exponential tiltings of a random variable $is known as the natural exponential family of .$

In mathematics, the Poisson boundary is a measure space associated to a random walk. It is an object designed to encode the asymptotic behaviour of the random walk, i.e. how trajectories diverge when the number of steps goes to infinity. Despite being called a boundary it is in general a purely measure-theoretical object and not a boundary in the topological sense. However, in the case where the random walk is on a topological space the Poisson boundary can be related to the Martin boundary, which is an analytic construction yielding a genuine topological boundary. Both boundaries are related to harmonic functions on the space via generalisations of the Poisson formula.

In mathematics, topological recursion is a recursive definition of invariants of spectral curves. It has applications in enumerative geometry, random matrix theory, mathematical physics, string theory, knot theory.

A Brownian snake is a stochastic Markov process on the space of stopped paths. It has been extensively studied., and was in particular successfully used as a representation of superprocesses.

References

↑ Le Gall, Jean-François (1999). Spatial branching processes, random snakes, and partial differential equations. Springer Science \& Business Media.
↑ David Aldous. "The continuum random tree" . Retrieved 2012-02-10.
↑ Grégory Miermont. "Une simulation de l'arbre continu aléatoire brownien". Archived from the original on 2016-03-03. Retrieved 2012-02-10.
↑ Aldous, David (1991). "The Continuum Random Tree I". The Annals of Probability. 19 (1): 1–28. doi: 10.1214/aop/1176990534 .
↑ Aldous, David (1991-10-25). "The continuum random tree. II. An overview". Stochastic Analysis. 167: 23–70. doi:10.1017/CBO9780511662980.003. ISBN 9780521425339.
↑ Aldous, David (1993). "The Continuum Random Tree III". The Annals of Probability. 21 (1): 248–289. doi: 10.1214/aop/1176989404 . ISSN 0091-1798. JSTOR 2244761. S2CID 122616896.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Le Gall, Jean-François (1999). Spatial branching processes, random snakes, and partial differential equations. Springer Science \& Business Media.

[2] David Aldous. "The continuum random tree" . Retrieved 2012-02-10.

[3] Grégory Miermont. "Une simulation de l'arbre continu aléatoire brownien". Archived from the original on 2016-03-03. Retrieved 2012-02-10.

[4] Aldous, David (1991). "The Continuum Random Tree I". The Annals of Probability. 19 (1): 1–28. doi: 10.1214/aop/1176990534 .

[5] Aldous, David (1991-10-25). "The continuum random tree. II. An overview". Stochastic Analysis. 167: 23–70. doi:10.1017/CBO9780511662980.003. ISBN 9780521425339.

[6] Aldous, David (1993). "The Continuum Random Tree III". The Annals of Probability. 21 (1): 248–289. doi: 10.1214/aop/1176989404 . ISSN 0091-1798. JSTOR 2244761. S2CID 122616896.

[1]

[2]

[3]

[4]

[5]

[6]