5.2 Modèle de Catalan et arbres de Galton-Watson
201
On remarquera, en appliquant la proposition 5.17, que
– pour les arbres binaires sous le modèle de Catalan, l’arbre de Galton-Watson
critique adéquat est obtenu pour p 0 = p 2 = 1/2 et donc la variance est égale à
1, soit σ = 1 dans le théorème précédent ;
– pour les arbres planaires sous le modèle de Catalan, l’arbre de Galton-Watson
critique adéquat est obtenu pour une loi géométrique de paramètre 1/2 et donc la
variance est égale à 2, soit σ =
√
2 dans le théorème précédent.
La partie de ce théorème relative à la hauteur des arbres planaires sous le modèle
de Catalan est détaillée ci-après.
Hauteur des arbres planaires sous le modèle de Catalan
Ce résultat peut se prouver de deux manières, toutes deux détaillées notamment dans
le livre de Drmota [68, Chap 4].
Une première manière d’obtenir la loi limite de h(τ n )/
√
n est
combinatoire, due aux travaux de Flajolet et ses co-auteurs [88, 89, 98] ou [94,
p. 328, section V.4.3 et p. 535, section VII.10.2] : on compte la proportion
d’arbres de taille n et de hauteur h via leur fonction génératrice et un calcul de
résidus (ou la formule de Stirling) conduit à la loi Theta (voir l’annexe C.3.4)
et au théorème suivant.
Théorème 5.20 La hauteur normalisée d’un arbre planaire de taille n sous
le modèle de Catalan,
h(τ n )
√
πn
, converge en distribution vers une variable
aléatoire de loi Theta lorsque n tend vers l’infini.
Une deuxième manière consiste à s’inscrire dans les méthodes asymptotiques
relatives à l’arbre continu d’Aldous ; introduit par Aldous [3, 4] et développé par
Duquesne et Le Gall [72], cet arbre est un objet limite obtenu à partir d’un arbre de
Galton-Watson de taille n lorsque les distances à la racine sont renormalisées par
1/
√
n.
Mettons en avant quelques idées de démonstration. Ci-dessous dans (a), la
construction de la correspondance bijective entre arbres et chemins de Dyck est
élémentaire. Ensuite dans (b), l’approximation du mouvement brownien par une
marche aléatoire discrète est assez intuitive. Et enfin l’identification de la loi limite
repose dans (c) sur des calculs de loi relatifs au mouvement brownien.
201
On remarquera, en appliquant la proposition 5.17, que
– pour les arbres binaires sous le modèle de Catalan, l’arbre de Galton-Watson
critique adéquat est obtenu pour p 0 = p 2 = 1/2 et donc la variance est égale à
1, soit σ = 1 dans le théorème précédent ;
– pour les arbres planaires sous le modèle de Catalan, l’arbre de Galton-Watson
critique adéquat est obtenu pour une loi géométrique de paramètre 1/2 et donc la
variance est égale à 2, soit σ =
√
2 dans le théorème précédent.
La partie de ce théorème relative à la hauteur des arbres planaires sous le modèle
de Catalan est détaillée ci-après.
Hauteur des arbres planaires sous le modèle de Catalan
Ce résultat peut se prouver de deux manières, toutes deux détaillées notamment dans
le livre de Drmota [68, Chap 4].
Une première manière d’obtenir la loi limite de h(τ n )/
√
n est
combinatoire, due aux travaux de Flajolet et ses co-auteurs [88, 89, 98] ou [94,
p. 328, section V.4.3 et p. 535, section VII.10.2] : on compte la proportion
d’arbres de taille n et de hauteur h via leur fonction génératrice et un calcul de
résidus (ou la formule de Stirling) conduit à la loi Theta (voir l’annexe C.3.4)
et au théorème suivant.
Théorème 5.20 La hauteur normalisée d’un arbre planaire de taille n sous
le modèle de Catalan,
h(τ n )
√
πn
, converge en distribution vers une variable
aléatoire de loi Theta lorsque n tend vers l’infini.
Une deuxième manière consiste à s’inscrire dans les méthodes asymptotiques
relatives à l’arbre continu d’Aldous ; introduit par Aldous [3, 4] et développé par
Duquesne et Le Gall [72], cet arbre est un objet limite obtenu à partir d’un arbre de
Galton-Watson de taille n lorsque les distances à la racine sont renormalisées par
1/
√
n.
Mettons en avant quelques idées de démonstration. Ci-dessous dans (a), la
construction de la correspondance bijective entre arbres et chemins de Dyck est
élémentaire. Ensuite dans (b), l’approximation du mouvement brownien par une
marche aléatoire discrète est assez intuitive. Et enfin l’identification de la loi limite
repose dans (c) sur des calculs de loi relatifs au mouvement brownien.