6.2 Analyse de la hauteur
247
Remarque 6.23 Les constantes c et c du théorème 6.22 sont les mêmes que celles
qui interviennent dans la convergence de la martingale de l’abr au théorème 6.8.
Nous donnons ci-dessous une idée des arguments utilisés pour montrer le
théorème 6.22, du moins pour la hauteur. Pour le niveau de saturation, les arguments
sont analogues. Appelons H n la hauteur du sous-arbre T n de l’arbre idéal, où T n est
précisément l’ensemble des nœuds u tels que n
v≤u U v ≥ 1. Alors
{H n ≥ k} =
n max
u,|u|=k
v≤u
U v ≥ 1
,
de sorte que l’égalité (6.20) et la proposition 6.21 indiquent que l’asymptotique de
H n ressemble à celle de la hauteur d’un abr.
Précisons donc l’asymptotique de H n , qui repose sur des techniques classiques
de grandes déviations (qui se trouvent par exemple dans le livre de Dembo et
Zeitouni [54]).
Tout d’abord,
P(H n ≥ k) = P
n max
u,|u|=k
v≤u
U v ≥ 1
= P
∃u, |u| = k, n
v≤u
U v ≥ 1
≤
|u|=k
P
v≤u
− log U v ≤ log n
.
Or, toutes les v.a. (− log U v ) pour v ≤ u sont i.i.d. de même loi exponentielle
de paramètre 1, à cause de l’indépendance le long d’une branche de l’arbre. Soit
(X i ) i≥1 une suite de v.a. i.i.d. de loi exponentielle de paramètre 1, de sorte que
P(H n ≥ k) ≤ 2
k
P
k
i=1
X i ≤ log n
.
(6.21)
Ceci permet de trouver, selon une approche classique en grandes déviations, une
majoration fine de H n : en effet, dès que, pour un certain k n bien choisi, le membre
de droite de l’inégalité précédente tend vers 0 lorsque n tend vers l’infini, nous
aurons P(H n ≥ k n ) → 0 et donc P(H n < k n ) → 1. Posons k n := α log n et
trouvons le meilleur α tel que, lorsque n tend vers l’infini,
2
α log n
P
⎛
⎝
α log n
i=1
X i ≤ log n
⎞
⎠ → 0.