20.2 Évaluation de la moyenne du cas uniforme
273
a n := E(L n (X 1 , . . . , X n )).
Le facteur t devant a n vient du fait que a n concerne [0, 1]
d et non pas [0, t]
d . Le
lemme 20.5 entraîne que a n = O(n
(d−1)/d ) et donc t → E(Z t ) est continue et
même analytique. La suite (a n ) n1 peut donc s’obtenir à partir de la donnée
de la fonction t → E(Z t ) au voisinage de t = 0. Cependant, nous allons plutôt
montrer que lim t→∞ t
−1
E(Z t ) existe, ce qui suffira.
Sous-additivité. Soit C 1 , . . . , C k d une partition (aux bords près) de [0, t]
d
en k
d cubes similaires à [0, t/k]
d . Pour tous x 1 , . . . , x n ∈ R
d , les k
d tournées
des ensembles S i = {x 1 , . . . , x n } ∩ C i peuvent être concaténées pour former
une tournée pour {x 1 , . . . , x n }∩ [0, t]
d , avec un coût supplémentaire O(k
d−1 ) :
choisir un point dans chacune des k
d tournées et les connecter avec une tournée
de coût O(k
d−1 ) grâce à la première borne du lemme 20.5 ce qui donne une
grande tournée en chapelet. Ainsi, il existe une constante c > 0 telle que pour
tout k 1 et tout t 0,
L({x 1 , . . . , x n } ∩ [0, t]
d )
k
d
i=1
L({x 1 , . . . , x n } ∩ C i ) + ctk
d−1 .
Cela donne E(Z t ) k
d
E(Z t/k ) + ctk
d−1 , d’où une première estimation :
E(Z tk )
(tk) d
E(Z t )
t d + ct
1−d .
En prenant t = 1 on obtient
0 γ := lim
k→∞
E(Z k )
k d E(Z 1 ) + c < ∞.
Par définition de γ, pour tout ε > 0 on peut choisir k 0 assez grand pour que
E(Z k0 )
k d
0
+ ck
1−d
0
γ + ε.
Comme t → E(Z t ) est continue, on peut choisir δ > 0 tel que pour tout
k 0 < t < k 0 + δ,
E(Z t )
t d + ct
1−d
γ + 2ε.
Grâce à notre première estimation, on voit que cette deuxième estimation
a lieu pour tout kk 0 < t < k(k 0 + δ). Or pour k > k 0 /δ les intervalles
I k := ]kk 0 , k(k 0 + δ)[ et I k+1 se recouvrent. On en déduit qu’elle a lieu pour
tout t k
2
0 /δ, ce qui implique en particulier
lim
t→∞
E(Z t )
t d lim
t→∞
E(Z t )
t d + 2ε = γ + 2ε.
Comme ε > 0 est arbitraire, on obtient donc