Arbre de Galton-Watson

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Arbre (homonymie).
Simulation d'un arbre de Galton-Watson avec une loi de Poisson de paramètre 1 pour loi de reproduction. Cet arbre contient 11 générations et 47 nœuds.

L'arbre de Galton-Watson est un objet mathématique aléatoire utilisé dans la théorie des probabilités. C'est un arbre planaire enraciné dont chaque nœud a un nombre aléatoire de fils et ce nombre ne dépend ni de la position du nœud dans l'arbre ni du nombre de fils des autres nœuds. Un formalisme des arbres de Galton-Watson a été introduit, par Jacques Neveu en 1986, comme représentation de la généalogie des processus de Galton-Watson.

Cet article traite principalement du cas où les arbres sont de taille finie.

Formalisme des arbres discrets[modifier | modifier le code]

Un arbre de Galton-Watson est un arbre (graphe connexe sans cycles) enraciné que l'on note G=(V,E) où V est l'ensemble des nœuds de l'arbre ("vertex" en anglais) et E est l'ensemble des arêtes ("edge" en anglais). Notons ρV la racine de l'arbre. Donnons une interprétation des arbres de Galton-Watson avec le vocabulaire d'un arbre généalogique.

  • La racine ρ est appelée l'ancêtre commun,
  • pour chaque nœud (ou individu) vV   \   {ρ}, le premier nœud sur la trajectoire (unique) de v vers ρ est appelé le père de v.

Notation de Neveu

Figure 1 : Notation de Neveu pour les sommets d'un arbre planaire.
  • La racine ρ est notée , l'ensemble vide,
  • les fils de ρ sont notés par un entier indiquant leur position dans la fratrie : {1},{2},{3},...
  • pour un individu v, noté {v1,v2,v3,...,vn}, de l'arbre, ses fils seront notés : v1:={v1,v2,v3,...,vn,1}, v2:={v1,v2,v3,...,vn,2}, v3:={v1,v2,v3,...,vn,3},...

Ainsi, un arbre (fini) est défini comme un sous-ensemble ω de l'ensemble des suites finies d'entiers strictement positifs (par convention ) et qui vérifie les trois conditions suivantes :

  1. ,
  2. ,
  3. Pour tout , il existe avec pour .

Dans ce cas ces arbres sont appelés arbres ordonnés et enracinés. Notons l'ensemble des arbres ordonnés et enracinés.

