20.1 Concentration pour le cas uniforme
269
Appliquée à U = d k = E(Y | F k ) − E(Y | F k−1 ) sachant F k−1 , cela donne
E(e
td k | F k−1 ) e
t 2
8 osc(d k )
2 .
Ensuite, en écrivant la somme télescopique Y −E(Y ) = d n +· · ·+d 1 on obtient
E(e
t(Y −E(Y )) ) = E(e
t(dn−1+···+d1)
E(e
tdn
| F n−1 )) · · · e
t 2
8 c ,
où c :=
n
k=1 osc(d k )
2 . À présent, pour tout t, r > 0, par l’inégalité de Markov,
P(Y − E(Y ) r) = P(e
t(Y −E(Y ))
e
tr )
e
−tr
E(e
t(Y −E(Y )) )
e
−tr+
ct 2
8 .
Ainsi, pour tout r 0,
P(Y − E(Y ) r) exp
inf
t>0
−tr +
ct
2
8
= exp
−
2r
2
c
.
En utilisant cela pour les variables Y et −Y , on obtient le résultat souhaité
pour P(|Y − E(Y )| r).
Lemme 20.4 (Lemme géométrique). Il existe une constante c d > 0 telle que
si X 1 , . . . , X k sont i.i.d. de loi uniforme sur [0, 1]
d alors pour tout x ∈ [0, 1]
d ,
g k (x) := E
min
1ik
|X i − x|
c d k
−1/d .
Démonstration. Si B(x, r) désigne la boule de centre x et de rayon r > 0 dans
R
d , le volume minimal de B(x, r) ∩ [0, 1]
d quand x parcourt [0, 1]
d est atteint
lorsque x est un coin du cube [0, 1]
d . Lorsque r 1, la valeur du minimum est
2
−d
|B(0, r)| = 2
−d
|B(0, 1)|r
d (dessin). Si 1 < r
√
d, la valeur du minimum
est difficile à calculer. Elle reste néanmoins supérieure ou égale à celle du cas
r = 1. Ainsi, pour tout 0 < r
√
d, ce volume minimal est supérieur ou égal
à 2
−d
|B(0, 1)|(r/
√
d)
d = a d r
d . Donc pour tout x ∈ [0, 1]
d et tout 0 < r
√
d,
en utilisant à la fin l’inégalité de convexité 1 − u e
−u ,
P
min
1ik
|X i − x| r
=
k
i=1
P(X i ∈ B(x, r)
c )
=
1 − |B(x, r) ∩ [0, 1]
d
|
k
1 − a d r
d
k
exp
−a d kr
d
.