274
20 Problème du voyageur de commerce
lim
t→∞
E(Z t )
t d = γ.
Ainsi, le développement en série de E(Z t ) donne, après le changement de
variable u = t
d ,
∞
k=0
e
−u a k
u
k
k!
∼
n→∞
γu
(d−1)/d .
Dépoissonisation. On commence par montrer que n → a n est assez régulière. Comme il est possible de concaténer un circuit pour X 1 , . . . , X m et
un circuit pour X m+1 , . . . , X m+n avec un coût inférieur à 2
√
d (diamètre du
cube) on en déduit que
a n+m a n + a m + 2
√
d
ce qui donne 0 a n − a k a n−k + 2
√
d pour tout 0 k n. Or le lemme
20.5 donne a n = O(n
(d−1)/d ) et on en déduit
|a n − a k | |a n−k + 2
√
d| c|n − k|
(d−1)/d .
Si N est une v.a.r. de Poisson de moyenne n alors
E(a N ) =
∞
k=0
a k e
−n n
k
k!
et donc
|a n − E(a N )|
∞
k=0
|a n − a k |e
−n n
k
k!
c
∞
k=0
|n − k|
(d−1)/d e
−n n
k
k!
= cE(|N − E(N )|
(d−1)/d )
cE(|N − E(N )|
2 )
(d−1)/(2d)
= cVar(N )
(d−1)/(2d)
= O(n
(d−1)/(2d) ) = o(n
(d−1)/d ).
Or le résultat de la poissonisation avec t = n donne
E(a N ) =
∞
𵫾
k=0
a k e
−n n
k
k!
∼
n→∞
γn
(d−1)/d
et donc
lim
n→∞
E(L n (X 1 , . . . , X n ))
n (d−1)/d
= lim
n→∞
a n
n (d−1)/d = γ.
Le fait que γ > 0 découle de la borne inférieure du lemme 20.5.