200
5 Approche probabiliste
Par ailleurs, pour un arbre de Galton-Watson τ de loi de Poisson, avec la formule (5.9),
P(τ = t
|τ | = n) =
n
i=1 e −λ λ y i /(y i )!
P(|τ | = n)
=
e −nλ λ n−1
y 1 ! . . . y n !P(|τ | = n)
.
Pour un n-uplet (y 1 , . . . , y n ) fixé, ces deux expressions sont proportionnelles et sont
des probabilités. Elles sont donc égales, ce qui prouve la proposition.
5.2.3 Largeur et hauteur des arbres sous le modèle de Catalan
Considérer des arbres de Galton-Watson conditionnés par leur taille pose la question
naturelle de la monotonie : est-il possible de considérer un arbre de taille n + 1
comme l’extension d’un arbre de taille n, alors qu’ils proviennent de deux conditionnements différents ? La réponse est non (voir Janson [148] et l’exercice 5.4). Le
raisonnement est basé sur la loi asymptotique qui est apparue dans le théorème 5.9
: un arbre de Galton-Watson conditionné par sa taille n converge vers l’arbre biaisé,
lorsque n tend vers l’infini.
Néanmoins, le lien Galton-Watson/Catalan ouvre de larges perspectives vers de
nombreux résultats asymptotiques, lorsque la taille tend vers l’infini. Il a été démontré (par Aldous [4, 5], Chassaing et Marckert [35], Drmota et Gittenberger [69, 70])
que la largeur w(τ n ) et la hauteur h(τ n ) d’un arbre binaire ou planaire de taille n sous
le modèle de Catalan sont d’ordre
√
n, et une fois renormalisés convergent vers la
même limite (!) qui ne dépend pas de la loi de reproduction du Galton-Watson, mais
seulement de sa variance, comme l’indique le résultat suivant.
Théorème 5.19 Soit τ n un arbre de Galton-Watson critique de loi de reproduction de variance σ 2 finie, conditionné à être de taille n. Lorsque n tend
vers l’infini,
1
√
n
w(τ n ),
1
√
n
h(τ n )
D
−→
n→∞
σ W,
2
σ
W
,
où σ 2 est la variance de la loi de reproduction du Galton-Watson et où W est
le maximum d’une excursion brownienne sur [0, 1].
5 Approche probabiliste
Par ailleurs, pour un arbre de Galton-Watson τ de loi de Poisson, avec la formule (5.9),
P(τ = t
|τ | = n) =
n
i=1 e −λ λ y i /(y i )!
P(|τ | = n)
=
e −nλ λ n−1
y 1 ! . . . y n !P(|τ | = n)
.
Pour un n-uplet (y 1 , . . . , y n ) fixé, ces deux expressions sont proportionnelles et sont
des probabilités. Elles sont donc égales, ce qui prouve la proposition.
5.2.3 Largeur et hauteur des arbres sous le modèle de Catalan
Considérer des arbres de Galton-Watson conditionnés par leur taille pose la question
naturelle de la monotonie : est-il possible de considérer un arbre de taille n + 1
comme l’extension d’un arbre de taille n, alors qu’ils proviennent de deux conditionnements différents ? La réponse est non (voir Janson [148] et l’exercice 5.4). Le
raisonnement est basé sur la loi asymptotique qui est apparue dans le théorème 5.9
: un arbre de Galton-Watson conditionné par sa taille n converge vers l’arbre biaisé,
lorsque n tend vers l’infini.
Néanmoins, le lien Galton-Watson/Catalan ouvre de larges perspectives vers de
nombreux résultats asymptotiques, lorsque la taille tend vers l’infini. Il a été démontré (par Aldous [4, 5], Chassaing et Marckert [35], Drmota et Gittenberger [69, 70])
que la largeur w(τ n ) et la hauteur h(τ n ) d’un arbre binaire ou planaire de taille n sous
le modèle de Catalan sont d’ordre
√
n, et une fois renormalisés convergent vers la
même limite (!) qui ne dépend pas de la loi de reproduction du Galton-Watson, mais
seulement de sa variance, comme l’indique le résultat suivant.
Théorème 5.19 Soit τ n un arbre de Galton-Watson critique de loi de reproduction de variance σ 2 finie, conditionné à être de taille n. Lorsque n tend
vers l’infini,
1
√
n
w(τ n ),
1
√
n
h(τ n )
D
−→
n→∞
σ W,
2
σ
W
,
où σ 2 est la variance de la loi de reproduction du Galton-Watson et où W est
le maximum d’une excursion brownienne sur [0, 1].