Chapitre 5
Approche probabiliste
Dans ce chapitre, comme à la section 2.1.3, un arbre pousse de manière aléatoire,
parce que chaque nœud a un nombre aléatoire de descendants, de moyenne m.
Pour un arbre de Galton-Watson, à la section 5.1, nous nous demandons d’abord
(section 5.1.1) si un tel arbre s’éteint ou bien grossit indéfiniment. Cela dépend
de m. Puis, lorsqu’il ne s’éteint pas toujours, c’est-à-dire lorsque m > 1, nous
cherchons à connaître le nombre de nœuds au niveau n. Quel est son ordre de
grandeur asymptotiquement en n ? Intuitivement c’est m n et nous verrons que sous
certaines hypothèses sur la loi de reproduction, c’est effectivement le cas, c’est le
théorème de Kesten-Stigum de la section 5.1.3.
Certains arbres étudiés au chapitre 4 (arbres binaires, arbres planaires, arbres
de Cayley sous la loi uniforme) peuvent être vus comme des arbres de GaltonWatson conditionnés par leur taille ; c’est ce qui est expliqué puis exploité dans
la section 5.2.
Enfin, dans la section 5.3 sont présentées les marches aléatoires branchantes,
qui sont des arbres de Galton-Watson dont les nœuds sont marqués par leur
position dans l’espace. Ce modèle est très riche et fait l’objet d’une vaste littérature,
néanmoins nous nous bornons ici à présenter ce qui est utile à l’étude de la hauteur
des arbres binaires de recherche au chapitre 6.
5.1 Arbres de Galton-Watson
Nous avons vu à la section 2.1.3 que le modèle le plus simple d’arbre de
branchement est l’arbre de Galton-Watson. En résumé, nous nous donnons une
loi de probabilité (p k ) k≥0 sur les entiers positifs ou nuls, qui induit une loi de
probabilité P sur les arbres planaires. Pour tout entier n, appelons (Z n ) n≥0 le
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_5
183
Approche probabiliste
Dans ce chapitre, comme à la section 2.1.3, un arbre pousse de manière aléatoire,
parce que chaque nœud a un nombre aléatoire de descendants, de moyenne m.
Pour un arbre de Galton-Watson, à la section 5.1, nous nous demandons d’abord
(section 5.1.1) si un tel arbre s’éteint ou bien grossit indéfiniment. Cela dépend
de m. Puis, lorsqu’il ne s’éteint pas toujours, c’est-à-dire lorsque m > 1, nous
cherchons à connaître le nombre de nœuds au niveau n. Quel est son ordre de
grandeur asymptotiquement en n ? Intuitivement c’est m n et nous verrons que sous
certaines hypothèses sur la loi de reproduction, c’est effectivement le cas, c’est le
théorème de Kesten-Stigum de la section 5.1.3.
Certains arbres étudiés au chapitre 4 (arbres binaires, arbres planaires, arbres
de Cayley sous la loi uniforme) peuvent être vus comme des arbres de GaltonWatson conditionnés par leur taille ; c’est ce qui est expliqué puis exploité dans
la section 5.2.
Enfin, dans la section 5.3 sont présentées les marches aléatoires branchantes,
qui sont des arbres de Galton-Watson dont les nœuds sont marqués par leur
position dans l’espace. Ce modèle est très riche et fait l’objet d’une vaste littérature,
néanmoins nous nous bornons ici à présenter ce qui est utile à l’étude de la hauteur
des arbres binaires de recherche au chapitre 6.
5.1 Arbres de Galton-Watson
Nous avons vu à la section 2.1.3 que le modèle le plus simple d’arbre de
branchement est l’arbre de Galton-Watson. En résumé, nous nous donnons une
loi de probabilité (p k ) k≥0 sur les entiers positifs ou nuls, qui induit une loi de
probabilité P sur les arbres planaires. Pour tout entier n, appelons (Z n ) n≥0 le
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_5
183