Pour simplifier la notation, il est courant d'utiliser v1v2v3...vn pour {v1,v2,v3,...,vn}. L'entier n est alors appelé la génération de v ou la hauteur de v dans l'arbre, c'est également la distance (de graphe) du nœud à la racine, on le note |v|. La géneration de la racine est 0. L'entier positif kv(ω) est le nombre d'enfant du nœud v, il est noté kv s'il n'y a pas d'ambiguïté. Pour un nœud vj de l'arbre, chaque couple (v,vj) est une arête (ou branche de l'arbre). Un nœud f de l'arbre qui n'a pas de fils, c'est-à-dire tel que kf=0, est une feuille de l'arbre. Les autres nœuds sont appelés nœuds de branchement.

Il est utile de considérer la notion d'arbre "décalé" (shifted tree en anglais). Pour un arbre , et pour v un nœud de ω, l'arbre "décalé" est intuitivement le sous-arbre de ω "au dessus" du nœud v.

L'ensemble U est dénombrable, il peut alors être ordonné en utilisant l'ordre lexicographique par exemple. Ordonnons un arbre fini ω (dont le nombre total de nœuds est un entier |ω| fini) avec l'ordre lexicographique, définissons son parcours de l'arbre en profondeur : on commence par la racine de l'arbre, puis lorsqu'on arrive à un nœud v, on visite son premier fils non encore visité ou on retourne à son père si tous les fils ont été visités, enfin le parcours se termine lorsqu'on revient à la racine et que tous ses fils ont été visités. Par ce parcours, les feuilles sont visitées une fois tandis que les autres nœuds sont visités plusieurs fois. Le nombre total de visites est alors 2|ω|.

Exemple

Dans la figure 1 ci-contre, l'individu 1221 est le premier fils, du deuxième fils, du deuxième fils, du premier fils, de l'ancêtre commun. C'est une feuille de l'arbre de géneration 4. La suite (, 1, 11, 111, 1111, 111, 11, 1, 12, 121, 12, 122, 1221, 122, 12, 1, , 2, , 3, ) est le parcours en profondeur de l'arbre.

Définition formelle[modifier | modifier le code]

Soit μ=(μ(n),n ≥ 0) une loi de probabilité sur critique ou sous-critique, c'est-à-dire telle que :

.

On exclut le cas trivial μ(1)=1.

Il existe une unique loi de probabilité sur l'ensemble des arbres ordonnés et enracinés telle que :

  1.     , pour tout ,
  2.     pour tout tel que μ(j) > 0, les arbres « décalés » sont indépendants sous la loi conditionnelle et leur loi conditionnelle est .

Un arbre aléatoire de loi est appelé un arbre de Galton-Watson avec loi de reproduction μ. (voir §0.2 de Duquesne et Le Gall[1] ou §3 de Neveu[2]).

Intuitivement, la première condition signifie que la loi de reproduction de la racine est μ ; la deuxième condition signifie que les sous-arbres « au-dessus » des fils de la racine sont indépendants les uns des autres et ont tous la même loi qui est celle de l'arbre entier.

Représentation des arbres[modifier | modifier le code]

Un arbre est la donnée des nœuds avec leur nombre de fils ordonnés par ordre lexicographique. Il y a donc plusieurs représentations possibles.

  • La racine peut se représenter en bas, en haut, à gauche, à droite, au centre (pour un arbre dessiné en cercles),...
  • Les nœuds peuvent se représenter par des points ou par des segments (horizontaux, verticaux, ...), ou encore par des arcs de cercle. Tous les nœuds de même génération sont à la même hauteur ou non.
  • Les arêtes peuvent se dessiner par des segments tous de même longueur ou non, reliant directement le nœud père et le nœud fils, ou encore reliant le fils et le segment/nœud père, …
  • l'angle entre les arêtes peut être variable.

Voici quelques exemples.

Différentes représentations d'un même arbre. Ici les racines sont en bas. Les deux arbres de gauche montrent les générations, les trois de droite ont leurs arêtes de même longueur.

Caractérisations d'un arbre de Galton-Watson[modifier | modifier le code]

La donnée d'un arbre ω équivaut à la donnée de la suite (kv(ω),vU). Ainsi, un arbre de Galton-Watson T peut être défini par une suite de variables aléatoires iid (indépendantes et identiquement distribuées) à valeurs entières positives.

Il est à remarquer que certaines valeurs de cette suite n'ont pas d'influence sur l'arbre. Le nombre d'éléments efficaces de correspond au nombre (aléatoire) total de nœuds dans l'arbre de Galton-Watson.

Exemple

La suite finie, donnée par ordre lexicographique, (k, k1, k11,k111,k111,k12,k121,k122,k1221,k2,k3)= (3,2,1,1,0,2,0,1,0,0,0) caractérise l'arbre de la figure 1. La valeur de k4 ne joue pas de rôle ici puisque la racine n'a pas de quatrième fils.

Marche de Łukasiewicz[modifier | modifier le code]

Figure 2 : Arbre fini et sa marche de Łukasiewicz associée.

Pour un arbre fini ω, la marche de Łukasiewicz est définie par :

                
               

est le k-ième individu de l'arbre par ordre lexicographique. La suite V caractérise l'arbre ω, puisqu'elle est équivalente à la donnée de la suite .

Propriétés

  • pour tout 0k|ω|-1, V(k) ≥ 0,
  • V(|ω|)= -1,
  • ses accroissements sont à valeurs dans {-1, 0, 1,...},
Figure 3 : Construction de l'arbre (en bleu avec nœuds en rouge) à partir d'une marche de Łukasiewicz.

Proposition (voir §0.2 de Duquesne et Le Gall[1])

Si T est un arbre de Galton-Watson de loi de reproduction donnée par est la probabilité d'avoir n fils, alors V est une marche aléatoire dont la loi des sauts est donnée par et stoppée lorsqu'elle atteint -1.


Remarque

Soit k un entier fixé. Si un entier nk-1 vérifie la condition , alors l'individu dénommé n est un ancêtre de l'individu k. On peut ainsi reconstituer l'arbre à partir de la trajectoire de la marche de Łukasiewicz en reliant les points (n,V(n)) du graphe de V avec ses infima précédents (voir Figure 3 ci-contre).

Processus de contour[modifier | modifier le code]

Figure 4 : Arbre fini et son processus de contour associé. en bleu: parcours en profondeur.


Pour un arbre fini ω, le processus de contour (ou fonction de contour ou marche de Harris ou chemin de Dyck) est défini par :

                                      

qui, à chaque étape k du parcours en profondeur, associe la génération de l'individu vk visité. Le processus de contour est parfois défini comme l'interpolation linéaire de la fonction C, on garde alors la même notation.

Le nom contour est issu du parcours en profondeur qui "contourne l'arbre par la gauche".

Figure 5 : Construction de l'arbre (en bleu avec les nœuds en rouge) à partir d'un processus de contour.


Propriétés

  • La fonction C est positive,
  • elle s'annule en 0 et en 2|ω|-1,
  • pour tout 1k2|ω|-1, ,
  • il existe une bijection entre les arbres de taille n et les fonctions (voir §6.3 de Pitman[3]).

Proposition (voir §6.3 de Pitman[3])

Si T est un arbre de Galton-Watson conditionné à avoir n nœuds et dont la loi de reproduction est une loi géométrique, alors son processus de contour est l'excursion d'une marche aléatoire simple conditionnée à avoir une longueur 2n.

Si T est un arbre de Galton-Watson conditionné à avoir n nœuds avec une loi de reproduction quelconque, alors son processus de contour n'est plus l'excursion d'un processus aléatoire markovien.


Remarque

Le processus de contour prend la même valeur aux différents passages du parcours en profondeur en un même nœud de l'arbre. On peut ainsi représenter un nœud de l'arbre par un segment horizontal sous le graphe du processus de contour. Les excursions du graphe "au-dessus" de ce segment correspondent aux sous-arbres "au-dessus" de ce nœud. On peut ainsi reconstituer l'arbre à partir du processus de contour (voir Figure 5 ci-contre).

Processus des hauteurs[modifier | modifier le code]

Figure 6 : Arbre fini et son processus des hauteurs associé.

Pour un arbre fini ω, le processus des hauteurs (ou fonction des hauteurs) est défini par :

                                    

tel que H(k) soit la génération du k-ième individu de l'arbre par ordre lexicographique.

Intuitivement, le processus des hauteurs est similaire au processus de contour mais chaque individu de l'arbre n'est visité qu'une fois.

Propriétés

  • La fonction H sont strictement positive pour tout 1k|ω|-1,
  • elle s'annule en 0,
  • ses accroissements sont à valeurs dans {..., -2, -1, 0, 1},
  • le processus des hauteurs caractérise l'arbre ω.

Proposition (voir §0.2 de Duquesne et Le Gall[1])

Soit T est un arbre de Galton-Watson de loi de reproduction donnée par est la probabilité d'avoir n fils et H son processus des hauteurs associé. Alors ce dernier n'est pas un processus aléatoire markovien mais il peut s'écrit en fonction de la marche de Łukasiewicz V associée à T par la formule :

Proposition

On peut retrouver le processus de contour à partir du processus des hauteurs. Notons K(n)= 2n-H(n). On retrouve le processus de contour par la formule (donnée ici pour l'interpolation linéaire) :

                       si
                  si

Liens avec les processus de Galton-Watson[modifier | modifier le code]

Considérons un arbre de Galton-Watson T de loi de reproduction μ. Considérons Zn(T) le nombre d'individus à la n-ième génération, potentiellement nul :

Proposition (voir §3 de Neveu[2])

La suite (Zn(T),n ≥ 1) de variables aléatoires est un processus de Galton-Watson de loi de reproduction μ et partant de Z0(T)=1.

Remarques

  • Le temps du processus de Galton-Watson correspond à la génération de l'arbre associé,
  • La probabilité d'extinction d'un processus de Galton-Watson (probabilité qu'en un temps fini N on ait ZN(T)=0) correspond à la probabilité que l'arbre associé soit fini (qu'il contienne un nombre fini d'individus, c'est-à-dire un nombre fini de générations).

Théorème

En fonction de la moyenne m associée à la loi de reproduction μ, on distingue trois cas :

  • Cas souscritique (m<1). La probabilité que l'arbre de Galton-Watson soit fini vaut 1.
  • Cas critique (m =1). La probabilité que l'arbre de Galton-Watson soit fini vaut 1 (on rappelle que μ(1)≠1)
  • Cas surcritique (m>1). La probabilité que l'arbre de Galton-Watson soit fini est strictement inférieure à 1.

Forêt de Galton-Watson[modifier | modifier le code]

Une forêt de Galton-Watson de loi de reproduction μ est une suite (finie ou infinie) d'arbres de Galton-Watson indépendants de même loi de reproduction μ. La loi d'une forêt de Galton-Watson est une loi de probabilité sur l'espace .

Considérons une forêt de Galton-Watson . Notons , et la marche de Łukasiewicz, le processus de contour et le processus des hauteurs de l'arbre Tk. On pose également H|Tk|(Tk)=0. La marche de Łukasiewicz , le processus de contour , et le processus des hauteurs de sont les concaténations respectives des marches de Łukasiewicz, des processus de contour et des processus des hauteurs des arbres de la forêt :

   si   ,
                  si   ,
                     si   .

Si la forêt est une suite finie d'arbres, ces trois processus restent constants après la dernière valeur issue de la définition précédente.

Notons une forêt de k arbres et conditionnées à avoir n nœuds, c'est-à-dire une forêt (T1,...,Tk) sous la loi conditionnelle . Les forêts conditionnelles sont caractérisées par les trois précédents processus.

Proposition

Soit une forêt de Galton-Watson de loi . Sous la loi la marche de Łukasievwicz jusqu'au temps m, a même loi que la marche de Łukasievwicz stoppée lorsqu'elle atteint le niveau -k.

Convergence des arbres de Galton-Watson[modifier | modifier le code]

Considérons une suite de processus de Galton-Watson telle que chaque processus de Galton-Watson ait pour loi de reproduction (critique ou sous-critique) et . C'est-à-dire qu'il y a initialement p individus.

Notons , et les suites des marches de Łukasiewicz, des processus de contour et des processus des hauteurs des forêts associées à .

Le théorème suivant donne un résultat de convergence type Donsker pour ces processus discrets vers des processus continus.

Théorème (citons Grimvall en 1974, Duquesne et Le Gall en 2002[1])

Sous une hypothèse technique donnée dans la remarque en fin de Théorème, il existe une suite croissante d'entiers naturels convergente vers telle que :

et

où [.] est la partie entière et la convergence est une convergence en loi des processus stochastiques dans l'espace de Skorokhod.

  • le processus est un processus stochastique à temps continu et à valeurs continues appelé processus de branchement à espace d'état continu (CSBP) de mécanisme de branchement ψ. C'est l'analogue continu d'un processus de Galton-Watson.
  • Le processus est un processus de Lévy (à temps continu et à valeurs continues) sans sauts négatifs et qui ne tend pas vers . Son exposant de Laplace est ψ.
  • Le processus est un processus stochastique à temps continus et à valeurs continues appelé le processus des hauteurs (continu) associé à X et à Y.

Intuitivement, il existe des renormalisations en espace et en temps telles que les quatre suites de processus discrets codant des forêts discrètes convergent (en loi) vers des processus continus lorsque le nombre de racines des forêts tend vers .

Remarques

  • hypothèse technique : le Théorème précédent est vrai sous les deux conditions suivantes :
     et      .
  • On peut construire un arbre continu (analogue des arbres discrets) en utilisant les méthodes précédentes pour les arbres de Galton-Watson. L'arbre obtenu est appelé arbre réel.

Cas particulier

Dans le cas où les lois de reproduction sont à variance finie, Le processus X est un mouvement brownien standard et le processus H est un mouvement brownien réfléchi en 0. L'arbre associé est appelé arbre brownien.

Annexes[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a b c et d (en) T. Duquesne et J.-F. Le Gall, Random Trees, Lévy Processes ans Spatial Branching Processes, Astérisque (2002), vol. 281, (ISBN 2-85629-128-7)
  2. a et b (fr) J. Neveu, Arbres et processus de Galton-Watson, Annales de l'IHP - section B, Vol. 22(2), (1986),p. 199-207 .
  3. a et b (en) J. Pitman, Combinatorial Stochastic Processes, Springer - Lecture Note in Mathematics - Ecole d'été de Proba. de St Flour XXXII (2002), (ISBN 3-540-30990-X)
  • (en) T. E. Harris, « First passage and recurrence distributions », Trans. Amer. Math. Soc., vol. 73,‎ , p. 471-486