50
3 Branchement et processus de Galton-Watson
Nous allons caractériser la loi de N en fonction de la loi de reproduction P .
Tout d’abord, nous pouvons exploiter la propriété de branchement : comme
l’individu racine donne naissance à X 1,1 arbres de Galton-Watson i.i.d., la loi
de N vérifie
N
loi
= 1 +
X1,1
i=1
N
(i)
où les variables aléatoires (N
(i) ) i1 sont i.i.d. de même loi que N . Cette égalité
en loi permet de retrouver la formule E(N ) = (1 − m)
−1
1 m<1 + ∞1 m=1 , et
fournit plus généralement le lemme suivant.
Lemme 3.15 (Fonction génératrice de N ). Si g et f sont les fonctions génératrices respectives de X 1,1 et N , alors la fonction f est solution de l’équation
f (s) = s(g ◦ f )(s) pour s ∈ [0, 1].
Exemple 3.16 (Reproduction géométrique). Si P = Geo N (p) =
n0 q
n pδ n
avec p 1/2, alors f (s) est solution de l’équation qf (s)
2
− f (s) + sp = 0, et
f (s) =
1 −
√
1 − 4pqs
2q
pour s ∈ [0, 1].
Cette équation sur la fonction génératrice n’est pas toujours facile à utiliser. On peut aussi exprimer la loi de N avec des convolutions de la loi P
Théorème 3.17 (Loi de la taille de l’arbre et marche aléatoire). On a
N
loi
= T −1 ,
où T −1 := inf{n 1 : S n = −1} est le temps d’atteinte de −1 d’une marche
aléatoire (S n ) n0 sur Z issue de S 0 = 0 et d’incréments (U i ) i1 tels que
1 + U i ∼ P . De plus, pour tout n 1,
P(N = n) =
P(n, n − 1)
n
=
P
∗n ({n − 1})
n
.
La loi de N peut bien sûr s’obtenir par un calcul direct, sans faire appel
à l’égalité en loi. Cependant, cette si belle identité en loi permet notamment
un contrôle de la queue de distribution, ce qui s’avère utile pour l’étude du
graphe aléatoire de Erdős-Rényi par exemple, voir théorème 16.14.
Démonstration. L’idée consiste à associer bijectivement un arbre fini à une
portion de trajectoire de marche aléatoire. Étant donné un arbre fini de taille
n, on numérote ses sommets en partant de la racine (notée 1) et de gauche
à droite pour des individus d’une même génération. On note ensuite X
(i) le
nombre d’enfants de l’individu i et U i = X
(i)
− 1 pour 1 i n, et on pose
S 0 = 0 et S i+1 = S i + U i+1 pour 0 i n − 1.
3 Branchement et processus de Galton-Watson
Nous allons caractériser la loi de N en fonction de la loi de reproduction P .
Tout d’abord, nous pouvons exploiter la propriété de branchement : comme
l’individu racine donne naissance à X 1,1 arbres de Galton-Watson i.i.d., la loi
de N vérifie
N
loi
= 1 +
X1,1
i=1
N
(i)
où les variables aléatoires (N
(i) ) i1 sont i.i.d. de même loi que N . Cette égalité
en loi permet de retrouver la formule E(N ) = (1 − m)
−1
1 m<1 + ∞1 m=1 , et
fournit plus généralement le lemme suivant.
Lemme 3.15 (Fonction génératrice de N ). Si g et f sont les fonctions génératrices respectives de X 1,1 et N , alors la fonction f est solution de l’équation
f (s) = s(g ◦ f )(s) pour s ∈ [0, 1].
Exemple 3.16 (Reproduction géométrique). Si P = Geo N (p) =
n0 q
n pδ n
avec p 1/2, alors f (s) est solution de l’équation qf (s)
2
− f (s) + sp = 0, et
f (s) =
1 −
√
1 − 4pqs
2q
pour s ∈ [0, 1].
Cette équation sur la fonction génératrice n’est pas toujours facile à utiliser. On peut aussi exprimer la loi de N avec des convolutions de la loi P
Théorème 3.17 (Loi de la taille de l’arbre et marche aléatoire). On a
N
loi
= T −1 ,
où T −1 := inf{n 1 : S n = −1} est le temps d’atteinte de −1 d’une marche
aléatoire (S n ) n0 sur Z issue de S 0 = 0 et d’incréments (U i ) i1 tels que
1 + U i ∼ P . De plus, pour tout n 1,
P(N = n) =
P(n, n − 1)
n
=
P
∗n ({n − 1})
n
.
La loi de N peut bien sûr s’obtenir par un calcul direct, sans faire appel
à l’égalité en loi. Cependant, cette si belle identité en loi permet notamment
un contrôle de la queue de distribution, ce qui s’avère utile pour l’étude du
graphe aléatoire de Erdős-Rényi par exemple, voir théorème 16.14.
Démonstration. L’idée consiste à associer bijectivement un arbre fini à une
portion de trajectoire de marche aléatoire. Étant donné un arbre fini de taille
n, on numérote ses sommets en partant de la racine (notée 1) et de gauche
à droite pour des individus d’une même génération. On note ensuite X
(i) le
nombre d’enfants de l’individu i et U i = X
(i)
− 1 pour 1 i n, et on pose
S 0 = 0 et S i+1 = S i + U i+1 pour 0 i n − 1.