44
2 Aléa sur les arbres
2.1.3 Arbres de branchement. Arbres de Galton-Watson
Rappelons (cf. section 1.1.1) qu’un arbre planaire τ ∈ P a été défini (cf. la
définition 1.1) comme ensemble de mots sur l’alphabet N >0 , de sorte qu’un nœud u
d’un arbre τ est une suite finie d’entiers strictement positifs, sa longueur notée |u|
est aussi sa profondeur ou niveau dans l’arbre et son arité est
M u := nombre d’enfants du nœud u,
avec la notation simplifiée M pour M ε les enfants de l’ancêtre. Un tel arbre est
représenté figure 2.3. Nous avions remarqué que la donnée des entiers M u , u ∈ U
suffit à définir l’arbre.
Lorsque les M u deviennent des variables aléatoires, alors l’arbre pousse de
manière aléatoire. Un tel arbre aléatoire est ainsi défini à partir d’une loi de
probabilité pour les M u , à valeurs dans N. Plus précisément :
Proposition-Définition 2.1 Soit (p k ) k≥0 une loi de probabilité sur N, dite loi de
reproduction.
Si M = M ε désigne le nombre d’enfants de l’ancêtre, et si τ 1 , . . . , τ M désignent
les sous-arbres issus des enfants de l’ancêtre, alors il existe une unique probabilité
P sur l’ensemble P des arbres planaires, telle que
(i) M a pour loi (p k ) k≥0 ;
(ii) conditionnellement sachant {M = j }, les sous-arbres τ 1 , . . . , τ j sont indépendants et de même loi P.
Un arbre planaire sous la loi P est un arbre de Galton-Watson de loi de
reproduction (p k ) k≥0 . La propriété (ii) s’appelle propriété de branchement.
Nous renvoyons pour la preuve de cette proposition à Neveu [194, pages 202-203] :
c’est une propriété d’existence de processus de Markov.
Remarque 2.2 L’ensemble des arbres binaires de taille donnée, muni de la distribution uniforme, peut aussi être vu comme l’ensemble des arbres de Galton-Watson
(cf. la section 2.1.3) conditionnés par leur taille ; ce lien probabilité/combinatoire
est détaillé dans la section 5.2.
Fig. 2.3 Un exemple d’arbre
planaire, de Galton-Watson
quand les M u sont aléatoires
2 Aléa sur les arbres
2.1.3 Arbres de branchement. Arbres de Galton-Watson
Rappelons (cf. section 1.1.1) qu’un arbre planaire τ ∈ P a été défini (cf. la
définition 1.1) comme ensemble de mots sur l’alphabet N >0 , de sorte qu’un nœud u
d’un arbre τ est une suite finie d’entiers strictement positifs, sa longueur notée |u|
est aussi sa profondeur ou niveau dans l’arbre et son arité est
M u := nombre d’enfants du nœud u,
avec la notation simplifiée M pour M ε les enfants de l’ancêtre. Un tel arbre est
représenté figure 2.3. Nous avions remarqué que la donnée des entiers M u , u ∈ U
suffit à définir l’arbre.
Lorsque les M u deviennent des variables aléatoires, alors l’arbre pousse de
manière aléatoire. Un tel arbre aléatoire est ainsi défini à partir d’une loi de
probabilité pour les M u , à valeurs dans N. Plus précisément :
Proposition-Définition 2.1 Soit (p k ) k≥0 une loi de probabilité sur N, dite loi de
reproduction.
Si M = M ε désigne le nombre d’enfants de l’ancêtre, et si τ 1 , . . . , τ M désignent
les sous-arbres issus des enfants de l’ancêtre, alors il existe une unique probabilité
P sur l’ensemble P des arbres planaires, telle que
(i) M a pour loi (p k ) k≥0 ;
(ii) conditionnellement sachant {M = j }, les sous-arbres τ 1 , . . . , τ j sont indépendants et de même loi P.
Un arbre planaire sous la loi P est un arbre de Galton-Watson de loi de
reproduction (p k ) k≥0 . La propriété (ii) s’appelle propriété de branchement.
Nous renvoyons pour la preuve de cette proposition à Neveu [194, pages 202-203] :
c’est une propriété d’existence de processus de Markov.
Remarque 2.2 L’ensemble des arbres binaires de taille donnée, muni de la distribution uniforme, peut aussi être vu comme l’ensemble des arbres de Galton-Watson
(cf. la section 2.1.3) conditionnés par leur taille ; ce lien probabilité/combinatoire
est détaillé dans la section 5.2.
Fig. 2.3 Un exemple d’arbre
planaire, de Galton-Watson
quand les M u sont aléatoires