198
5 Approche probabiliste
Proposition 5.17 Soit (p k ) k≥0 une loi de probabilité sur N telle que m =
k kp k ≤ 1. Soit τ l’arbre de Galton-Watson associé. Alors
(i) Pour tout α ∈]0, 1[, si τ est un arbre de Galton-Watson binaire défini par la loi
(p k ) k≥0 avec p 2 = α, p 0 = 1 − α, alors τ , conditionné à être de taille n, suit
la loi uniforme sur l’ensemble B n des arbres binaires complets à n nœuds.
(ii) Pour tout α ∈]0, 1[, si τ est un arbre de Galton-Watson planaire de loi
géométrique définie par p k = α(1 − α) k pour k ≥ 0, alors τ , conditionné
à être de taille n, suit la loi uniforme sur l’ensemble P n des arbres planaires à
n nœuds.
Ainsi,
(i) Un arbre de Galton-Watson binaire, conditionné à être de taille n, suit la loi
uniforme sur l’ensemble B n des arbres binaires complets à n nœuds.
(ii) Un arbre de Galton-Watson planaire de loi géométrique, conditionné à être de
taille n, suit la loi uniforme sur l’ensemble P n des arbres planaires à n nœuds.
Preuve
(i) Avec la formule (5.10), la probabilité
P(τ = t
|τ | = 2n + 1) =
p
n+1
0 p n
2
P(|τ | = 2n + 1)
ne dépend pas de y 1 , . . . , y n c’est-à-dire de la forme de l’arbre. Tous les arbres
binaires complets de taille 2n + 1 sont donc équiprobables. Nous retrouvons
bien les arbres sous le modèle de Catalan du chapitre 4.
(ii) La formule (5.9) donne
P(τ = t
|τ | = n) =
n
i=1 α(1 − α) y i
P(|τ | = n)
=
α n (1 − α) n−1
P(|τ | = n)
qui est une expression qui ne dépend pas non plus de y 1 , . . . , y n c’est-àdire de la forme de l’arbre. Tous les arbres planaires de taille n sont donc
équiprobables.
5.2.2 Pour les arbres de Cayley
Rappelons (cf. section 1.2.3) qu’un arbre de Cayley est un arbre non planaire marqué
par des entiers positifs distincts. Pour le représenter sur un dessin, nous convenons
que les fils d’un même nœud portent des marques croissantes de gauche à droite.
L’ensemble des arbres de Cayley à n nœuds est appelé Cay n et cet ensemble a été
dénombré section 4.5.1.
Proposition 5.18 Pour tout λ > 0, un arbre de Galton-Watson de loi de Poisson
de paramètre λ (c’est-à-dire que la loi de reproduction (p k ) k≥0 est définie par :
5 Approche probabiliste
Proposition 5.17 Soit (p k ) k≥0 une loi de probabilité sur N telle que m =
k kp k ≤ 1. Soit τ l’arbre de Galton-Watson associé. Alors
(i) Pour tout α ∈]0, 1[, si τ est un arbre de Galton-Watson binaire défini par la loi
(p k ) k≥0 avec p 2 = α, p 0 = 1 − α, alors τ , conditionné à être de taille n, suit
la loi uniforme sur l’ensemble B n des arbres binaires complets à n nœuds.
(ii) Pour tout α ∈]0, 1[, si τ est un arbre de Galton-Watson planaire de loi
géométrique définie par p k = α(1 − α) k pour k ≥ 0, alors τ , conditionné
à être de taille n, suit la loi uniforme sur l’ensemble P n des arbres planaires à
n nœuds.
Ainsi,
(i) Un arbre de Galton-Watson binaire, conditionné à être de taille n, suit la loi
uniforme sur l’ensemble B n des arbres binaires complets à n nœuds.
(ii) Un arbre de Galton-Watson planaire de loi géométrique, conditionné à être de
taille n, suit la loi uniforme sur l’ensemble P n des arbres planaires à n nœuds.
Preuve
(i) Avec la formule (5.10), la probabilité
P(τ = t
|τ | = 2n + 1) =
p
n+1
0 p n
2
P(|τ | = 2n + 1)
ne dépend pas de y 1 , . . . , y n c’est-à-dire de la forme de l’arbre. Tous les arbres
binaires complets de taille 2n + 1 sont donc équiprobables. Nous retrouvons
bien les arbres sous le modèle de Catalan du chapitre 4.
(ii) La formule (5.9) donne
P(τ = t
|τ | = n) =
n
i=1 α(1 − α) y i
P(|τ | = n)
=
α n (1 − α) n−1
P(|τ | = n)
qui est une expression qui ne dépend pas non plus de y 1 , . . . , y n c’est-àdire de la forme de l’arbre. Tous les arbres planaires de taille n sont donc
équiprobables.
5.2.2 Pour les arbres de Cayley
Rappelons (cf. section 1.2.3) qu’un arbre de Cayley est un arbre non planaire marqué
par des entiers positifs distincts. Pour le représenter sur un dessin, nous convenons
que les fils d’un même nœud portent des marques croissantes de gauche à droite.
L’ensemble des arbres de Cayley à n nœuds est appelé Cay n et cet ensemble a été
dénombré section 4.5.1.
Proposition 5.18 Pour tout λ > 0, un arbre de Galton-Watson de loi de Poisson
de paramètre λ (c’est-à-dire que la loi de reproduction (p k ) k≥0 est définie par :