Arbre brownien

Les définitions suivantes sont différentes caractérisations d'un arbre brownien, elles sont issues des trois articles pionniers d'Aldous^[4],[5],[6]. 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.

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

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

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

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.

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 ${\displaystyle 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 ${\displaystyle d}$ sur le support ${\displaystyle [0,1]}$ de cette excursion par

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

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

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

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

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

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

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

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

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

On considère ${\displaystyle G_{n}}$, un arbre de Galton-Watson dont la loi de reproduction est de variance finie non nulle et conditionné à avoir ${\displaystyle n}$ nœuds. On note ${\displaystyle {\tfrac {1}{\sqrt {n}}}G_{n}}$ cet arbre lorsque la longueur des arêtes est divisée par ${\displaystyle {\sqrt {n}}}$, c'est-à-dire que chaque arête est de longueur ${\displaystyle {\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).

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

• Portail des probabilités et de la statistique