2.1 Aléa sur les arbres non marqués
45
Les probabilistes s’intéressent depuis longtemps (voir le livre d’Athreya et
Ney [12]) au processus discret « nombre de nœuds de la n-ième génération ». Plus
précisément, pour tout entier n ∈ N, et pour tout arbre τ , soit
z n (τ ) := {u ∈ τ, |u| = n}
la n-ième génération de τ .
Remarque 2.3 Attention : dans cette section n désigne le numéro de génération
considéré et pas du tout le nombre de nœuds de l’arbre. D’ailleurs les arbres de
Galton-Watson peuvent être infinis.
Le nombre de nœuds de la n-ième génération est
Z n (τ ) := |z n (τ )|.
Si τ est un arbre de Galton-Watson, autrement dit si l’ensemble des arbres planaires
est muni de la loi P, alors (Z n (τ )) n≥0 est un processus de Galton-Watson, noté plus
légèrement (Z n ) n≥0 . En particulier, z 0 (τ ) = {ε} et Z 0 (τ ) = 1.
Propriété de branchement pour (Z n )
Pour tout arbre τ , pour tout u ∈ τ , on désigne par
τ
u
:= {v ∈ U, uv ∈ τ }
le sous-arbre de τ dont la racine est u. Par exemple, τ 1 , . . . , τ M sont les sousarbres issus des enfants de l’ancêtre, ils constituent une forêt. La relation suivante
est évidente : pour tous entiers n et k,
Z n+k (τ ) =
u, |u|=n
Z k (τ
u ).
Elle se décline en deux relations, dites respectivement « backward » et « forward »,
qui sont fondamentales dans l’étude des processus de branchement : pour tout
entier n,
Z n+1 (τ ) =
M
j =1
Z n (τ
j ) ;
(2.2)
Z n+1 (τ ) =
u, |u|=n
M u .
(2.3)
La propriété de branchement, qui était exprimée à la première génération dans la
proposition 2.1 (ii), peut aussi par récurrence s’exprimer à la n-ième génération :
sachant le passé avant n, les sous-arbres τ u qui ont pour racine un nœud u de la