20.2 Évaluation de la moyenne du cas uniforme
271
20.2 Évaluation de la moyenne du cas uniforme
Lemme 20.5 (Un bon début). Si μ ∼ Unif([0, 1]
d ) alors pour tout n 1,
L n (X 1 , . . . , X n ) ∞ c d n
(d−1)/d
et
c
−
d n
(d−1)/d
E(L n (X 1 , . . . , X n )) c
+
d n
(d−1)/d
où 0 < c
−
d c
+
d < ∞ sont des constantes qui ne dépendent que de d.
Démonstration. Le cube [0, 1]
d est l’union de (1/ε)
d petits cubes isométriques
à [0, ε]
d . Avec ε = n
−1/d on obtient que [0, 1]
d peut être recouvert par O(n)
petits cubes de diamètre O(n
−1/d ). Par le principe des tiroirs
5 , pour tous
x 1 , . . . , x n ∈ [0, 1]
d on a, pour une constante c d qui peut dépendre de d,
min
1i =jn
|x i − x j | c d n
−1/d .
Par conséquent, si n est le maximum sur x 1 , . . . , x n de la longueur de tournée
minimale pour x 1 , . . . , x n , alors
n n−1 + 2c d n
−1/d
qui donne, pour une nouvelle constante c d qui peut dépendre de d,
L n (X 1 , . . . , X n ) ∞ c d n
−1/d+1 = c d n
(d−1)/d .
Par ailleurs, la preuve du lemme 20.4 indique que |B(x, r)∩[0, 1]
d
| est maximal
quand x est au centre du cube, d’où, pour tout x ∈ [0, 1]
d et tout 0 < r 1/2,
P
min
1in−1
|X i − x| r
(1 − ω d r
d )
n−1
avec ω d := |B(0, 1)|. En utilisant l’inégalité élémentaire (1 − u)
α
1 − αu
valable dès que 0 u 1/α, on en déduit que
E
min
1in−1
|X i − x|
1/2
0
(1 − ω d r
d )
n−1 dr c d n
−1/d .
Ainsi,
min
1jn
E
min
1i =jn
|X i − X j |
= min
1jn
E
E
min
1i =jn
|X i − X j | | X j
c d n
−1/d
où c d est une constante qui dépend de la dimension d. Or le circuit optimal
à travers X 1 , . . . , X n possède n arêtes et passe par chacun des n sommets.
5. Pigeonhole principle en anglais : si on dispose n objets dans m boîtes avec
n > m alors au moins l’une des boîtes contient deux objets ou plus.