Arbre brownien

En théorie des probabilités, l'arbre brownien, ou l'arbre aléatoire continu brownien, ou encore arbre d'Aldous, est un cas particulier d'arbre réel aléatoire qui peut être défini à partir d'une excursion d'un mouvement brownien. L'arbre brownien a été défini et étudié mathématiquement par David Aldous dans une série de trois articles parus en 1991 et 1993. Son nom anglais est Brownian continuum random tree, abrégé en Brownian CRT ou CRT ou même Aldous' CRT. Cet arbre a depuis été généralisé et des propriétés fines ont été obtenues.

Cet arbre aléatoire possède plusieurs définitions et modes de construction équivalents : en utilisant les sous-arbres engendrés par un nombre fini de feuilles, en utilisant une excursion brownienne, par la séparation poissonienne d'une droite ou comme limite d'arbres de Galton-Watson.

Intuitivement, l'arbre brownien est un arbre binaire dont les nœuds (ou points de branchement) sont denses dans l'arbre ; c'est-à-dire qu'entre deux points choisis sur l'arbre, il existera toujours un nœud entre les deux points. C'est un objet fractal qui peut avoir une représentation approchée par des programmes informatiques ou par des processus physiques qui obtiennent des structures dendritiques

Définitions

Les définitions suivantes sont différentes caractérisations d'un arbre brownien, elles sont issues des trois articles pionniers d'Aldous. Les notions de feuilles, nœuds, branches, racines sont les notions intuitives sur un arbre. Pour des explications plus précises, voir ces définitions pour un arbre réel.

Lois finies dimensionnelles

Cette définition donne les lois finies dimensionnelles des sous-arbres engendrés par un nombre fini de feuilles.

On se place dans l'espace des arbres binaires finis possédant $k$ feuilles numérotées de 1 à $k$, ces arbres possèdent donc $2k-1$ arêtes dont les longueurs sont données par des réels positifs $(\ell _{1},\ldots ,\ell _{2k-1})$. Un arbre est alors défini par sa forme $\tau$ (c'est-à-dire l'ordre de ces nœuds) et les longueurs de ces arêtes. On définit une loi de probabilité $\mathbb {P}$ d'une variable aléatoire $(T,(L_{i})_{1\leq i\leq 2k-1})$ sur cet espace par :

$\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}$

où $\textstyle s=\sum \ell _{i}$. C'est-à-dire que la loi $\mathbb {P}$ ne dépend pas de la forme de l'arbre mais que de la somme totale des longueurs des arêtes.

Définition — Notons $X$ est un espace métrique ayant la propriété d'arbre, c'est-à-dire tel qu'il existe un unique chemin entre deux points de $X$, on munit $X$ d'une mesure de probabilité $\mu$. Si le sous-arbre de $X$ engendré par $k$ points, choisis aléatoirement par $\mu$, a la loi $\mathbb {P}$, alors $X$ est appelé l'arbre brownien.

C'est-à-dire que l'arbre brownien est défini à partir des lois de tous les sous-arbres finis que l'on peut générer.

Arbre continu

L'arbre brownien est un arbre réel défini comme à l'aide d'une excursion brownienne (c'est la Caractérisation 4 de l'article wikipedia arbre réel)

Notons $e=(e(x),0\leq x\leq 1)$, une excursion brownienne normalisée, c'est-à-dire conditionnée à être de longueur 1. On définit une pseudo-distance $d$ sur le support $[0,1]$ de cette excursion par

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

On définit alors une relation d'équivalence, notée $\sim _{e}$; sur $[0,1]$ qui permet d'identifier les points $x,y$ tels que $d(x,y)=0$ .

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

$d$ est alors une distance sur l'espace quotient $[0,1]\,/\!\sim _{e}$.

Définition — L'espace métrique ${\big (}[0,1]\,/\!\sim _{e},\,d{\big )}$ est appelé arbre brownien.

Il est en fait plus courant de considérer l'excursion $e/2$ plutôt que $e$.

Fragmentation poissonienne d'une droite

Ce terme est issu du terme anglais Poisson line-breaking ou stick-breaking construction.

On considère un processus de Poisson non homogène N d'intensité $r(t)=t$. C'est-à-dire que, pour tout $t>0$, $N_{t}$ est une variable de Poisson de paramètre $t^{2}$. Si on note $C_{1},C_{2},\ldots$ les points générés par ce processus de Poisson, les longueurs des intervalles $[C_{i},C_{i+1}]$ ont une loi exponentielle qui décroit avec $i$. On effectue alors la construction suivante :

• (initialisation) A la première étape, on choisit un point aléatoire $u$ de Loi uniforme continue sur le segment $[0,C_{1}]$, et le segment $]C_{1},C_{2}]$ est « collé » au point $u$. Le collage s'effectue mathématiquement par la définition d'une nouvelle distance. À la fin de cette étape, on obtient un arbre $T_{1}$ contenant une racine (le point 0), deux feuilles ($C_{1}$ et $C_{2}$) ainsi qu'un point de branchement binaire (le point $u$).
• (itération) A l'étape k, le segment $]C_{k},C_{k+1}]$ est collé à l'arbre $T_{k-1}$, construit à l'étape k-1, en un point choisi uniformément sur $T_{k-1}$.

Définition —  La fermeture ${\overline {\bigcup _{k\geq 1}T_{k}}}$, muni de la distance construite par l'algorithme précédent, est appelé l'arbre brownien.

L'algorithme est utilisé pour simuler l'arbre brownien informatiquement.

Limite d'arbres de Galton-Watson

(voir la section Convergence des arbres de Galton-Watson)

On considère $G_{n}$, un arbre de Galton-Watson dont la loi de reproduction est de variance finie non nulle et conditionné à avoir $n$ nœuds. On note ${\tfrac {1}{\sqrt {n}}}G_{n}$ cet arbre lorsque la longueur des arêtes est divisée par ${\sqrt {n}}$, c'est-à-dire que chaque arête est de longueur ${\tfrac {1}{\sqrt {n}}}$. Construction peut se formaliser en considérant l'arbre de Galton-Watson comme un espace métrique (ou arbre réel) ou en utilisant les processus de contour (ou des hauteurs) et en les renormalisant (voir la formule).

Définition —  Il existe une limite en loi de ${\tfrac {1}{\sqrt {n}}}G_{n}$ vers un arbre réel aléatoire que l'on appelle l'arbre brownien

La limite en loi utilisée ici est la convergence en loi des processus stochastiques dans l'espace de Skorokhod (pour une caractérisation par les processus de contour) ou la convergence en loi définie à partir de la distance de Hausdorff (pour une caractérisation en espace métrique).