270
20 Problème du voyageur de commerce
Ceci reste valable si r >
√
d car dans ce cas P(min 1ik |X i − x| r) = 0.
On a
E
min
1ik
|X i − x|
=
∞
0
P
min
1ik
|X i − x| r
dr
et
∞
0
e
−br
d dr =
Γ (1/d)
db 1/d .
Démonstration du théorème 20.2. Appliquons l’inégalité d’Azuma-Hoeffding
(lemme 20.3) à Y = L n (X 1 , . . . , X n ) et à la filtration F k = σ(X 1 , . . . , X k )
avec F 0 = {∅, Ω}. Cela ramène le problème à la majoration uniforme de
d k = E(L n (X 1 , . . . , X n ) | F k ) − E(L n (X 1 , . . . , X n ) | F k−1 ).
Si (X
1 , . . . , X
n ) est une copie indépendante de (X 1 , . . . , X n ) on remarque que
E(L n (X 1 , . . . , X k , . . . , X n ) | F k−1 ) = E(L n (X 1 , . . . , X
k , . . . , X n ) | F k )
et donc
d k := E(L n (X 1 , . . . , X k , . . . , X n ) − L n (X 1 , . . . , X
k , . . . , X n ) | F k ).
Nous allons maintenant majorer d k ∞ . Soit L la fonction qui associe à un
ensemble fini de R
d la longueur minimale de la tournée. On a, pour tout
S ⊂ R
d fini et tout x ∈ R
d ,
L(S) L(S ∪ {x}) L(S) + 2 min
y∈S
|x − y|.
En appliquant cette inégalité à S = {x 1 , . . . , x n } \ {x k } et à x = x k et x = x
k
on obtient que
|L n (x 1 , . . . , x k , . . . , x n ) − L n (x 1 , . . . , x
k , . . . , x n )|
2 min
i =k
|x
k − x i | + 2 min
i =k
|x k − x i |
2 min
i>k
|x
k − x i | + 2 min
i>k
|x k − x i |.
En posant g k (x) := E
min
1ik
|X i − x|
on obtient pour 1 k n − 1,
|d k | 2E
min
i>k
|X k − X i | + min
i>k
|X
k − X i |
F k
= 2g n−k (X k ) + 2E(g n−k (X
k )).
Le lemme géométrique 20.4 donne, pour d 2 et 1 k n − 1,
d k ∞ c d (n − k)
−1/d .
Or d n ∞ c d pour une autre constante car les X i sont bornées, d’où
n
k=1
d k
2
∞
c d log(n)
pour d = 2,
c d n
(d−2)/d
pour d > 2.