252
6 Arbres binaires de recherche
la position la plus à droite parmi les individus en vie à l’instant t, alors
R T n = h(τ n ).
Les résultats de Biggins [27] sur R t ont pour corollaire la convergence presque sûre
de
h(τ n )
log n
vers la constante c indiquée dans le théorème 6.22 plus haut.
Quels sont les termes suivant le terme c log n dans le développement
asymptotique de la hauteur ? Reed dans [218] précise le terme suivant pour
l’espérance de la hauteur : quand n tend vers +∞,
E(h(τ n )) = c log n − β log log n + O(1),
où β =
3
2 log(c/2) .
Plus récemment, Roberts [223] a obtenu, à partir d’un résultat spectaculaire
de Hu et Shi [134] sur les marches aléatoires branchantes, le résultat suivant,
à la fois fin (il concerne le second terme en log log n de la hauteur d’un
abr) et surprenant : la hauteur correctement renormalisée varie entre sa limite
inférieure et sa limite supérieure, qui sont différentes, il n’y a donc pas de
limite presque sûre, et pourtant il y a une limite en probabilité 9 ! L’obtention
de ce résultat illustre à nouveau la richesse de la connexion : « la loi de la
hauteur h(τ n ) est asymptotiquement (quand n → +∞) donnée par la position
maximale dans une marche aléatoire branchante ».
Théorème 6.27 Soit a l’unique solution réelle positive de l’équation 2(a −
1)e a +1 = 0 et soit b := 2ae a (numériquement a ≈ 0,76804 et b ≈ 3,31107).
Alors la hauteur h(τ n ) de l’abr au temps n vérifie
1
2
= lim inf
n→∞
ah(τ n ) − b log n
− log log n
< lim sup
n→∞
ah(τ n ) − b log n
− log log n
=
3
2
et
ah(τ n ) − b log n
− log log n
−→
3
2
en probabilité .
Les constantes a et b sont liées aux constantes c et c du théorème 6.22 par :
c = b/a et c = 3/2a.
9 Les différents types de convergence sont rappelés en section C.6.
6 Arbres binaires de recherche
la position la plus à droite parmi les individus en vie à l’instant t, alors
R T n = h(τ n ).
Les résultats de Biggins [27] sur R t ont pour corollaire la convergence presque sûre
de
h(τ n )
log n
vers la constante c indiquée dans le théorème 6.22 plus haut.
Quels sont les termes suivant le terme c log n dans le développement
asymptotique de la hauteur ? Reed dans [218] précise le terme suivant pour
l’espérance de la hauteur : quand n tend vers +∞,
E(h(τ n )) = c log n − β log log n + O(1),
où β =
3
2 log(c/2) .
Plus récemment, Roberts [223] a obtenu, à partir d’un résultat spectaculaire
de Hu et Shi [134] sur les marches aléatoires branchantes, le résultat suivant,
à la fois fin (il concerne le second terme en log log n de la hauteur d’un
abr) et surprenant : la hauteur correctement renormalisée varie entre sa limite
inférieure et sa limite supérieure, qui sont différentes, il n’y a donc pas de
limite presque sûre, et pourtant il y a une limite en probabilité 9 ! L’obtention
de ce résultat illustre à nouveau la richesse de la connexion : « la loi de la
hauteur h(τ n ) est asymptotiquement (quand n → +∞) donnée par la position
maximale dans une marche aléatoire branchante ».
Théorème 6.27 Soit a l’unique solution réelle positive de l’équation 2(a −
1)e a +1 = 0 et soit b := 2ae a (numériquement a ≈ 0,76804 et b ≈ 3,31107).
Alors la hauteur h(τ n ) de l’abr au temps n vérifie
1
2
= lim inf
n→∞
ah(τ n ) − b log n
− log log n
< lim sup
n→∞
ah(τ n ) − b log n
− log log n
=
3
2
et
ah(τ n ) − b log n
− log log n
−→
3
2
en probabilité .
Les constantes a et b sont liées aux constantes c et c du théorème 6.22 par :
c = b/a et c = 3/2a.
9 Les différents types de convergence sont rappelés en section C.6.