Jump to content

Brownian tree

From Wikipedia, the free encyclopedia

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.

This random tree has several equivalent definitions and constructions:[2] 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 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

[edit]

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

[edit]

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 leaves numbered from to . These trees have edges with lengths . A tree is then defined by its shape (which is to say the order of the nodes) and the edge lengths. We define a probability law of a random variable on this space by:[clarification needed]

where .

In other words, depends not on the shape of the tree but rather on the total sum of all the edge lengths.

Definition — Let be a random metric space with the tree property, meaning there exists a unique path between two points of . Equip with a probability measure . Suppose the sub-tree of generated by points, chosen randomly under , has law . Then 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

[edit]

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

Let be a Brownian excursion. Define a pseudometric on with

for any

We then define an equivalence relation, noted on which relates all points such that .

is then a distance on the quotient space .

Definition — The random metric space is called a Brownian tree.

It is customary to consider the excursion rather than .

Poisson line-breaking construction

[edit]

This is also called stick-breaking construction.

Consider a non-homogeneous Poisson point process N with intensity . In other words, for any , is a Poisson variable with parameter . Let be the points of . Then the lengths of the intervals are exponential variables with decreasing means. We then make the following construction:

  • (initialisation) The first step is to pick a random point uniformly on the interval . Then we glue the segment to (mathematically speaking, we define a new distance). We obtain a tree with a root (the point 0), two leaves ( and ), as well as one binary branching point (the point ).
  • (iteration) At step k, the segment is similarly glued to the tree , on a uniformly random point of .

Definition — The closure , 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

[edit]

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

Definition and Theorem —  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).

References

[edit]
  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.