268
20 Problème du voyageur de commerce
La preuve du théorème 20.2 s’appuie sur deux lemmes.
On dit qu’une variable est concentrée lorsqu’elle reste proche de sa
moyenne avec grande probabilité. Une telle propriété peut être obtenue en
contrôlant la queue de distribution de la variable, par exemple au moyen de
moments, comme dans l’inégalité de Tchebychev basée sur la variance, et l’inégalité de Chernoff basée sur la transformée de Laplace (moments exponentiels). L’inégalité d’Azuma-Hoeffding exploite une information sur l’oscillation
de la variable (diamètre du support). On a osc(f ) 2f ∞ où
osc(f ) := sup f − inf f = diamètre(support(f )).
Lemme 20.3 (Inégalité de concentration d’Azuma-Hoeffding). Considérons
une variable aléatoire Y : (Ω, F, P) → R intégrable, alors pour tout r 0,
P(|Y − E(Y )| r) 2 exp
−
2r
2
osc(d 1 )
2 + · · · + osc(d n )
2
pour la décomposition télescopique en somme de différences de martingale
4
Y − E(Y ) =
n
𨐿
k=1
E(Y | F k ) − E(Y | F k−1 ) =
n
𨐿
k=1
d k
associée à une filtration arbitraire d’interpolation
{∅, Ω} = F 0 ⊂ F 1 ⊂ · · · ⊂ F n = F.
Démonstration. Soit U une v.a.r. telle que E(U ) = 0 et a U b. La
convexité de u → e
u donne, pour tout t 0 et tout x ∈ [a, b],
e
tx
x − a
b − a
e
tb +
b − x
b − a
e
ta .
En posant p = −a/(b − a) et f (u) = −pu + log(1 − p + pe
u ) il vient donc
E(e
tU )
b
b − a
e
ta
−
a
b − a
e
tb = e
ta
(1 − p) + pe
t(b−a)
= e
f (t(b−a)) .
À présent on a
f
(u) = −p +
pe
u
1 − p + pe u et f
(u) = p(1 − p)
e
u
(1 − p + e u ) 2
1
4
.
Comme f (0) = f
(0) = 0, on en déduit que f (u) u
2 /8 et donc
E(e
tU ) e
t 2
8 (b−a)
2 .
4. On parle parfois de martingale de Doob.