272
20 Problème du voyageur de commerce
On dispose donc d’une écriture L n (X 1 , . . . , X n ) =
n
i=1 |X i − X ji | pour des
entiers aléatoires j 1 , . . . , j n , ce qui donne
E(L n (X 1 , . . . , X n ))
n
j=1
E
min
1i =jn
|X i − X j |
nc d n
−1/d
= c d n
(d−1)/d .
Théorème 20.6 (Le bon résultat). Si μ est la loi uniforme sur [0, 1]
d alors
lim
n→∞
E(L n (X 1 , . . . , X n ))
n (d−1)/d
= γ d
où 0 < γ d < ∞ est un réel qui dépend de d.
Nous savons déjà que a n := E(L n ) ≈ n
(d−1)/d ce qui rend naturel de chercher à établir que n
d/(d−1) a n converge quand n tend vers l’infini. Ce comportement non linéaire empêche l’usage direct d’une technique de sous-additivité.
Il est cependant possible de linéariser le problème par poissonisation puis dépoissonisation. L’heuristique est la suivante : si N est une v.a.r. à valeurs entières alors E(a N ) ≈ E(N
(d−1)/d ) ≈ E(N )
(d−1)/d qui est linéaire en t lorsque
N ∼ Poi(t
d/(d−1) ). Par ailleurs si N ∼ Poi(n) alors a n ≈ E(a N ).
Démonstration. On procède par étapes.
Poissonisation. On note L(S) la longueur minimale de la tournée pour un
ensemble fini de points S = {x 1 , . . . , x n } ⊂ R
d , avec la convention L(S) = 0
si card(S) 2. Soit P un processus ponctuel de Poisson sur R
d de mesure
d’intensité Lebesgue. Soit (Z t ) t0 le processus défini par Z t = L(P ∩ [0, t]
d )
c’est-à-dire la longueur minimale de la tournée pour les atomes du processus
de Poisson P se trouvant dans le cube [0, t]
d . Pour tout n 0,
Loi(P | card(P ∩ [0, t]
d ) = n) = Unif([0, t]
d )
⊗n .
D’autre part, L(tS) = tL(S) et card(P ∩ [0, t]
d ) ∼ Poi(t
d ), ce qui donne
E(Z t ) =
∞
n=0
E(Z t | card(P ∩ [0, t]
d ) = n)P(card(P ∩ [0, t]
d ) = n)
=
∞
n=0
E(L(P ∩ [0, t]
d ) | card(P ∩ [0, t]
d )e
−t
d t
dn
n!
= e
−t
d
∞
n=0
ta n
t
dn
n!
où
20 Problème du voyageur de commerce
On dispose donc d’une écriture L n (X 1 , . . . , X n ) =
n
i=1 |X i − X ji | pour des
entiers aléatoires j 1 , . . . , j n , ce qui donne
E(L n (X 1 , . . . , X n ))
n
j=1
E
min
1i =jn
|X i − X j |
nc d n
−1/d
= c d n
(d−1)/d .
Théorème 20.6 (Le bon résultat). Si μ est la loi uniforme sur [0, 1]
d alors
lim
n→∞
E(L n (X 1 , . . . , X n ))
n (d−1)/d
= γ d
où 0 < γ d < ∞ est un réel qui dépend de d.
Nous savons déjà que a n := E(L n ) ≈ n
(d−1)/d ce qui rend naturel de chercher à établir que n
d/(d−1) a n converge quand n tend vers l’infini. Ce comportement non linéaire empêche l’usage direct d’une technique de sous-additivité.
Il est cependant possible de linéariser le problème par poissonisation puis dépoissonisation. L’heuristique est la suivante : si N est une v.a.r. à valeurs entières alors E(a N ) ≈ E(N
(d−1)/d ) ≈ E(N )
(d−1)/d qui est linéaire en t lorsque
N ∼ Poi(t
d/(d−1) ). Par ailleurs si N ∼ Poi(n) alors a n ≈ E(a N ).
Démonstration. On procède par étapes.
Poissonisation. On note L(S) la longueur minimale de la tournée pour un
ensemble fini de points S = {x 1 , . . . , x n } ⊂ R
d , avec la convention L(S) = 0
si card(S) 2. Soit P un processus ponctuel de Poisson sur R
d de mesure
d’intensité Lebesgue. Soit (Z t ) t0 le processus défini par Z t = L(P ∩ [0, t]
d )
c’est-à-dire la longueur minimale de la tournée pour les atomes du processus
de Poisson P se trouvant dans le cube [0, t]
d . Pour tout n 0,
Loi(P | card(P ∩ [0, t]
d ) = n) = Unif([0, t]
d )
⊗n .
D’autre part, L(tS) = tL(S) et card(P ∩ [0, t]
d ) ∼ Poi(t
d ), ce qui donne
E(Z t ) =
∞
n=0
E(Z t | card(P ∩ [0, t]
d ) = n)P(card(P ∩ [0, t]
d ) = n)
=
∞
n=0
E(L(P ∩ [0, t]
d ) | card(P ∩ [0, t]
d )e
−t
d t
dn
n!
= e
−t
d
∞
n=0
ta n
t
dn
n!
où