20.1 Concentration pour le cas uniforme
267
Fig. 20.2. Tracé d’une approximation de n → n
−1/2 E(Ln) dans le cas uniforme,
avec une méthode de Monte-Carlo et l’algorithme du recuit simulé (chapitre 5).
20.1 Concentration pour le cas uniforme
Théorème 20.2 (Concentration autour de la moyenne). Si μ est la loi uniforme sur le cube [0, 1]
d alors pour tout n 1 et tout réel t 0 on a
P(|L n − E(L n )| t) 2 exp
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
−
ct
2
log(n)
si d = 2,
−
ct
2
n (d−2)/d si d > 2,
où c > 0 est une constante qui ne dépend que de la dimension d. Ainsi,
P
L n
n (d−1)/d − E
L n
n (d−1)/d
t
2 exp
⎧
⎪ ⎨
⎪ ⎩
−
cnt
2
log(n)
si d = 2,
−cnt
2
si d > 2.