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[1]. Cet arbre a depuis été généralisé et des propriétés fines ont été obtenues.

Pour les articles homonymes, voir Arbre (homonymie).

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

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

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

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 semi-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

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

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

Références

  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)
  • Portail des probabilités et de la statistique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.