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[1]. 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[2] : 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[3] ou par des processus physiques qui obtiennent des structures dendritiques

Définitions modifier

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.

Lois finies dimensionnelles modifier

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

 

 . C'est-à-dire que la loi   ne dépend pas de la forme de l'arbre mais que de la somme totale des longueurs des arêtes.

Définition — Notons   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  , on munit   d'une mesure de probabilité  . Si le sous-arbre de   engendré par   points, choisis aléatoirement par  , a la loi  , alors   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 modifier

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  , une excursion brownienne normalisée, c'est-à-dire conditionnée à être de longueur 1. On définit une pseudo-distance   sur le support   de cette excursion par

  pour tout  

On définit alors une relation d'équivalence, notée  ; sur   qui permet d'identifier les points   tels que   .

 

  est alors une distance sur l'espace quotient  .

Définition — L'espace métrique   est appelé arbre brownien.

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

Fragmentation poissonienne d'une droite modifier

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é  . C'est-à-dire que, pour tout  ,   est une variable de Poisson de paramètre  . Si on note   les points générés par ce processus de Poisson, les longueurs des intervalles   ont une loi exponentielle qui décroit avec  . On effectue alors la construction suivante :

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

Définition —  La fermeture  , 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 modifier

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

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

Propriétés modifier

Références modifier

  1. (en) Jean-François Le Gall, Spatial branching processes, random snakes, and partial differential equations, Basel ; Boston : Birkhäuser, Lectures in mathematics ETH Zürich., , 162 + viii (lire en ligne)
  2. David Aldous, « The continuum random tree » (consulté le )
  3. Grégory Miermont, « Une simulation de l'arbre continu aléatoire brownien » (consulté le )
  4. (en) David Aldous, « The Continuum Random Tree. I », The Annals of Probability, vol. 19, no 1,‎ , p. 1-28 (lire en ligne)
  5. (en) David Aldous, « The Continuum Random Tree II: an overview », Proc. Durham Symp. Stochastic Analysis,‎ , p. 23-70 (lire en ligne)
  6. (en) David Aldous, « The Continuum Random Tree. III », The Annals of Probability, vol. 21, no 1,‎ , p. 248-289 (lire en ligne)