248
6 Arbres binaires de recherche
Nous utilisons le lemme suivant, dû à Chernov (que l’on peut trouver dans tout livre
de base de probabilités, par exemple dans Barbe et Ledoux [15, p. 59]).
Lemme 6.24 Soit (X i ) i≥1 une suite de v.a. i.i.d. de transformée de Laplace donnée
par son logarithme : (λ) := log E
e λX
. Soit S n := X 1 + · · · + X n et soit ∗ la
transformée de Legendre de , définie pour tout ρ ≤ EX par :
∗ (ρ) := sup
λ≤0
{λρ −
Alors, pour tout ρ ≤ EX,
P(S n ≤ ρn) = exp
−n[
∗ (ρ) + o(1)]
.
Appliquons ceci aux v.a X i de loi Exp(1), d’espérance 1, de sorte que pour tout
ρ ≤ 1
P
⎛
⎝
α log n
i=1
X i ≤ ρα log n
⎞
⎠ = exp
−α log n[
∗ (ρ) + o(1)]
.
En imposant ρα = 1 et donc α ≥ 1, la quantité qui nous intéresse
2
α log n
P
⎛
⎝
α log n
i=1
X i ≤ log n
⎞
⎠ = e
α log n[log 2− ∗ (
1
α )+o(1)]
tend vers 0 tant que log 2 < < ∗ (
1
α ). Le meilleur α vérifie donc log 2 = ∗ (
1
α ). Ici,
les variables aléatoires X i suivent chacune une loi exponentielle de paramètre 1, par
conséquent (λ) = − log(1 − λ) et ∗ (ρ) = ρ − 1 − log ρ, ce qui donne α comme
solution (supérieure à 1) de
α log 2 + α − α log α = 1.
Nous avons donc trouvé l’équation qui donne α, apparaissant dans le théorème.
Pour la minoration de H n , ce sont des arguments plus sophistiqués (construction
d’un processus de Galton-Watson couplé) qui interviennent, non détaillés ici (voir
par exemple Broutin et al.[31]).
Remarque 6.25 Des résultats de grandes déviations sur la hauteur (et sur le niveau
de saturation) peuvent être trouvés dans le livre de Drmota [68, Th. 6.47] ; ils
expriment que la hauteur s’éloigne de son espérance et donc de c log n − α log log n
avec une probabilité exponentiellement petite : il existe une constante a telle
que lorsque n tend vers l’infini, pour tout η > 0, P (|h(τ n ) − E(h(τ n ))| ≥ η) =
O
e −aη
.