238
6 Arbres binaires de recherche
Y ∗ || 2 . En outre, pour tout x ∈]0, 1], il existe un unique entier j dans {0, . . . , n − 1}
tel que x ∈]
j
n ,
j +1
n ] de sorte que l’on peut définir V x = Y j et V ∗
x = Y ∗
j .
Soit maintenant U une variable aléatoire de loi uniforme sur ]0, 1], indépendante
de Y, Y ∗ et des Y j , Y ∗
j . Rappelons-nous que G n suit une loi uniforme sur {1, . . . , n}
de sorte qu’elle a même loi que nU . Ainsi l’équation (6.14)
Y n
L
=
G n
n + 1
Y
(1)
G n −1 +
1 −
G n
n + 1
Y
(2)
n−G n
+ C n (G n )
peut aussi s’écrire
ν n = L(Y n )
L
=
nU
n + 1
V U +
1 −
nU
n + 1
V
∗
1−U + C n (nU ).
La loi ν de Y et Y ∗ ,vérifie l’équation (6.16)
ν = L(Y )
L
= UY + (1 − U)Y
∗
+ C(U ).
Par conséquent, et comme d 2 (ν n , ν) est une borne inférieure, on a l’inégalité
d
2
2 (ν n , ν) ≤ E
nU
n + 1
V U − U Y +
1 −
nU
n + 1
V
∗
1−U − (1 − U )Y
∗ + C n (nU − C(U )
2
.
En développant ce carré, six termes apparaissent, trois carrés et trois doubles
produits. Le premier carré est
E
nU
n + 1
V U − UY
2
=
n−1
j=0
E
1 U ∈]
j
n ,
j +1
n ]
j + 1
n + 1
Y j − UY
2
=
n−1
j=0
E
1 U ∈]
j
n ,
j +1
n ]
j + 1
n + 1
(Y j − Y ) + Y
j + 1
n + 1
− U
2
.
En développant le carré, en utilisant l’indépendance entre U et les autres variables,
et grâce à l’inégalité de Cauchy-Schwarz pour E(Y (Y j − Y )) on obtient
E
nU
n + 1
V U − UY
2
≤
1
n
n−1
j=0
(j + 1) 2
(n + 1) 2 d
2
2 (ν j , ν)+
σ (Y )
n 2
n−1
j=0
j + 1
n + 1
d 2 (ν j , ν)+
Var(Y )
n 2 .
Le raisonnement est analogue pour le deuxième carré. Le troisième carré est
E (C n (nU − C(U ))
2
≤ sup
x∈]0,1[
C n (nx) − C(x)
2