234
6 Arbres binaires de recherche
On montre que cette transformation S est une contraction 3 dans (M, d). Par
le théorème du point fixe de Banach, il existe alors une unique solution de
l’équation Y = S(Y ) dans M, autrement dit, la loi de Y est caractérisée par
cette équation.
Etape 4. Il s’agit de montrer la convergence en loi de Y n vers Y . Pour cela il suffit
de montrer, si la distance a été bien choisie, que d(Y n , Y ) tend vers 0 quand
n tend vers l’infini. C’est cette étape qui peut être obtenue autrement (par une
convergence de martingales par exemple).
Déroulons ces étapes pour la longueur de cheminement lce(τ n ) et sa renormalisation :
Y n :=
1
n + 1
(lce(τ n ) − E (lce(τ n ))) .
Etape 1 Cherchons une équation de récurrence vérifiée par Y n . Par le principe
« diviser pour régner » de la proposition 6.1, la longueur de cheminement externe
d’un abr vérifie l’équation en loi :
lce(τ n )
L
= lce
(1)
τ G n −1
+ lce
(2)
τ n−G n
+ n − 1,
(6.12)
où G n suit une loi uniforme sur les entiers {1, 2, . . . , n} et est indépendante des
autres variables aléatoires et où lce (1) et lce (2) sont indépendantes et de même loi que
lce. Déduisons-en maintenant l’équation en loi vérifiée par la variable renormalisée
Y n . Posons pour i = 1, 2, . . . , n,
C n (i) =
1
n + 1
n − 1 + E(lce(τ i−1 )) + E(lce(τ n−i )) − E(lce(τ n ))
.
(6.13)
Comme G n est indépendante des autres variables aléatoires, nous obtenons :
C n (G n ) =
1
n + 1
n − 1 + E
lce(τ G n −1 )
G n
+ E
lce(τ n−G n )
G n
− E(lce(τ n ))
.
Alors, en utilisant l’équation (6.12),
Y n =
1
n + 1
(lce(τ n ) − E(lce(τ n )))
L
=
1
n + 1
lce
(1)
τ G n −1
+ lce
(2)
τ n−G n
+ n − 1 − E(lce(τ n ))
.
3 L’application S est une contraction lorsqu’il existe κ ∈]0, 1[ tel que pour tous F, G ∈ M,
d(S(F ), S(G)) ≤ κ d(F, G).