236
6 Arbres binaires de recherche
où X (1) et X (2) sont indépendantes et de même loi F et où U est de loi uniforme sur
[0, 1], indépendante de X (1) et X (2) .
Etape 3 Appelons M l’ensemble des mesures de probabilités sur R ayant un second
moment. Pour F, G ∈ M, posons 4
d 2 (F, G) =
inf
X de loi F, Y de loi G
{ − Y 2 }
où
− Y 2 =
E
| X − Y | 2
est la norme L 2 . Alors (voir par exemple Dudley [71]), d 2 est une distance, appelée
parfois distance de Wasserstein, qui rend l’espace (M, d 2 ) métrique et complet.
Cette distance s’exprime aussi sous forme intégrale, en montrant (cf. Major [177,
Th. 8.1]) que la borne inférieure ci-dessus est atteinte pour une variable aléatoire
X = F −1 (U ) et pour une variable aléatoire Y = G −1 (U ) où U est la même variable
aléatoire de loi uniforme sur [0, 1], de sorte que l’on a
d 2 (F, G) = =F
−1 (U ) − G
−1 (U ) 2
=
1
0
| F
−1 (u) − G
−1 (u) |
2 du
1/2
.
Dans la suite, nous allons utiliser le fait que la convergence pour la distance d 2 est
équivalente à la convergence en loi et la convergence des moments d’ordre 2. Elle
est donc plus forte que la convergence en loi.
Plaçons-nous dans l’espace M 0 des mesures de probabilités de moyenne nulle
et admettant un second moment. Comme Y n est de moyenne nulle, Y n ∈ M 0 . Le
lemme suivant assure que la transformation S de l’étape 2 est une contraction.
Lemme 6.15 (Lemme de contraction) La transformation
F −→ S(F ) = L(U X
(1)
+ (1 − U)X
(2)
+ C(U )),
où X (1) et X (2) sont indépendantes et de même loi F , U est de loi uniforme sur
[0, 1], indépendante de X (1) et X (2) et C(x) = 1 + 2(x log x + (1 − x) log(1 − x)),
est une contraction de (M 0 , d 2 ) dans (M 0 , d 2 ).
Preuve Rappelons que par définition, d 2 est une borne inférieure. Donc, pour X (1)
et X (2) indépendantes de loi F , Y (1) et Y (2) indépendantes de loi G et indépendantes
de X (1) et X (2) , nous obtenons, en utilisant en outre le fait que toutes ces variables
4 L’indice 2 de d 2 n’est pas strictement utile, il est présent pour se rappeler que l’on travaille dans
L 2 .
6 Arbres binaires de recherche
où X (1) et X (2) sont indépendantes et de même loi F et où U est de loi uniforme sur
[0, 1], indépendante de X (1) et X (2) .
Etape 3 Appelons M l’ensemble des mesures de probabilités sur R ayant un second
moment. Pour F, G ∈ M, posons 4
d 2 (F, G) =
inf
X de loi F, Y de loi G
{ − Y 2 }
où
− Y 2 =
E
| X − Y | 2
est la norme L 2 . Alors (voir par exemple Dudley [71]), d 2 est une distance, appelée
parfois distance de Wasserstein, qui rend l’espace (M, d 2 ) métrique et complet.
Cette distance s’exprime aussi sous forme intégrale, en montrant (cf. Major [177,
Th. 8.1]) que la borne inférieure ci-dessus est atteinte pour une variable aléatoire
X = F −1 (U ) et pour une variable aléatoire Y = G −1 (U ) où U est la même variable
aléatoire de loi uniforme sur [0, 1], de sorte que l’on a
d 2 (F, G) = =F
−1 (U ) − G
−1 (U ) 2
=
1
0
| F
−1 (u) − G
−1 (u) |
2 du
1/2
.
Dans la suite, nous allons utiliser le fait que la convergence pour la distance d 2 est
équivalente à la convergence en loi et la convergence des moments d’ordre 2. Elle
est donc plus forte que la convergence en loi.
Plaçons-nous dans l’espace M 0 des mesures de probabilités de moyenne nulle
et admettant un second moment. Comme Y n est de moyenne nulle, Y n ∈ M 0 . Le
lemme suivant assure que la transformation S de l’étape 2 est une contraction.
Lemme 6.15 (Lemme de contraction) La transformation
F −→ S(F ) = L(U X
(1)
+ (1 − U)X
(2)
+ C(U )),
où X (1) et X (2) sont indépendantes et de même loi F , U est de loi uniforme sur
[0, 1], indépendante de X (1) et X (2) et C(x) = 1 + 2(x log x + (1 − x) log(1 − x)),
est une contraction de (M 0 , d 2 ) dans (M 0 , d 2 ).
Preuve Rappelons que par définition, d 2 est une borne inférieure. Donc, pour X (1)
et X (2) indépendantes de loi F , Y (1) et Y (2) indépendantes de loi G et indépendantes
de X (1) et X (2) , nous obtenons, en utilisant en outre le fait que toutes ces variables
4 L’indice 2 de d 2 n’est pas strictement utile, il est présent pour se rappeler que l’on travaille dans
L 2 .