Master 2 Probabilités + M2A Algorithmes et Apprentissage

Sorbonne Université

Inégalités de concentration

Références :
Boucheron, Lugosi, Massart, Concentration inequalities [3].
Devroye, Györfi, Lugosi, A probabilistic theory of pattern recognition [7].
Dubhashi, Panconesi, Concentration of measure for the analysis of randomised algorithms [8].
Ledoux, The concentration of measure phenomenon [15].
Tropp, An introduction to matrix concentration inequalities [24].
Vershynin, High-dimensional probability [25].

Anna Ben-Hamou
[email protected]
 Table des matières

CHAPITRE 1. Variance, entropie, influences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. L’inégalité d’Efron–Stein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Inégalité de Sobolev logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Influences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4. Phénomènes de transition de phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

CHAPITRE 2. Méthode de Cramér-Chernoff et inégalités classiques . . . . . . . . . . . . . . . 14

1. Méthode de Cramér-Chernoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2. Variables sous-gaussiennes, sous-Poisson, sous-gamma . . . . . . . . . . . . . . . . . . . . . 15
3. Sommes de variables indépendantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1. Inégalité d’Hoeffding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Inégalité de Bennett . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3. Inégalité de Bernstein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

CHAPITRE 3. L’approche par martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1. L’inégalité d’Azuma-Hoeffding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2. L’inégalité des différences bornées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3. L’inégalité de Grable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4. L’inégalité de Freedman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

CHAPITRE 4. La méthode entropique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1. Entropie de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.1. Un peu de théorie de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2. Entropie relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.3. Entropie conditionnelle et chain rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4. Inégalité de Han . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2. Sous-additivité de l’entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3. Lien avec la transformée de Laplace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4. Inégalité de Mc Diarmid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5. Une inégalité de Sobolev logarithmique modifiée . . . . . . . . . . . . . . . . . . . . . . . . . 36
6. Une autre inégalité de Mc Diarmid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7. Concentration des fonctions auto-bornées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

CHAPITRE 5. La méthode de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

1. Le lemme de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2. L’inégalité de transport conditionnelle de Marton . . . . . . . . . . . . . . . . . . . . . . . . 44
3. L’inégalité de distance convexe de Talagrand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

CHAPITRE 6. Classification et théorie de Vapnik-Chervonenkis . . . . . . . . . . . . . . . . . 49

1
 1. Un problème d’apprentissage statistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2. Inégalités de Vapnik–Chervonenkis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3. Chaı̂nage et inégalité de Dudley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

CHAPITRE 7. Concentration de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

1. Une inégalité de Bernstein pour les sommes de matrices . . . . . . . . . . . . . . . . . . . . 60
2. Application : connexité du graphe d’Erdös-Renyi . . . . . . . . . . . . . . . . . . . . . . . . . 61

CHAPITRE 8. Concentration sans indépendance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

1. Concentration pour les chaı̂nes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2. Concentration avec dépendance négative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.1. Association négative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.2. Propriété de recouvrement stochastique . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3. Paires échangeables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Application : poids d’une permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Magnétisation dans le modèle de Curie–Weiss . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2
 Chapitre 1

Variance, entropie, influences

Soient X1 , . . . , Xn des variables aléatoires indépendantes définies sur un espace mesurable

(Ω, F, P), à valeurs dans un espace mesurable X , et soit Z = f (X1 , . . . , Xn ) avec f : X n → R
une fonction mesurable. Si l’on s’intéresse à la façon dont Z se concentre autour de son espérance
EZ, une première quantité que l’on peut étudier est la variance. Si la fonction f correspond à
une somme, alors le problème est simplement celui des variances individuelles des variables :
n
X
Var(Z) = Var(Xi ) .
i=1

Mais que peut-on dire de la variance d’une fonction éventuellement bien plus complexe que la
somme ? Notons que l’on peut toujours décomposer Z − EZ comme une somme d’incréments
de martingale pour la filtration de Doob et utiliser l’orthogonalité de ces incréments. Plus
précisément, notons Ei = E[· X1 , . . . , Xi ] et E0 = E. Alors
n
X
Z − EZ = Ei Z − Ei−1 Z ,
i=1

et
n
X X
E (Ei Z − Ei−1 Z)2 + 2
 
Var(Z) = E [(Ej Z − Ej−1 Z)(Ei Z − Ei−1 Z)] .
i=1 i<j

En remarquant que pour j > i, Ei [Ej Z − Ej−1 Z] = 0, on voit que les covariances sont nulles et
l’on obtient
Xn
E (Ei Z − Ei−1 Z)2 .
 
Var(Z) =
i=1
Jusqu’ici, on n’a pas utilisé l’hypothèse d’indépendance sur les X1 , . . . , Xn . Celle-ci intervient
maintenant pour pouvoir écrire
Ei−1 Z = Ei E(i) Z ,
où E(i) = E[· X (i) ] avec X (i) = (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ). C’est l’observation-clé dans la
preuve du résultat principal de ce chapitre, l’inégalité d’Efron–Stein.

1. L’inégalité d’Efron–Stein
Proposition 1.1 (Inégalité d’Efron–Stein). Soient X1 , . . . , Xn des variables indépendantes à
valeurs dans un espace mesurable X , et soit Z = f (X1 , . . . , Xn ) une fonction mesurable. Alors
Xn  2 
(i)
Var(Z) ≤ E Z −E Z .
i=1
3
Preuve de la Proposition 1.1. Par le théorème de Fubini, si Pi est la loi de Xi , on a
Z 
(i)
E i E Z = Ei f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn )dPi (xi )
X
Z
= f (X1 , . . . , Xi−1 , xi , xi+1 , . . . , xn )dPi (xi ) . . . dPn (xn )
X n−i+1
= Ei−1 Z .

Ainsi, en utilisant l’inégalité de Jensen conditionnellement à X1 , . . . , Xi ,

 2 h i
(Ei Z − Ei−1 Z)2 = Ei [Z − E(i) Z] ≤ Ei (Z − E(i) Z)2 ,

et
n
X n
X h h ii Xn  2 
2 (i) 2 (i)
 
Var(Z) = E (Ei Z − Ei−1 Z) ≤ E Ei (Z − E Z) = E Z −E Z .
i=1 i=1 i=1


h
i
(i) Z 2 de l’inégalité d’Efron–Stein peut se
Pn
Remarque 1.1. La borne v = i=1 E Z − E
ré-écrire de plusieurs façons. Rappelons que si X est une variable aléatoire réelle et Y une copie
indépendante de X, on peut écrire Var(X) = 12 E[(X − Y )2 ]. Si Xi0 est une copie indépendante
de Xi , alors, conditionnellement à X (i) , la variable

Zi0 = f (X1 , . . . , Xi−1 , Xi0 , Xi+1 , . . . , Xn )

est une copie indépendante de Z, et l’on a

 2  1
(i) (i) (i)
= E(i) (Z − Zi0 )2 = E(i) (Z − Zi0 )2+ .
   
Var (Z) = E Z −E Z
2
Ainsi
n n
1X   X 
E (Z − Zi0 )2 = E (Z − Zi0 )2+ .

v=
2
i=1 i=1

De plus, en utilisant que pour toute variable aléatoire réelle X, Var(X) = inf a∈R E[(X − a)2 ],
on a
Var(i) (Z) = inf E(i) (Z − Zi )2 ,
 
Zi

où l’infimum est pris sur les fonctions mesurables de X (i) de carré intégrable. Ainsi
Xn  
(i) 2
 
v= E inf E (Z − Zi ) .
Zi
i=1

Exemple 1.2 (Bins and balls). Soit X1 , . . . , Xn des variables i.i.d. à valeurs dans N∗ , de
loi (pj )j≥1 . Pour r ≥ 1, on note Kn,r le nombre d’entiers représentés exactement r fois dans
l’échantillon (X1 , . . . , Xn ), soit

1{Pni=1 1X =j =r} .
X
Kn,r =
i
j≥1

4
 P
On définit aussi K̄n,r = s≥r Kn,s le nombre d’entiers représentés au moins r fois, et Kn = K̄n,1
le nombre d’entiers distincts présents dans l’échantillon. On a
X n
EKn,r = pr (1 − pj )n − r ,
r j
j≥1
et X
EKn = (1 − (1 − pj )n ) .
j≥1
(i)
Que peut-on dire de la variance de ces variables ? Soit Kn le nombre de symboles distincts dans
l’échantillon lorsque l’on omet la iième variable. Alors
(
Kn − 1 si Xi n’est présent qu’une seule fois,
Kn(i) =
Kn sinon.
Ainsi l’inégalité d’Efron–Stein donne
Var(Kn ) ≤ EKn,1 .
De façon plus générale, on a
Var(K̄n,r ) ≤ rEKn,r .
De plus, Var(Kn,r ) ≤ rEKn,r + (r + 1)EKn,r+1 .

Définition 1.1 (Fonction à différences bornées). On dit que f : X n → R est à différences

bornées s’il existe des constantes c1 , . . . , cn ≥ 0 telles que pour tout i ∈ J1, nK, on a
sup f (x1 , . . . , xn ) − f (x1 , . . . , xi−1 , x0i , xi+1 , . . . , xn ) ≤ ci .
x1 ,...,xn ∈X
x0i ∈X

L’inégalité d’Efron–Stein donne la borne suivante sur la variance des fonctions à différences
bornées.

Proposition 1.2 (Variance des fonctions à différences bornées). Si f : X n → R est à

différences bornées avec constantes c1 , . . . , cn ≥ 0 et si Z = f (X1 , . . . , Xn ) avec X1 , . . . , Xn
indépendantes, alors
n
1X 2
Var(Z) ≤ ci .
4
i=1

Preuve de la Proposition 1.2. On définit

1 −
Zi + Zi+ ,


Zi =
2
avec
Zi− = inf f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn ) et Zi+ = sup f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn ) .
xi ∈X xi ∈X

Alors |Z − Zi | correspond à la distance entre Z et le milieu de l’intervalle [Zi− , Zi+ ]. Comme cette
intervalle est de longueur inférieure à ci par hypothèse, on a |Z − Zi | ≤ ci /2. Ainsi, par l’inégalité
d’Efron–Stein, on a
n n
X
2
 1X
c2i .

Var(Z) ≤ E (Z − Zi ) ≤
4
i=1 i=1

5
 Dans le reste de ce chapitre, on s’intéresse au cas (simple mais déjà très riche) où X = {0, 1}
et où X = (X1 , . . . , Xn ) ∼ B(p)⊗n avec B(p) = pδ1 + (1 − p)δ0 (notons que quand p = 1/2, la loi
de X est uniforme sur {0, 1}n ). Dans ce cas, l’inégalité d’Efron–Stein correspond exactement à
une inégalité de Poincaré. L’énergie d’une fonction f : {0, 1}n → R est définie par
n  2 
1X
E(f ) = E f (X) − f (X ei ) ,
2
i=1

où X
ei = (X1 , . . . , Xi−1 , Xi0 , Xi+1 , . . . , Xn )
est le vecteur obtenu en rejouant la iième coordonnée
de X indépendamment des autres. L’inégalité d’Efron–Stein donne
(1.1) Var(f ) ≤ E(f )
Pn
avec égalité pour f (x) = i=1 xi . On dit que la mesure produit B(p)⊗n vérifie une inégalité de
Poincaré, avec constante de Poincaré égale à 1, i.e.
Var(f )
sup = 1.
f :{0,1}n →R E(f )
f non-constante

Nous allons voir que l’on peut aussi montrer que

!
Var(f )
(1.2) Var(f ) log Pn 2
≤ c(p)E(f ) ,
j=1 (E|∆j |)

où ∆j = Ej f − Ej−1 f , et où c(p) est une constante qui ne dépend que de p. Dès que
n
X n
X
2
E [|Ej f − Ej−1 f |]2 ,
 
Var(f ) = E (Ej f − Ej−1 f ) 
j=1 j=1

l’inégalité (1.2) constitue une significative amélioration par rapport à (1.1). Avant d’établir (1.2),
montrons que la mesure B(p)⊗n vérifie aussi une inégalité de Sobolev logarithmique.

2. Inégalité de Sobolev logarithmique

Soit µ une mesure de probabilité sur {0, 1}n . L’entropie sous µ d’une fonction positive
g : {0, 1}n → R+ est définie comme
Entµ (g) = Eµ [g log g] − Eµ [g] log Eµ [g] ,
avec la convention 0. log 0 = 0. Si (X1 , . . . , Xn ) ∼ µ et Z = g(X1 , . . . , Xn ) on écrira indifféremment
Ent(Z) ou Entµ g. On a
Entµ (g) = sup Eµ [g log h] ,
h:{0,1}n →R+ ,
Supp(g)⊂Supp(h)
Eµ h=1

où Supp(g) = {x ∈ {0, 1}n , g(x) > 0}. En effet, d’une part il y a égalité pour h = Egµ g . D’autre
part, pour toute fonction h : {0, 1}n → R+ avec Supp(g) ⊂ Supp(h) et Eµ h = 1, on a
h gi hg gi
Eµ [g log g] − Eµ [g log h] = Eµ g log = Eν log ,
h h h
où ν est la loi de probabilité sur {0, 1}n donnée par ν(x) = h(x)µ(x). Par l’inégalité de Jensen,
on a hg gi hgi hgi
Eν log ≥ Eν log Eν = Eµ [g] log Eµ [g] ,
h h h h
6
soit Entµ (g) ≥ Eµ [g log h]. Cette caractérisation variationnelle de l’entropie (que nous retrouve-
rons en plus grande généralité au Chapitre 4) a de nombreuses implications, la plus importante
d’entre elles étant probablement la sous-additivité de l’entropie.

Proposition 1.3 (Sous-additivité de l’entropie). Soit X = (X1 , . . . , Xn ) ∼ B(p)⊗n et Z =

g(X) pour g : {0, 1}n → R∗+ une fonction positive. Alors
" n #
X
(i)
Ent(Z) ≤ E Ent (Z) ,
i=1
(i)
où Ent (Z) = E(i) [Z log Z] − E(i) [Z] log E(i) [Z] avec E(i) = E[· X (i) ].

Preuve de la Proposition 1.3. On rappelle la notation Ei = E[· X1 , . . . , Xi ] avec E0 = E, et le

fait que Ei−1 Z = E(i) Ei Z par indépendance des Xi . On peut alors écrire
Xn n
X  
Z (log Z − log EZ) = Z (log Ei Z − log Ei−1 Z) = Z log Ei Z − log E(i) Ei Z .
i=1 i=1

En appliquant l’inégalité Entµ g ≥ Eµ [g log h − log Eµ h] avec µ la loi de X sachant X (i) et

h(X) = Ei g(X), on obtient
h  i
E(i) Z log Ei Z − log E(i) Ei Z ≤ Ent(i) (Z) ,
et en prenant l’espérance dans la somme, on obtient bien
" n # " n #
X X
Ent(Z) = E E(i) [Z (log Ei Z − log Ei−1 Z)] ≤ E Ent(i) (Z) .
i=1 i=1


Proposition 1.4 (Inégalité de Sobolev logarithmique sur le cube). Soit µ = B(p)⊗n . Pour
toute fonction f : {0, 1}n → R,
Entµ (f 2 ) ≤ c(p)E(f ) ,
avec 
2 1
si p = 2 ,
c(p) =  
1
 1−2p log 1−p
p sinon.
On dit que la mesure B(p)⊗n vérifie une inégalité de Sobolev logarithmique avec constante c(p).

Preuve de la Proposition 1.4. Soit X ∼ B(p)⊗n . Par sous-additivité de l’entropie, on a

n h

X
i
Ent f (X)2 ≤ E Ent(i) f (X)2 .
i=1
Il suffit donc de montrer que
 2 
(i) 2 (i) (i)


Ent f (X) ≤ c(p)p(1 − p)E f (X) − f (X̄ ) .

Pour toute réalisation de X (i) , la fonction f (X) ne peut prendre que deux valeurs selon que
Xi = 1 ou Xi = 0. En notant a et b ces deux valeurs possibles, il s’agit de montrer
pa2 log(a2 ) + (1 − p)b2 log(b2 ) − pa2 + (1 − p)b2 log pa2 + (1 − p)b2 ≤ c(p)p(1 − p)(a − b)2 .

7
On laisse en exercice la démonstration de cette inégalité. 
Montrons maintenant comment l’inégalité de Sobolev logarithmique peut être utilisée pour
montrer l’inégalité 1.2.

Proposition 1.5. Sous la loi µ = B(p)⊗n , pour toute fonction f : {0, 1}n → R,
!
Var(f )
Var(f ) log Pn 2
≤ c(p)E(f ) ,
j=1 (E|∆j |)

où ∆j = Ej f − Ej−1 f , et où c(p) est la constante de Sobolev logarithmique de la Proposition 1.4.

Preuve de la Proposition 1.5. Remarquons d’abord que

n
X
E(f ) = E(∆j ) .
j=1

En effet, pour X ∼ B(p)⊗n et X

ei = (X1 , . . . , Xi−1 , X 0 , Xi+1 , . . . , Xn ), on a
i

n
X X n
n X  2 
2 E(∆j ) = E ∆j (X) − ∆j (Xi )
e
j=1 j=1 i=1
Xn   2   2 
= E Ej f (X) − Ej f (Xi )
e − E Ej−1 f (X) − Ej−1 f (Xi )
e
i,j=1
X n   2   2 
= E En f (X) − En f (X
ei ) −E E0 f (X) − E0 f (X
ei )
i=1
n
X  2 
= E f (X) − f (Xi )
e
i=1
= 2E(f ) ,

où pour la première égalité on a utilisé

h  i  2 
E Ej f (X) − Ej f (Xi ) Ej−1 f (X) − Ej−1 f (Xi ) = E Ej−1 f (X) − Ej−1 f (Xi )
e e e .

En appliquant la Proposition 1.4, on a

n n
X 1 X
Ent ∆2j .


E(f ) = E(∆j ) ≥
c(p)
j=1 j=1

E[g ] 2
Pour toute fonction positive g, on a Ent(g 2 ) ≥ E[g 2 ] log (E[g]) 2 . En effet, en utilisant que pour

tout x > 0, log(x) ≤ x − 1, on a

Eg 2
    2 
2 2 Eg
E g log ≤E g −1 = 0,
gEg gEg
8
ce qui équivaut à l’inégalité voulue. Ainsi
n
1 X E[∆2j ]
E(f ) ≥ E[∆2j ] log
c(p) E[|∆j |]2
j=1
n
Var(f ) X E[∆2j ] E[|∆j |]2
=− log
c(p)
j=1
Var(f ) E[∆2j ]
Pn 2
!
Var(f ) j=1 E[|∆j |]
≥− log ,
c(p) Var(f )
où l’on a utilisé l’inégalité de Jensen et le fait que Var(f ) = nj=1 E[∆2j ].
P


3. Influences
Nous allons voir les conséquences surprenantes de la Proposition 1.5 quant à l’influence
des fonctions booléennes. Soit f : {0, 1}n → {0, 1} une fonction booléenne et notons A = {x ∈
{0, 1}n , f (x) = 1}. Pour X ∼ B(p)⊗n , l’influence de i sur f est définie comme
 
Ii (f ) = P f (X) 6= f (X̄ (i) ) ,
soit la probabilité qu’un flip de la coordonnée implique un changement de la valeur de f . Quand
f (X) 6= f (X̄ (i) ), on dit que i est un pivot pour X. L’influence totale est définie comme la somme
des influences individuelles :
n
X
I(f ) = Ii (f ) .
i=1

Exemple 1.3 (Fonction parité). Pour f la fonction qui vaut 1 si le nombre de coordonnées
égales à 1 est impair, 0 sinon, appelée fonction parité, on a toujours f (X) 6= f (X̄ (i) ). Ainsi
Ii (f ) = 1 et I(f ) = n. Clairement, c’est la plus grande influence possible.

Exemple 1.4 (Fonction majorité). Pour f (x) = 1P xi >n/2 la fonction majorité, la coordonnée
= n−1 . Ainsi, pour p = 12 , par la formule de Stirling,
P  
i est pivot uniquement quand j6=i xj2
     r
1 n−1 2
Ii (f ) = P Bin n − 1, = ∼ ,
2 2 πn
q
2n
et I(f ) ∼ π .

Exemple 1.5 (Fonction dictature). Pour f (x) = x1 la fonction dictature qui ne retient que la
valeur de la première coordonnée, l’influence de toutes les coordonnées est nulle, sauf celle de la
première qui vaut 1. Ainsi I(f ) = I1 (f ) = 1.

Peut-on obtenir des bornes générales pour l’influence d’une fonction f ? Par l’inégalité
d’Efron–Stein,
Xn
Var(f ) = P(A)(1 − P(A)) ≤ p(1 − p) Ii (f ) = p(1 − p)I(f ) .
i=1
En particulier, si P(A) = p, l’influence doit être au moins égale à 1, et cette borne inférieure est
atteinte par la fonction dictature. Pour cette fonction, il n’y a qu’une seule coordonnée qui a une
influence non-nulle. Plus généralement, si seulement k coordonnées ont une influence non-nulle
9
sur f (pour k fixé ne dépendant pas de n, on dit que f est un junta), alors clairement I(f ) ≤ k.
Une question que l’on peut se poser est la suivante : si f est symétrique au sens où toutes
les coordonnées ont la même influence sur f , I1 (f ) = · · · = In (f ) = I(f )
n , jusqu’à quel point
l’influence totale peut-elle être petite ? Un résultat fondamental de Kahn et al. [13] implique que
l’influence d’une fonction symétrique est au moins égale à Var(f ) log n, ce qui contraste fortement
avec le cas de la fonction dictature ou plus généralement des juntas qui ont une influence bornée.

Proposition 1.6 (Kahn et al. [13]). Soit f : {0, 1}n → {0, 1} une fonction booléenne. Alors,
sous la loi µ = B(p)⊗n ,
Var(f ) log n
max Ii (f ) ≥ ,
1≤i≤n n
En particulier, si f est symétrique, alors I(f ) ≥ Var(f ) log n.

Preuve de la Proposition 1.6. On a

h i
E|∆j | = E Ei f (X) − Ei E(i) f (X)
h i
≤ E f (X) − E(i) f (X)
= 2p(1 − p)Ii (f ) .
Ainsi, la Proposition 1.5 implique que
!
Var(f )
Var(f ) log ≤ c(p)p(1 − p)I(f ) ,
4p (1 − p)2 nj=1 Ij (f )2
2
P

soit
n  
X
2 Var(f ) c(p)p(1 − p)I(f )
Ij (f ) ≥ 2 exp − ,
4p (1 − p)2 Var(f )
j=1

α Var(f ) log(Var(f ) log2 n)

On distingue deux cas. Soit I(f ) ≥ c(p)p(1−p) log n, pour α = 1 − log n , auquel cas
n
X I(f )2 α2 Var(f )2 log2 n
Ij (f )2 ≥ ≥ · ,
n c(p)2 p2 (1 − p)2 n
j=1

et
α Var(f ) log n
max Ii (f ) ≥ · ·
1≤i≤n c(p)p(1 − p) n
α Var(f )
Soit I(f ) ≤ c(p)p(1−p) log n, auquel cas
n
X Var(f ) −α 1 Var(f )2 log2 n
Ij (f )2 ≥ · n = · ,
4p2 (1 − p)2 4p2 (1 − p)2 n
j=1

et
1 Var(f ) log n
max Ii (f ) ≥ · ·
1≤i≤n 2p(1 − p) n
Dans les deux cas, en utilisant que α ≥ 12 , que c(p)p(1 − p) ≤ 12 , et que p(1 − p) ≤ 14 , on obtient
Var(f ) log n
max Ii (f ) ≥ ·
1≤i≤n n


10
 4. Phénomènes de transition de phase
Soit f : {0, 1}n → {0, 1} une fonction booléenne monotone, au sens où elle est croissante en
chacune de ses coordonnées (par exemple la fonction majorité et la fonction dictature sont toutes
les deux monotones). Pour A = {x ∈ {0, 1}n , f (x) = 1}, on s’intéresse à la fonction
X
p 7→ µp (A) = P(X ∈ A) = pkxk (1 − p)n−kxk ,
x∈A
Pn
où kxk = i=1 xi et X ∼ µp = B(p)⊗n (on rend maintenant la dépendance en p explicite). La
monotonicité de f implique que µ0 (A) = 0, µ1 (A) = 1, et p 7→ µp (A) est une fonction strictement
croissante et différentiable. Le message principal de cette section est que si la fonction f ne
dépend pas trop de chaque coordonnée individuellement, alors on observe une transition abrupte
de 0 à 1. Plus précisément, si l’on note pε la valeur de p pour laquelle µp (A) = ε, alors la différence
p1−ε − pε est très petite.

Exemple 1.6 (Fonction dictature). Soit f (x) = x1 la fonction dictature. Dans ce cas, on a
µp (A) = p. La fonction p 7→ µp (A) croit linéairement de 0 à 1, il n’y a pas de transition abrupte.

Exemple 1.7 (Fonction majorité). Soit f (x) = 1P xi >n/2 la fonction majorité. On a p1/2 = 1/2,
et, pour p < 1/2, par l’inégalité de Hoeffding,
n
!
X n
µp (A) = Pp Xi >
2
i=1
n   !
X 1
= Pp Xi − np > −p n
2
i=1
(  2 )
1
≤ exp −2 −p n .
2
q q
Ainsi µp (A) ≤ ε dès que p ≤ 21 − log(1/ε)
2n . De même, µ p (A) ≥ 1 − ε dès que p ≥ 1
2 + log(1/ε)
2n .
q
Ainsi, la valeur de µp (A) saute de ε à 1 − ε dans un intervalle de longueur 2 log(1/ε)
n , il y a une
1
transition abrupte autour de p = 2 .

Ce phénomène de transition de phase s’étend à une large classe de fonctions monotones,

grosso modo celles qui dépendent un peu mais pas trop de chaque variable individuellement. Le
Lemme de Russo ci-dessous relie la dérivée de la fonction p 7→ µp (A) à l’influence de f .

Lemme 1.7 (Lemme de Russo). Soit f : {0, 1}n → {0, 1} une fonction booléenne monotone
et A = {x ∈ {0, 1}n , f (x) = 1}. Alors pour tout p ∈]0, 1[,
dµp (A)
= Ip (f ) .
dp
Preuve du Lemme 1.7. Soit µp = B(p)⊗n et pour i ∈ J1, nK et q ∈ [0, 1], soit
⊗i−1
µ(i)
p = B(p) ⊗ B(q) ⊗ B(p)⊗n−i .
En considérant des variables U1 , . . . , Un indépendantes uniformes sur [0, 1], on a
Xi = 1Ui ≤p ∼ B(p) ,
11
et X = (X1 , . . . , Xn ) ∼ µp , et si Xi0 = 1Ui ≤q , alors le vecteur Xe (i) = (X1 , . . . , Xi−1 , X 0 , Xi+1 , . . . , Xn )
i
(i)
est de loi µp . Supposons q > p. Par monotonicité de f , on a
 
(i) (i)
µp (A) − µp (A) = P X ∈ A, X 6∈ A
e
 
= P Ui ∈]p, q], f (X e (i) ) 6= f (X)

= (q − p)Ipi (f ) .
(i)
Par un argument similaire, si q < p, µp (A) − µp (A) = (q − p)Ipi (f ). Ainsi, en divisant par q − p
et en faisant tendre q vers p, on a
∂µp (A)
= Ipi (f ) .
∂pi
Et ainsi
n
dµp (A) X ∂µp (A)
= = Ip (f ) .
dp ∂pi
i=1


Proposition 1.8. Soit f : {0, 1}n → {0, 1} une fonction monotone symétrique. Alors pour tout
ε ∈]0, 1/2[,
1


4 log 2ε
p1−ε − pε ≤ ,
log n
où pε est la valeur de p telle que µp (f = 1) = ε.

Preuve de la Proposition 1.8. Soit p ≤ p1/2 . Par la Proposition 1.6 et le Lemme 1.7, et comme
µp (A) ≤ 1/2, on a
dµp (A) µp (A) log n
≥ µp (A)(1 − µp (A)) log n ≥ ,
dp 2
soit
d log µp (A) log n
≥ ·
dp 2
Ainsi pour ε < 1/2,
log n
log(1/2) − log(ε) ≥ (p1/2 − pε ) ,
2
soit
1


2 log 2ε
p1/2 − pε ≤ ·
log n
Comme la même borne supérieure est valable pour p1−ε − p1/2 , on obtient bien l’inégalité voulue.

√ √ √
Exemple 1.8 (Percolation sur J1, nK2 ). Soit C = J1, nK2 la grille carrée de côté n.
Indépendamment pour chaque sommet (i, j), on tire une variable de loi B(p). On dit qu’un
sommet est ouvert si la variable en ce sommet est égale à 1 (fermé sinon), et l’on note A l’ensemble
des configurations dans lesquelles il existe un chemin de sommets ouverts allant de gauche à
droite (ici, un chemin est une suite de sommets (u1 , . . . , uk ) telle que pour tout j ≤ k − 1,
|u1j − u1j+1 | + |u2j − u2j+1 | = 1). La fonction f = 1A est clairement monotone. Par symétrie, on voit
que p1/2 = 1/2. En effet, si l’on note B l’ensemble des configurations dans lesquelles il existe un
chemin de sommets fermés allant de bas en haut, alors A = B c , et pour p = 1/2, on a clairement
12
µ1/2 (A) = µ1/2 (B) = 1 − µ1/2 (A), d’où µ1/2 (A) = 1/2. En admettant que toutes les variables ont
à peu près la même influence sur f , la Proposition 1.8 implique qu’il y a une transition abrupte
autour de p = 1/2.

13
 Chapitre 2

Méthode de Cramér-Chernoff et inégalités classiques

1. Méthode de Cramér-Chernoff
Soit Z une variable aléatoire réelle d’espérance EZ finie. La fonction génératrice des moments
de Z, ou transformée de Laplace, est la fonction qui à λ ∈ R associe EeλZ ∈ R+ ∪ {+∞}. On
note
ψZ (λ) = log Eeλ(Z−EZ) .
En passant à l’exponentielle et en appliquant l’inégalité de Markov, on a, pour tout t ≥ 0 et
λ ≥ 0,  
P(Z − EZ ≥ t) ≤ P eλ(Z−EZ) ≥ eλt ≤ e−λt Eeλ(Z−EZ) = e−{λt−ψZ (λ)} .
Comme cela est vrai pour tout λ ≥ 0, on peut choisir celui qui minimise la quantité ci-dessus et
l’on a
P(Z − EZ ≥ t) ≤ e− supλ≥0 {λt−ψZ (λ)} .
Si l’on s’intéresse aux déviations de Z  vers la gauche , on peut écrire, pour tout t ≥ 0 et
λ ≥ 0,
P(Z − EZ ≤ −t) = P(−Z + EZ ≥ t) ≤ e−λt Ee−λ(Z−EZ) ,
et ainsi
P(Z − EZ ≤ −t) ≤ e− supλ≥0 {λt−ψZ (−λ)} = e− supλ≥0 {λt−ψ−Z (λ)} .
La fonction ψZ∗ : t 7→ supλ≥0 {λt − ψZ (λ)} s’appelle la transformée de Cramér de Z − EZ. Comme
ψZ (0) = 0, on a ψZ∗ ≥ 0. De plus, par l’inégalité de Jensen, λt − ψZ (λ) ≤ λt, qui est négatif pour
t ≥ 0 et λ ≤ 0. Pour t ≥ 0, on peut donc écrire
ψZ∗ (t) = sup{λt − ψZ (λ)} .
λ∈R

Ainsi, sur R+ , la transformée de Cramér ψ ∗ correspond à la transformée de Legendre de ψ.

Remarquons aussi que, si EeλZ = +∞ pour tout λ > 0, alors la fonction ψZ∗ est identiquement
nulle, ce qui n’a pas beaucoup d’intérêt (la borne de Cramér–Chernoff est triviale dans ce cas).
Maintenant, si l’ensemble I = λ ≥ 0, EeλZ < +∞ n’est pas réduit à {0} (I est alors de la


forme [0, b[ avec 0 < b ≤ +∞), la fonction ψZ est convexe et continuement différentiable sur I
avec ψZ (0) = ψZ0 (0) = 0, et on peut écrire
ψZ∗ (t) = sup{λt − ψZ (λ)} = λt t − ψZ (λt ) ,
λ∈I

où λt vérifie ψZ0 (λt ) = t.

λ2 σ 2 t
Exemple 2.1 (Variable gaussienne). Si Z ∼ N (0, σ 2 ), on a ψZ (λ) = 2 et t = σ2
. La
méthode de Cramér-Chernoff donne alors, pour tout t ≥ 0,
t2
P(Z ≥ t) ≤ e− 2σ2 .
14
Exemple 2.2 (Variable de Poisson). Si Z ∼ P(θ), avec θ > 0, on a pour tout λ ∈ R,
X e−θ θk λ
EeλZ = eλk = eθ(e −1) ,
k!
k≥0

et ainsi
ψZ (λ) = θ(eλ − λ − 1) .
On obtient alors, pour t ≥ 0,
   
t t
λt = log 1 + et ψZ∗ (t) = θh ,
θ θ
avec h définie pour
∗ t

x ≥ −1 par h(x) = (1 + x) log(1 + x) − x. On obtient de même, pour 0 ≤ t ≤ θ,
ψ−Z (t) = θh − θ .

Exemple 2.3 (Variable Gamma). Soit Z ∼ Γ(p, θ) une variable de loi Gamma de paramètres
p, θ > 0, de densité donnée par
θp p−1 −θx
x 7→ x e 1{x≥0} .
Γ(p)
p p
On peut facilement vérifier que EZ = θ et Var Z = .
On a pour tout λ < θ,
θ2

λp λ
ψZ (λ) = − − p log 1 − .
θ θ
En utilisant l’inégalité (laissée en exercice)
u2
∀u ∈ [0, 1[, − log(1 − u) − u ≤ ,
2(1 − u)
on obtient que pour tout λ ∈ [0, θ[,
pλ2
ψZ (λ) ≤ .
2θ2 (1 − λ/θ)
u2
Pour λ ≤ 0, on peut utiliser l’inégalité − log(1 − u) − u ≤ 2 pour tout u ≤ 0 et obtenir que pour
tout λ ≤ 0,
pλ2
ψZ (λ) ≤ 2 .
2θ

2. Variables sous-gaussiennes, sous-Poisson, sous-gamma

On dit qu’une variable Z est sous-gaussienne avec facteur de variance σ 2 > 0 si pour tout
λ ∈ R,
λ2 σ 2
ψZ (λ) ≤ ·
2
Si cette égalité est vérifiée pour λ ≥ 0 (resp. λ ≤ 0), on dit qu’elle est sous-gaussienne à droite
(resp. à gauche).

On dit qu’une variable Z est sous-Poisson avec facteur de variance v > 0 et facteur d’échelle
c > 0 si pour tout λ ∈ R,
v
ψZ (λ) ≤ 2 (ecλ − cλ − 1) ·
c
15
Si cette égalité est vérifiée pour λ ≥ 0 (resp. λ ≤ 0), on dit qu’elle est sous-Poisson à droite (resp.
à gauche).

On dit qu’une variable Z est sous-gamma à droite avec facteur de variance v > 0 et facteur
d’échelle c > 0 si pour tout λ ∈ [0, 1/c[,
vλ2
ψZ (λ) ≤ .
2(1 − cλ)
Ainsi par example, une variable de loi Γ(p, θ) est sous-gamma à droite avec facteur variance
v = p/θ2 et facteur d’échelle c = 1/θ, et sous-gaussienne à gauche avec facteur de variance v.

Proposition 2.1. Une variable sous-Poisson avec facteur de variance v > 0 et facteur d’échelle
c > 0 est sous-gaussienne à gauche avec facteur de variance v, et sous-gamma à droite avec
facteur de variance v et facteur d’échelle c/3.

Preuve de la Proposition 2.1. Supposons que pour tout λ ∈ R,

v
ψZ (λ) ≤ 2 (ecλ − cλ − 1) ·
c
(cλ)2 vλ2
Pour λ ≤ 0, on a ecλ − cλ − 1 ≤ 2 . Ainsi, pour tout λ ≤ 0, on a bien ψZ (λ) ≤ 2 .
Pour λ ≥ 0, on a
+∞ +∞
X (cλ)k X (cλ)k
ecλ − cλ − 1 = = (cλ)2 ·
k! (k + 2)!
k=2 k=0

En utilisant que pour tout k ≥ 0, (k + 2)! ≥ 2 · 3k ,

on obtient
+∞ 
vλ2 X cλ k

ψZ (λ) ≤ ·
2 3
k=0
Ainsi, pour tout λ ∈ [0, 3/c[, on a
vλ2
ψZ (λ) ≤ ·
2 (1 − cλ/3)


Proposition 2.2. Si Z est sous-gamma à droite avec facteur de variance v > 0 et facteur
d’échelle c > 0, alors, pour tout t ≥ 0,
t2
 
P(Z − EZ ≥ t) ≤ exp − .
2(v + ct)
Démonstration.Voir feuilles d’exercices. 

3. Sommes de variables indépendantes

Soit (X1 , . . . , Xn ) une suite de v.a.r. indépendantes et Z = ni=1 Xi . La transformée de
P

Laplace de Z s’exprime facilement en fonction de celle des Xi : EeλZ = ni=1 EeλXi , et ainsi
Q

n
X
ψZ (λ) = ψXi (λ) .
i=1
16
Exemple 2.4 (Loi binomiale). Soient X1 , . . . , Xn des variables i.i.d. de loi de Bernoulli B(p),
Pn
pour p ∈ [0, 1], et Z = On a, pour tout λ ∈ R,
i=1 Xi .
n   o
ψZ (λ) = n log peλ + 1 − p − λp ≤ np(eλ − λ − 1) ,

où l’on a utilisé log(1 + x) ≤ x.Ainsi Z est sous-poisson avec facteur de variance np et facteur
d’échelle 1. En combinant les Propositions 2.1 et 2.2, on a, pour t ≥ 0,
t2
 
P (Z − EZ ≥ t) ≤ exp − ,
2(np + t/3)
et
t2
 
P (Z − EZ ≤ −t) ≤ exp − .
2np
Remarquons que si t ∈ [0, np], on obtient
3t2
 
(2.1) P (|Z − EZ| ≥ t) ≤ 2 exp − .
8np
Dans l’exemple ci-dessus, on sait calculer explicitement la transformée de Laplace de chaque
variable. Ce que nous allons voir maintenant, c’est que l’on peut obtenir des bornes parfois
très bonnes sur la transformée de Laplace avec seulement très peu d’informations sur la loi des
variables.

3.1. Inégalité d’Hoeffding.

Proposition 2.3 (Inégalité d’Hoeffding). Soit (X1 , . . . , Xn ) une suite de v.a.r. indépendantes
Pn
et Z = i=1 Xi . Si pour tout i ∈ J1, nK, il existe ai , bi ∈ R tels que ai ≤ Xi ≤ bi , alors, pour tout
t ≥ 0,
2t2
 
P (Z − EZ ≥ t) ≤ exp − Pn 2
.
i=1 (bi − ai )

Preuve de la Proposition 2.3. Montrons d’abord le résultat suivant : si X est une v.a.r. telle que
a ≤ X ≤ b, alors pour tout λ ∈ R,
h i λ2 (b − a)2
(2.2) log E eλ(X−EX) ≤ ·
8
En effet, posons Y = X−a EX−a
b−a et p = b−a , de telle sorte que 0 ≤ Y ≤ 1 et EY = p. Par convexité
de λ 7→ eλY , on a eλY ≤ Y eλ + 1 − Y , si bien que
log Eeλ(Y −EY ) ≤ log(peλ + 1 − p) − λp := ϕ(λ) .
Par le théorème de Taylor, il existe θ entre 0 et λ tel que
λ2 00
ϕ(λ) = ϕ(0) + λϕ0 (0) +
ϕ (θ) .
2
Il suffit maintenant de remarquer que ϕ(0) = ϕ0 (0) = 0 et que
p(1 − p)eθ 1
ϕ00 (θ) = θ 2
≤ ·
(pe + 1 − p) 4
On obtient alors
λ2 (b − a)2
log Eeλ(X−EX) = log Ee(b−a)λ(Y −EY ) ≤ ·
8
17
Maintenant, par indépendance des Xi , on a
n n
X λ2 X
log Eeλ(Z−EZ) = log Eeλ(Xi −EXi ) ≤ (bi − ai )2 ,
8
i=1 i=1
et la méthode de Cramér-Chernoff donne alors, pour tout t > 0,
2
n o
− supλ≥0 λt− λ8 v 2t2
P (Z − EZ ≥ t) ≤ e = e− v ,
Pn
où l’on a noté v = i=1 (bi − ai )2 . 

Remarque 2.5. En appliquant le résultat à −Z et en utilisant une borne union, on a

2t2
 
P (|Z − EZ| ≥ t) ≤ 2 exp − Pn 2
.
i=1 (bi − ai )

Exemple 2.6 (Loi binomiale). Si X1 , . . . , Xn sont des variables i.i.d. de loi de Bernoulli B(p),
p ∈ [0, 1], l’inégalité de Hoeffding donne, pour tout t ≥ 0,
n
!
2t2
X  
P Xi − np ≥ t ≤ exp − .
n
i=1
On obtient ainsi une inégalité sous-gaussienne avec un facteur de variance de l’ordre de n. Pour
p fixé dans ]0, 1[, c’est bien le bon ordre pour la variance d’une variable binomiale. Mais si p  1,
par exemple pour p = n1 , cela devient une très mauvaise borne, la vraie variance étant d’ordre 1.
Le comportement de la somme n’est plus gaussien, mais poissonien (ce que l’on avait remarqué
dans l’exemple 2.4) et appliquer l’inégalité de Hoeffding n’est pas judicieux.

3.2. Inégalité de Bennett.

Proposition 2.4 (Inégalité de Bennett). Soient X1 , . . . , Xn des variables aléatoires indépendantes

de variance finie et telles que Xi ≤ c avec c > 0. On pose Z = ni=1 Xi et v = ni=1 E[Xi2 ].
P P

Alors, pour tout λ ≥ 0,

v
log Eeλ(Z−EZ) ≤ 2 φ(cλ) ,
c
avec φ(λ) = eλ − λ − 1. De plus, pour tout t ≥ 0,
  
v ct
P (Z − EZ ≥ t) ≤ exp − 2 h ,
c v
avec h(x) = (1 + x) log(1 + x) − x.

Remarque 2.7. L’inégalité de Bennett affirme que si chaque variable d’une suite indépendante
est majorée par c, alors la somme est sous-Poisson à droite avec facteur de variance v, la somme
des moments d’ordre 2, et facteur d’échelle c, donc sous-gamma à droite avec facteurs v et c/3.
Ainsi, on a la borne plus manipulable
t2
 
(2.3) P (Z − EZ ≥ t) ≤ exp − .
2(v + ct/3)
Preuve de la Proposition 2.4. Par homogénéité, on peut supposer c = 1. Remarquons d’abord
que la fonction u 7→ φ(u)
u2
(prolongée par continuité en 0) est croissante sur R. Comme Xi ≤ 1, on
a alors, pour λ ≥ 0,
eλXi = 1 + λXi + φ(λXi ) ≤ 1 + λXi + Xi2 φ(λ) .
18
Ainsi,
n
X h i
log Eeλ(Z−EZ) = log E eλ(Xi −EXi )
i=1
n
X
log 1 + λEXi + E[Xi2 ]φ(λ) − λEXi


≤
i=1
n
X
≤ E[Xi2 ]φ(λ) ,
i=1

où pour la dernière inégalité on a utilisé log(1
+ x) ≤ x. Maintenant, pour t ≥ 0, la fonction

λ 7→ λt − vφ(λ) est maximale en λ = log 1 + vt et vaut en ce point
      
t t t t
t log 1 + −v − log 1 + = vh .
v v v v


Exemple 2.8 (Loi binomiale). Reprenons l’exemple de la loi binomiale de paramètres n et

1/n. En appliquant l’inégalité de Bennett (ou plutôt la version (2.3)) avec c = 1 et v = 1, on a
n
!
t2
X  
P Xi − 1 ≥ t ≤ exp − .
2(1 + t/3)
i=1

Pour t fixé (i.e. ne dépendant pas de n), cela donne une bien meilleure concentration que celle qui
provenait de l’inégalité de Hoeffding. Morale de l’histoire : ne pas forcer une variable poissonnienne
à être sous-gaussienne !

Exemple 2.9 (Degrés dans un graphe aléatoire dense). Soit G = (V, E) ∼ G(n, pn ) un
graphe aléatoire d’Erdös–Renyi, c’est-à-dire un graphe dont l’ensemble de sommets V est de
cardinal n et dont l’ensemble d’arêtes E est formé en connectant chaque paire de sommets
distincts indépendamment avec probabilité pn . On suppose npn  log n (régime dit dense). Soit
Du le degré du sommet u, i.e.
1{{u,v}∈E} .
X
Du =
v6=u

Comme les indicatrices sont i.i.d. de loi B(pn ), on a Du ∼ Bin(n − 1, pn ). En particulier

EDu = (n − 1)pn  log n. Par l’inégalité (2.1), pour ε ∈]0, 1[,

3ε2 (n − 1)pn
   
Du
P − 1 ≥ ε ≤ 2 exp − .
(n − 1)pn 8
Et en utilisant une borne union,
!
[  3ε2 (n − 1)pn
 
Du
P −1 ≥ε ≤ 2n exp − = o(1) .
(n − 1)pn 8
u∈V

Du P
Ainsi, supu∈V (n−1)p n
− 1 −→ 0. Dans le régime dense, le graphe d’Erdös–Renyi est presque
régulier : tous les degrés sont concentrés autour de (n − 1)pn .
19
 3.3. Inégalité de Bernstein. À la fois l’inégalité de Hoeffding et l’inégalité de Bennett
reposent sur le fait que les variables sont bornées (soit des deux soit d’un seul côté). L’inégalité de
Bernstein montre que l’on peut établir le comportement sous-gamma d’une somme de variables
indépendantes en faisant seulement une hypothèse sur la croissance des moments.

Proposition 2.5 (Inégalité de Bernstein). Soient X1 , . . . , Xn des variables indépendantes et

Pn Pn 2
soit Z = i=1 Xi . On suppose qu’il existe v et c tels que i=1 EXi ≤ v et
n
X vk!ck−2
∀k ≥ 3, E(Xi )k+ ≤ ·
2
i=1

Alors pour tout λ ∈ [0, 1/c[,

vλ2
log Eeλ(Z−EZ) ≤ ,
2(1 − cλ)
ce qui implique que pour tout t ≥ 0,
t2
 
P (Z − EZ ≥ t) ≤ exp − .
2(v + ct)
Preuve de la Proposition 2.5. En notant φ(u) = eu − u − 1 et en utilisant l’inégalité log(1 + x) ≤ x,
on a
Xn
log Eeλ(Z−EZ) = {log (1 + λEXi + Eφ(λXi )) − λEXi }
i=1
Xn
≤ Eφ(λXi ) .
i=1

u2
Comme pour tout u ≤ 0, φ(u) ≤ 2 (et que φ(0) = 0), on a
λ2 (Xi )2− X λk (Xi )k+ λ2 Xi2 X λk (Xi )k+
φ(λXi ) = φ(λ(Xi )− ) + φ(λ(Xi )+ ) ≤ + = + .
2 k! 2 k!
k≥2 k≥3

Ainsi pour λ ∈ [0, 1/c[,

n n n
X λ2 X X λk X
Eφ(λXi ) ≤ E[Xi2 ] + E[(Xi )k+ ]
2 k!
i=1 i=1 k≥3 i=1

λ2 v X λk vck−2 λ2 v X vλ2
≤ + = (λc)k = ·
2 2 2 2(1 − cλ)
k≥3 k≥0

Exemple 2.10 (Norme d’un vecteur sous-gaussien). Soit X = (X1 , . . . , Xn ) un vecteur

aléatoire de Rn dont les coordonnées sont indépendantes. On note
v
u n
uX
kXk2 = t Xi2
i=1

la norme euclidienne de X. Supposons que chaque coordonnée est d’espérance nulle et de variance
1. En particulier, EkXk22 = n. À quel point la norme est-elle concentrée par rapport à son
20
espérance ? Faisons l’hypothèse supplémentaire que chaque entrée est sous-gaussienne (avec
facteur de variance 1) :
λ2
∀i ∈ J1, nK, ∀λ ∈ R, ψXi (λ) ≤ ·
2
Montrons que si X est sous-gaussienne avec facteur de variance 1, alors X 2 − 1 est sous-gamma à
droite avec facteur de variance 16 et facteur d’échelle 2, et sous-gaussienne à gauche avec facteur
de variance 16. En effet,
Z +∞   Z +∞  
1
2k 2k
EX = P X > t dt = P |X| > t 2k dt
0 0
Z +∞ ( ) Z +∞
t 1/k
≤ 2 exp − k+1
dt = 2 k uk−1 e−u du = 2k+1 k! ,
0 2 0

t1/k
où l’on a utilisé la majoration de Cramér–Chernoff, puis le changement de variable u = 2 .
Ainsi, pour tout λ ≥ 0,
λ2
 
−λ(X 2 −1) −λX 2 4
log Ee = λ + log Ee ≤ λ + log 1 − λ + EX ≤ 8λ2 .
2
Par indépendance des Xi , on a donc
2
∀λ ≥ 0, log Ee−λ(kXk2 −n) ≤ 8nλ2 ,
ce qui implique
t2
 
kXk22


∀t ≥ 0, P − n ≤ −t ≤ exp − .
32n
D’autre part, pour tout λ ∈ [0, 1/2[,
  
h i 2 k
(λX )  X k k+1 8λ2
2
X
log E eλ(X −1) = −λ + log 1 + λ + E  ≤ λ 2 = ·
k! 1 − 2λ
k≥2 k≥2

et ainsi
2 8nλ2
∀λ ∈ [0, 1/2[, log Eeλ(kXk2 −n) ≤ ,
1 − 2λ
ce qui implique
t2
 
kXk22


∀t ≥ 0, P ≥ n + t ≤ exp − .
4(8n + t)
En combinant les deux inégalités, on obtient
t2
 
2


(2.4) ∀t ≥ 0, P kXk2 − n ≥ t ≤ 2 exp − .
4(8n + t)
Maintenant utilisons le fait que pour tout z, δ ≥ 0, |z − 1| ≥ δ implique |z 2 − 1| ≥ max{δ, δ 2 }
pour obtenir que
kXk22 nδ 2
     
kXk2 2
P √ −1 ≥δ ≤P − 1 ≥ max{δ, δ } ≤ 2 exp − .
n n 36
√
En posant t = δ n, on a finalement
 2
√
t
P kXk2 − n ≥ t ≤ 2 exp − .
36
√
On a ainsi montré que X était extrêmement proche de la sphère de rayon n : avec grande
probabilité, X est à distance constante de cette sphère. Le fait que les déviations soient si petites
21
peut paraı̂tre surprenant mais tentons d’en donner l’intuition. On a d’abord montré que la norme
√
au carré kXk22 était concentrée autour de n avec des fluctuations d’ordre n (cela est naturel,
kXk22 étant une somme de n variables aléatoires possédant un moment d’ordre 2, cf. TCL). De
√
façon non-rigoureuse, kXk22 = n ± O( n). Mais
q √ √
n ± O( n) = n ± O(1) .

Exemple 2.11 (Le lemme de Johnson-Lindenstrauss). Une application surprenante de

l’inégalité de Bernstein est le lemme de Johnson-Lindenstrauss, qui énonce qu’étant donnés n
points dans un espace euclidien de dimension arbitrairement grande, on peut les plonger dans un
espace euclidien de dimension d de telle sorte que toutes les distances entre deux points soient
préservées à un facteur 1 ± ε près, pourvu que d soit plus grand qu’une constante fois log ε2
n
. La
preuve repose sur la méthode probabiliste. Nous allons définir une notion naturelle de projection
aléatoire et montrer qu’une projection tirée aléatoirement selon cette loi vérifie la propriété de
préservation des distances avec grande probabilité. Pour simplifier, supposons que l’espace de
départ est RD avec D ≥ 1. Mais insistons sur le fait que le résultat est complètement indépendant
de la dimension de départ D, et que l’on pourrait en fait remplacer RD par un espace de Hilbert
séparable de dimension infinie.
On construit une application linéaire aléatoire W : RD → Rd de la façon suivante. Soient
(Xi,j )1≤i≤d,1≤j≤D une suite i.i.d. de variables aléatoires sous-gaussiennes avec facteur de variance
1. Pour α = (α1 , . . . , αD ) ∈ RD , on pose
1
W (α) = √ (W1 (α), . . . , Wd (α)) ,
d
avec, pour 1 ≤ i ≤ d,
D
X
Wi (α) = αj Xi,j .
j=1

Soient x1 , . . . , xn des points distincts de RD et notons S le sous-ensemble de la boule unité défini

par
 
xi − xj
S= ,1≤i<j≤n .
kxi − xj k
 2
Nous allons montrer que pour tout ε, δ ∈]0, 1[, si d ≥ 36 ε 2 log n
δ , alors
 
2
P sup kW (α)k − 1 ≤ ε ≥ 1 − δ .
α∈S

Autrement dit, avec probabilité 1 − δ, l’application W vérifie que pour tout i, j ∈ J1, nK,

(1 − ε)kxi − xj k2 ≤ kW (xi ) − W (xj )k2 ≤ (1 + ε)kxi − xj k2 .

Soit α ∈ RD tel que kαk = 1. Remarquons que pour tout i ∈ J1, dK, et pour tout λ ∈ R,
D D α2 2
jλ λ2
h i Y h i Y
E eλWi (α) = E eλαj Xi,j ≤ e 2 =e2 .
j=1 j=1

Ainsi, les variables Wi (α) sont sous-gaussiennes avec facteur de variance 1. Et comme elles sont
indépendantes, l’exemple précédent 2.10 s’applique et l’inégalité (2.4), appliquée avec d au lieu
22
de n, et dε au lieu de t, donne
dε2
 
2


P kW (α)k − 1 ≥ ε ≤ 2 exp − .
4(8 + ε)
En utilisant que ε ≤ 1 et que |S| ≤ n(n−1)
2 , on obtient
dε2
   
P sup kW (α)k2 − 1 ≥ ε ≤ n2 exp − ≤ δ,
α∈S 36
 2
pour d ≥ 36
ε 2 log n
δ .

23
 Chapitre 3

L’approche par martingales

Soient (Ω, F, P) un espace de probabilité et Z : Ω → R une variable aléatoire intégrable. Soit

(Fi )ni=0 une filtration, i.e. une suite croissante de tribus sur Ω avec {∅, Ω} = F0 ⊂ F1 ⊂ · · · ⊂
Fn = F. La martingale de Doob associée à Z et (Fi ) est la suite de variables aléatoires (Zi )ni=0
définies par
Zi = E[Z Fi ] .
La suite (Zi ) est adaptée à la filtration (Fi ) (Zi est Fi -mesurable) et E[Zi Fi−1 ] = Zi−1 . En
remarquant que Zn = Z et que Z0 = EZ, on peut écrire
n
X
Z − EZ = (Zi − Zi−1 ) .
i=1

1. L’inégalité d’Azuma-Hoeffding
Proposition 3.1 (Inégalité d’Azuma–Hoeffding). Si pour tout i ∈ J1, nK, il existe ai , bi ∈ R
tels que ai ≤ Zi − Zi−1 ≤ bi , alors, pour tout t > 0,
2t2
 
P (Z − EZ ≥ t) ≤ exp − Pn 2
.
i=1 (bi − ai )

Preuve de la Proposition 3.1. Comme les variables Z0 , . . . , Zn−1 sont Fn−1 -mesurables, on a ,
pour tout λ ≥ 0,
h Pn−1 h ii
Eeλ(Z−EZ) = E eλ i=1 (Zi −Zi−1 ) E eλ(Zn −Zn−1 ) Fn−1 .
λ2 (bn −an )2
En utilisant (2.2), on a E eλ(Zn −Zn−1 ) Fn−1 ≤ e
 
8 . On peut alors procéder de la même
manière en conditionnant successivement par Fn−1 , . . . , F0 , et l’on obtient
n
λ2 X
log Eeλ(Z−EZ) ≤ (bi − ai )2 .
8
i=1

On conclut en appliquant la méthode de Cramér-Chernoff. 

Exemple 3.1 (Tirage sans remise). Initialement, une urne contient K boules noires et N − K
boules blanches. À chaque temps, on tire uniformément au hasard une boule dans l’urne, sans
la remettre. Pour n ∈ J0, N − 1K, on note Xn le nombre de boules noires dans l’urne après n
−1
tirages et Mn = NX−n
n
la proportion correspondante. Remarquons que la suite (Mn )N n=0 est une
martingale adaptée à la filtration Fn = σ(X0 , . . . , Xn ). En effet, comme au temps n on tire une
boule noire avec probabilité Mn−1 , on a
Xn−1 − Mn−1 Xn−1
E[Mn Fn−1 ] = = = Mn−1 .
N −n N −n+1
24
 K
En particulier, EMn = M0 = N. De plus, en utilisant que 0 ≤ Xn−1 − Xn ≤ 1 et que
0 ≤ Xn−1 ≤ N − n + 1, on a
1 1
− ≤ Mn − Mn−1 ≤ ·
N −n N −n
Pn Pn 1 4n
Ainsi i=1 (bi − ai )2 ≤ 4 i=1 (N −i)2 ≤ et l’inégalité d’Azuma–Hoeffding donne
(N −n)2
 2
ε (N − n)2

P (Mn − EMn ≥ ε) ≤ exp − .
2n
Une conséquence majeure de l’inégalité d’Azuma–Hoeffding est l’inégalité des différences
bornées.

2. L’inégalité des différences bornées

Dans le cas où Z = f (X1 , . . . , Xn ) avec X1 , . . . , Xn indépendantes, l’inégalité d’Azuma-
Hoeffding a pour conséquence un résultat essentiel : l’inégalité des différences bornées.

Corollaire 3.2 (L’inégalité des différences bornées). Soit (X1 , . . . , Xn ) une suite de variables
aléatoires indépendantes à valeurs dans un espace mesurable X et Z = f (X1 , . . . , Xn ), avec
f : X n → R à différences bornées avec constantes c1 , . . . , cn ≥ 0 (voir Définition 1.1). Alors pour
tout t > 0,
t2
 
P (Z − EZ ≥ t) ≤ exp − Pn 2 .
2 i=1 ci
Preuve du Corollaire 3.2. Posons Fk = σ(X1 , . . . , Xk ) et soit (X10 , . . . , Xn0 ) une copie indépendante
de (X1 , . . . , Xn ). Par indépendance, on a
E Z Fk−1 = E f (X1 , . . . , Xk−1 , Xk0 , Xk+1 , . . . , Xn ) X1 , . . . , Xk .
   

Ainsi
E Z Fk − E Z Fk−1 = E f (X1 , . . . , Xk , . . . , Xn ) − f (X1 , . . . , Xk0 , . . . , Xn ) Fk ,
     

qui est contenu dans [−ck , ck ] par hypothèse. On conclut en appliquant l’inégalité d’Azuma–
Hoeffding. 

Exemple 3.2 (Bins and balls). Reprenons l’exemple 1.2. Si l’on change le résultat du iième
lancer, la variable Kn soit reste la même, soit est modifiée de −1 ou 1. L’inégalité des différences
bornées donne  2
t
P (Kn − EKn ≥ t) ≤ exp − .
2n
Nous verrons en Section 7 que cette inégalité peut être significativement améliorées.

Exemple 3.3 (Bin packing). Étant donnés x1 , . . . , xn ∈ [0, 1], quel est le nombre minimum de
cases de taille unitaire nécessaires pour contenir ces éléments, de telle sorte que la somme des
éléments dans chaque case n’excède pas 1 ? Notons Mn = f (X1 , . . . , Xn ) ce nombre minimum,
où X1 , . . . , Xn sont i.i.d. à support dans [0, 1]. Comme changer un des Xi ne peut pas changer la
valeur de Mn de plus que −1 ou 1, l’inégalité des différences bornées donne
 2
t
P (Mn − EMn ≥ t) ≤ exp − .
2n
25
Exemple 3.4 (Plus longue sous-suite commune). Dans sa version la plus simple, le problème
de la plus longue sous-suite commune peut s’énoncer ainsi : soit (X1 , . . . , Xn , Y1 , . . . , Yn ) une
suite i.i.d. de loi de Bernoulli B(1/2). Quelle est la longueur de la plus longue sous-suite commune
à (X1 , . . . , Xn ) et (Y1 , . . . , Yn ) ? Formellement, on s’intéresse à
Ln = max {k, Xi1 = Yj1 , . . . , Xik = Yjk , avec i1 < · · · < ik et j1 < · · · < jk } .
ELn
On sait qu’il existe γ ∈ [0, 1] tel que −→
n n→∞ γ mais la valeur de γ, appelée constante de
Chvátal-Sankoff, est inconnue (on sait que 0, 78807 ≤ γ ≤ 0, 82628). Même sans connaı̂tre la
valeur précise de l’espérance, on peut s’intéresser aux propriétés de concentration de Ln . Là
encore, changer une des variables ne peut pas perturber Ln de plus que −1 ou 1, et l’inégalité
des différences bornées (appliquée à droite et à gauche) donne
 2
t
P (|Ln − ELn | ≥ t) ≤ 2 exp − .
4n
En particulier, pour tout ε > 0,
 2
ε (ELn )2
  
Ln
P − 1 ≥ ε ≤ 2 exp − .
ELn 4n
Comme on sait que ELn ≈ n, la borne ci-dessus est en e−cε n . En particulier, elle correspond
donc au terme général d’une série convergente et le lemme de Borel-Cantelli assure alors que Ln
vérifie la loi forte des grands nombres :
Ln p.s.
−→ 1 .
ELn
Exemple 3.5 (Le voyageur de commerce). Le problème du voyageur de commerce est un
problème classique (et très difficile) d’optimisation combinatoire. Un voyageur de commerce
doit visiter n villes en revenant à son point de départ et en empruntant le chemin le plus court.
Considérons ici une version aléatoire de ce problème. Supposons que les positions des n villes
sont données par des variables i.i.d. X1 , . . . , Xn de loi uniforme sur le carré [0, 1]2 . On s’intéresse
à la variable
X n
Ln = min kXσ(i) − Xσ(i+1) k ,
σ∈Sn
i=1
où σ(n + 1) = σ(1). Le théorème de Beardwood–Halton–Hammersley affirme qu’il existe β > 0
tel que
L p.s.
√n −→ β .
n
Que peut-on dire de la concentration de Ln par rapport à son espérance ? Voyons ce que donne
l’inégalité
√ des différences bornées. Si l’on rejoue la position de la ville i, on modifie Ln d’au plus
2 2 (et cette borne est atteinte dans le cas extrême où toutes les villes sont d’abord placées en
(0, 0) et où l’on déplace la ville i en (1, 1)). On obtient alors
t2
 
P (|Ln − ELn | ≥ t) ≤ 2 exp − .
16n
Cette inégalité n’est pas très satisfaisante : le facteur de variance est de l’ordre de n, alors que
l’inégalité d’Efron–Stein nous dit que Var Ln = O(1). En effet, si l’on note Ln (i) la longueur du
plus petit parcours lorsque l’on ne prend pas en compte la ville i, on peut observer que
Ln (i) ≤ Ln ≤ Ln (i) + 2ξi ,
26
où ξi = minj6=i kXi − Xj k. Ainsi
n
X n
X
Var Ln ≤ E[(Ln − Ln (i))2 ] ≤ 4 Eξi2 = 4nEξ12 = O(1) .
i=1 i=1
Cherchons maintenant à appliquer plus finement l’inégalité d’Azuma–Hoeffding pour obtenir
une inégalité exponentielle. En notant Fi = σ(X1 , . . . , Xi ) et en observant que E[Ln (i) Fi ] =
E[Ln (i) Fi−1 ], on obtient
−2E[ξi Fi−1 ] ≤ E[Ln Fi ] − E[Ln Fi−1 ] ≤ 2E[ξi Fi ] .
Or  
 c
max E[ξi Fi ], E[ξi Fi−1 ] ≤ max E min kXk − xk ≤ √ ·
x∈[0,1]2 i+1≤k≤n n−i+1
L’inégalité d’Azuma–Hoeffding donne alors
!
t2 t2
 
P (|Ln − ELn | ≥ t) ≤ 2 exp − Pn 1 ≤ 2 exp − .
8c2 i=1 n−i+1 8c2 (log n + 1)
On verra au Chapitre 5 que l’on peut encore améliorer cette inégalité en supprimant le facteur
log n.

3. L’inégalité de Grable
Dans de nombreuses situations, la borne ni=1 (bi − ai )2 s’avère trop grande par rapport à la
P

vraie variance (cf. l’exemple de la loi Bin(n, 1/n)). On peut néanmoins obtenir une inégalité de
type Bernstein faisant intervenir une estimée plus fine de la variance.
Revenons au cadre général du début de chapitre, avec (Zi )ni=0 lamartingale de Doob associée
à Z pour la filtration (Fi )i=0 . Notons Vi = E (Zi − Zi−1 )2 Fi−1 . On définit le processus de
n


variation quadratique associé à (Zi ) par

i
X
hZii = Vj .
j=1

Proposition 3.3 ([11]). Supposons que hZin ≤ v avec v > 0, et que pour tout i ∈ J1, nK,
|Zi − Zi−1 | ≤ c. Alors pour tout λ ∈ [0, 1/c[,
λ2 v
log Eeλ(Z−EZ) ≤ ·
2(1 − λc)
Preuve de la Proposition 3.3. En développant l’exponentielle, on a, pour λ ∈ [0, 1/c[,
" +∞ #
h i X (λ(Zi − Zi−1 ))k
λ(Zi −Zi−1 )
E e Fi−1 = 1 + E Fi−1
k!
k=2
+∞
X (λc)k
≤ 1 + λ2 Vi
(k + 2)!
k=0
2
λ Vi
≤1+
2(1 − λc)
λ2 Vi
 
≤ exp .
2(1 − λc)
27
Ainsi, le processus n
λ2 hZii
 
exp λZi −
2(1 − λc) i=0
est une supermartingale. En particulier
λ2 hZin λ2 hZi0
    
E exp λZn − ≤ exp λZ0 − = exp (λEZ) .
2(1 − λc) 2(1 − λc)
Comme hZin ≤ v, on obtient bien
λ2 v
log Eeλ(Z−EZ) ≤ ·
2(1 − λc)


4. L’inégalité de Freedman
L’inégalité de Grable requiert une borne sur la variation quadratique. Or cette borne peut ne
pas être valable presque sûrement, mais seulement avec grande probabilité. L’astuce de Freedman
pour s’affranchir de l’hypothèse hZin ≤ v est de passer par un temps d’arrêt bien choisi.
Soit (Zn )n≥0 une martingale adaptée à la filtration (Fn )n≥0 , avec Z0 = 0.

Proposition 3.4 ([10]). Supposons que pour tout i ∈ N∗ , |Zi − Zi−1 | ≤ 1. Alors pour tout
t ≥ 0, et pour tout v > 0, on a
v+t
t2
  
v t
P (∃n ∈ N , Zn ≥ t , hZin ≤ v) ≤ e ≤ exp − .
v+t 2(v + t/3)
φ(u)
Preuve de la Proposition 3.4. Soit λ ≥ 0 et φ(u) = eu − u − 1. En utilisant le fait que u 7→ u2
est croissante sur R, on a
h i
E eλ(Zn −Zn−1 ) Fn−1 = 1 + E φ (λ(Zn − Zn−1 )) Fn−1
 

≤ 1 + φ(λ)Vn
≤ exp (φ(λ)Vn ) .
Ainsi le processus
(exp (λZn − φ(λ)hZin ))n≥0
est une supermartingale. En particulier, pour tout temps d’arrêt borné τ , on a
E [exp (λZτ − φ(λ)hZiτ )] ≤ 1 .
Soit τ = inf{n ≥ 0, Zn ≥ t} ∪ {∞} et soit E l’événement
E = {∃n ∈ N , Zn ≥ t , hZin ≤ v} .
Sur E, on a τ < ∞, Zτ ≥ t, et hZiτ ≤ v (puisque le processus (hZin )n≥0 est croissant). Ainsi
P(E) exp (λt − φ(λ)v) ≤ E [exp (λZτ − φ(λ)hZiτ ) 1E ] ≤ 1 .
t


Donc pour tout λ ≥ 0, on a P(E) ≤ exp (−{λt − vφ(λ)}). Pour λ = log 1 + v , on obtient
    v+t
t v
P(E) ≤ exp −vh = et ,
v v+t
avec h(x) = (1 + x) log(1 + x) − x. La dernière borne de la proposition s’obtient en utilisant
u2
h(u) ≥ 2(1+u/3) . 
28
 Chapitre 4

La méthode entropique

1. Entropie de Shannon
Soit X un ensemble dénombrable et X une variable aléatoire à valeurs dans X , de loi P .
Pour x ∈ X , on note p(x) = P(X = x). L’entropie de P (ou indifféremment l’entropie de X) est
définie comme
X
H(P ) = H(X) = E[− log p(X)] = − p(x) log p(x) ,
x∈X

avec 0 log 0 = 0. On a H(P ) ≥ 0, et, si X est un ensemble fini, alors H(P ) ≤ log |X |, la borne
étant atteinte par la loi uniforme sur X .

1.1. Un peu de théorie de l’information. D’un point de vue théorie de l’information, il

est souvent plus naturel de définir l’entropie en base 2 :
X
H2 (X) = − p(x) log2 p(x) .
x∈X

En effet, H2 (X) représente alors le nombre minimal de bits (0 ou 1) nécessaires pour coder un
mot de X de loi P . Plus précisément, on appelle code uniquement décodable une fonction ϕ de
X dans ∪n≥1 {0, 1}n , l’ensemble des suites finies de 0 et de 1, telle que si (x1 , . . . , xn ) ∈ X n et
(y1 , . . . , ym ) ∈ X m sont deux suites d’éléments de X ,

ϕ(x1 ) . . . ϕ(xn ) = ϕ(y1 ) . . . ϕ(ym ) ⇒ n = m et x1 = y1 , . . . , xn = yn .

Autrement dit, on n’a pas besoin de séparer les mots de code pour décoder, la ponctuation est
inclue dans le code. Pour x ∈ X , on note |ϕ(x)| la longueur du mot de code associé à x. Le
théorème de Kraft–McMillan affirme que pour tout code uniquement décodable ϕ,
X
2−|ϕ(x)| ≤ 1 ,
x∈X

et qu’inversement, si ` est une fonction de X dans N∗ telle que

X
2−`(x) ≤ 1 ,
x∈X

alors il existe un code uniquement décodable ϕ tel que |ϕ| = `. Par la première assertion du
théorème, à tout code uniquement décodable ϕ est associée une sous-probabilité Q sur X donnée
par q(x) = 2−|ϕ(x)| (on dit que l’on code selon la loi Q), et la longueur moyenne d’un mot de
code satisfait
X X
E [|ϕ(X)|] = p(x)|ϕ(x)| = − p(x) log2 q(x) ≥ H2 (X) .
x∈X x∈X
29
En effet, par l’inégalité de Jensen,
!
X X q(x) X
H2 (X) + p(x) log2 q(x) = p(x) log2 ≤ log2 q(x) ≤ 0.
p(x)
x∈X x∈X x∈X
Ainsi, la longueur moyenne de tout mot de code uniquement décodable est au moins égale à
l’entropie de la source. Inversement, si l’on pose `(x) = d− log2 p(x)e, alors
X
2−`(x) ≤ 1 ,
x∈X
et, par la deuxième assertion du théorème, il existe un code uniquement décodable ϕ tel que
|ϕ| = `. Pour ce code-là, on a alors
X
E [|ϕ(X)|] = p(x) d− log2 p(x)e ≤ H2 (X) + 1 .
x∈X
Si l’on connaı̂t la loi de la source P , on peut donc coder de façon optimale et atteindre la borne
inférieure de l’entropie (éventuellement +1). En pratique cependant, on ne connaı̂t pas la loi de
la source. On ne peut donc pas coder selon P . La longueur moyenne additionnelle due au fait de
coder selon Q et non pas selon P est alors donnée par
X X p(x)
− p(x) log2 q(x) − H(P ) = p(x) log2 .
q(x)
x∈X x∈X

Cette quantité s’appelle la divergence de Kullback–Leibler (ou entropie relative) de P par rapport
à Q. C’est le nombre moyen de bits additionnels lorsque l’on code selon Q alors que la source est
de loi P .
1.2. Entropie relative. Revenons en base e. Si Q  P , on définit l’entropie relative de Q
par rapport à P par
Z     
X q(x) dQ q q
D(Q P ) = q(x) log = log dQ = E (X) log (X) ,
p(x) X dP p p
x∈X

avec X ∼ P . Si Q n’est pas absolument continue par rapport à P , on pose D(Q P ) = +∞. Par
l’inégalité de Jensen, on voit facilement que D(Q P ) ≥ 0 et que D(Q P ) = 0 si et seulement si
P = Q.
1.3. Entropie conditionnelle et chain rule. Si (X, Y ) est un couple de variables aléatoires
à valeurs dans X × X , de loi P(X,Y ) , et si l’on note PX (resp. PY ) la loi marginale de X (resp. de
Y ), alors l’information mutuelle de X et Y , notée I(X, Y ), est l’entropie relative de la loi P(X,Y )
par rapport à la loi produit PX ⊗ PY , i.e.
I(X, Y ) = D(P(X,Y ) PX ⊗ PY ) = H(X) + H(Y ) − H(X, Y ) .
En particulier, cela montre que H(X, Y ) ≤ H(X) + H(Y ), avec égalité si et seulement X et Y
sont indépendantes.
L’entropie conditionnelle de X sachant Y est définie par
H(X Y ) = H(X, Y ) − H(Y ) .
On a
I(X, Y ) = H(X) − H(X Y ) = H(Y ) − H(Y X) .
Cela montre que H(X) ≥ H(X Y ) : ajouter de l’information réduit l’entropie.
30
 En itérant la définition de l’entropie conditionnelle, on obtient que si X1 , . . . , Xn sont des
v.a. sur X ,
H(X1 , . . . , Xn ) = H(X1 ) + H(X2 X1 ) + · · · + H(Xn X1 , . . . , Xn−1 ) .
C’est ce qu’on appelle la règle de la chaı̂ne (chain rule en anglais).

1.4. Inégalité de Han.

Proposition 4.1 (Inégalité de Han). Soit (X1 , . . . , Xn ) une variable aléatoire sur X n de loi
Q. Alors
n
1 X
H(X1 , . . . , Xn ) ≤ H(X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) .
n−1
i=1
Autrement dit,
n
1 X
H(Q) ≤ H(Q(i) ) ,
n−1
i=1

où Q(i) est la loi de (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ).

Preuve de la Proposition 4.1. Par la définition de l’entropie conditionnelle et le fait que le

conditionnement réduit l’entropie,
H(X1 , . . . , Xn ) = H(X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) + H(Xi X1 , . . . , Xi−1 , Xi+1 , . . . , Xn )
≤ H(X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) + H(Xi X1 , . . . , Xi−1 ) .
Et sommant ces n inégalités et en utilisant la règle de la chaı̂ne, on obtient
n
X
nH(X1 , . . . , Xn ) ≤ H(X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) + H(X1 , . . . , Xn ) .
i=1

Corollaire 4.2 (Inégalité de Han pour l’entropie relative). Soient P et Q deux probabilités
sur X n , avec P = P1 ⊗ · · · ⊗ Pn une mesure produit. Alors
Xn  
D(Q P ) ≤ D(Q P ) − D(Q(i) P (i) ) .
i=1

Preuve du Corollaire 4.2. Notons p = p1 . . . pn , q, p(i) et q (i) les densités par rapport à la mesure de
comptage de P , Q, P (i) et Q(i) respectivement, et x(i) = (x1 , . . . , xi−1 , xi+1 , . . . , xn ). Remarquons
d’abord que, comme P est produit, on a
n
X 1X X  
q(x) log p(x) = q(x) log pi (xi ) + log p(i) (x(i) )
n
n n
x∈X i=1 x∈X
n
1 X 1X X
= q(x) log p(x) + q (i) (x(i) ) log p(i) (x(i) ), .
n n
n
x∈X i=1 x(i) ∈X n−1

Ainsi
n
X 1 X X
q(x) log p(x) = q (i) (x(i) ) log p(i) (x(i) ) .
n−1
x∈X n i=1 x(i) ∈X n−1

31
 1 Pn (i)
D’autre part, par l’inégalité de Han, H(Q) ≤ n−1 i=1 H(Q ), et l’on obtient
X
D(Q P ) = − q(x) log p(x) − H(Q)
x∈X n
n
1 X X q (i) (x(i) )
≥ q (i) (x(i) ) log
n−1
i=1 x(i) ∈X n−1
p(i) (x(i) )
n
1 X
(i)
= D(Q P (i) ) .
n−1
i=1

En réarrangeant, on obtient bien l’inégalité voulue. 

2. Sous-additivité de l’entropie
On considère désormais un espace mesurable (X , E) quelconque. Soit f : X n → R+ une
fonction positive et Z = f (X1 , . . . , Xn ) avec (X1 , . . . , Xn ) à valeurs dans X n , de loi P . Si
E[Z log Z] < +∞, on définit l’entropie fonctionnelle de f sous P (ou indifféremment de Z) par
EntP f = Ent[Z] = E[Z log Z] − EZ log EZ .

h ifaire le lien avec la section suivante en remarquant que si Q  P , alors D(Q P ) =

On peut
Ent dQ
dP .

Proposition 4.3 (Formule de dualité pour l’entropie). Soit Z une variable aléatoire positive
avec E[Z log Z] < +∞. On a
Ent[Z] = sup E [Z(log T − log ET )] ,
T

où le supremum est pris sur les variables aléatoires positives intégrables et telles que Supp(Z) ⊂
Supp(T ).

Preuve de la Proposition 4.3. Quitte à considérer la variable Z/EZ, il suffit de montrer que pour
toute variable positive avec EZ = 1,
Ent[Z] = sup E [Z log T ] .
T ≥0, ET =1,Supp(Z)⊂Supp(T )

Soit T une v.a. positive avec ET = 1 et Supp(Z) ⊂ Supp(T ). En posant dQ(ω) = T (ω)dP(ω),
on a
Z  
Z(ω)
Ent[Z] − E [Z log T ] = Z(ω) log dP(ω)
Supp(T ) T (ω)
Z  
Z(ω) Z(ω)
= log dQ(ω) .
Supp(T ) T (ω) T (ω)
Par l’inégalité de Jensen,
Z      
Z(ω) Z(ω) Z Z
log dQ(ω) ≥ EQ log EQ = E[Z] log E[Z] = 0 .
Supp(T ) T (ω) T (ω) T T
On voit de plus que le supremum est atteint pour T = Z. 
On peut maintenant établir la sous-additivité de l’entropie dans le cas général.
32
Proposition 4.4 (Sous-additivité de l’entropie). Soit f : X n → R+ et Z = f (X1 , . . . , Xn )
avec X1 , . . . , Xn indépendantes. On suppose E[Z log Z] < +∞. Alors
" n #
X
(i)
Ent[Z] ≤ E Ent [Z] .
i=1

Preuve de la Proposition 4.4. Introduisons la notation Ei = E[· X1 , . . . , Xi ] avec E0 = E. On

peut alors écrire
X n
(4.1) Z (log Z − log EZ) = Z (log Ei Z − log Ei−1 Z) .
i=1

En remarquant que Ei−1 Z = E(i) E iZ

et en utilisant la Proposition 4.3, on a
h  i
E(i) [Z (log Ei Z − log Ei−1 Z)] = E(i) Z log Ei Z − log E(i) Ei Z ≤ Ent(i) [Z] ,
et en prenant l’espérance dans (4.1), on obtient bien
" n # " n #
X X
Ent[Z] = E E(i) [Z (log Ei Z − log Ei−1 Z)] ≤ E Ent(i) [Z] .
i=1 i=1

Donnons une autre caractérisation de l’entropie qui nous sera utile par la suite.

Proposition 4.5. Soit Z une variable positive avec E[Z log Z] < +∞. On a
Ent[Z] = inf E [Z(log Z − log u) − (Z − u)] .
u>0

Preuve de la Proposition 4.5. Cela découle du résultat plus général suivant : soit Φ : I → R
une fonction convexe et dérivable définie sur une intervalle ouvert I ⊂ R et soit X une variable
aléatoire à valeurs dans I. Alors
EΦ(X) − Φ(EX) = inf E Φ(X) − Φ(u) − Φ0 (u)(X − u) .
 
u∈I
En effet, soit u ∈ I. On a
E Φ(X) − Φ(u) − Φ0 (u)(X − u) − (EΦ(X) − Φ(EX)) = Φ(EX) − Φ(u) − Φ0 (u)(EX − u) .
 

Comme Φ est convexe, la quantité ci-dessus est positive. D’autre part, on voit que le supremum
est atteint en u = EX. La Proposition 4.5 vient alors en prenant I = R+ et Φ(x) = x log x
(prolongée par continuité en 0). 

3. Lien avec la transformée de Laplace

Quel est le lien de tout cela avec la concentration ? Nous avons vu qu’une façon d’obtenir
une inégalité de concentration pour une variable Z = f (X1 , . . . , Xn ) par rapport à son espérance
était de majorer la transformée de Laplace λ 7→ E[eλ(Z−EZ) ]. Or pour des fonctions f autres
que la somme, la transformée de Laplace est généralement difficile à manier. Nous allons voir
qu’une majoration de E[eλ(Z−EZ) ] peut être déduite d’une majoration de Ent[eλZ ]. En particuler,
l’argument de Herbst permet d’obtenir une majoration sous-gaussienne. Comme il est plus facile
de majorer l’entropie, notamment grâce à la sous-additivité, cela permet alors d’obtenir des
inégalités de concentration exponentielle pour des fonctions de variables indépendantes bien plus
complexes que la somme. C’est la méthode entropique.
33
Proposition 4.6. Soit Z une variable aléatoire intégrable. Pour tout λ ≥ 0, on a
1 Ent eγZ
Z λ
 
ψ(λ) = λ dγ ,
0 γ 2 E [eγZ ]

où ψ(λ) = log Eeλ(Z−EZ) .

Preuve de la Proposition 4.6. On vérifie facilement que

Ent[eλZ ]
(4.2) = λψ 0 (λ) − ψ(λ) .
EeλZ
Et l’on a
λ
γψ 0 (γ) − ψ(γ) ψ(γ) λ
Z  
λ dγ = λ = ψ(λ) ,
0 γ2 γ 0
ψ(γ)
où l’on a utilisé que γ → ψ 0 (0). 
γ→0+

La Proposition 4.6 fournit immédiatement une condition entropique suffisante pour obtenir
une inégalité sous-gaussienne, connue sous le nom d’argument de Herbst.

Proposition 4.7 (Argument de Herbst). Soit Z une variable aléatoire intégrable. S’il existe
v > 0 tel que pour tout λ ≥ 0,
h i λ2 v h i
Ent eλZ ≤ E eλZ ,
2
alors pour tout λ ≥ 0,
λ2 v
ψ(λ) ≤ ·
2
Preuve de la Proposition 4.7. Pour tout λ ≥ 0, on a

1 Ent eγZ
Z λ   Z λ
v λ2 v
ψ(λ) = λ 2 E [eγZ ]
dγ ≤ λ dγ = ·
0 γ 0 2 2


4. Inégalité de Mc Diarmid
Comme première application de la méthode entropique, présentons une amélioration de
l’inégalité des différences bornées due à McDiarmid [18].

Proposition 4.8 (Inégalité de McDiarmid). Soit f : X n → R et notons

 
ci x(i) = sup f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) − f (x1 , . . . , xi−1 , x0i , xi+1 , . . . , xn ) .
xi ,x0i

S’il existe v > 0 tel que pour tout x ∈ X n , ni=1 c2i x(i) ≤ v, et si Z = f (X1 , . . . , Xn ) avec
P

X1 , . . . , Xn indépendantes, alors pour tout t ≥ 0,

2t2
 
P (Z − EZ ≥ t) ≤ exp − .
v
34
Preuve de la Proposition 4.8. Montrons d’abord le résultat suivant (qui correspond en fait à une
version plus forte l’inégalité de Hoeffding) : si X est une variable aléatoire prenant ses valeurs
dans l’intervalle [a, b], alors pour tout λ ∈ R,

Ent[eλX ] (b − a)2 λ2
(4.3) ≤ ·
EeλX 8
En effet, par (4.2), on a
λ
Ent[eλX ]
Z
= λψ 0 (λ) − ψ(λ) = uψ 00 (u)du ,
EeλX 0

où ψ(λ) = log Eeλ(X−EX) . Or

E[X 2 euX ]E[euX ] − E[XeuX ]2

ψ 00 (u) =
E[euX ]2
= EQu [X 2 ] − EQu [X]2 ,

où Qu est la mesure de probabilité donnée par

euX(ω)
dQu (ω) = dP(ω) .
E[euX ]

Ainsi
" 2 #
a+b (b − a)2
ψ 00 (u) = VarQu (X) ≤ EQu X− ≤ .
2 4

On a donc
λ
Ent[eλX ] (b − a)2 λ2
Z
= uψ 00 (u)du ≤ ·
EeλX 0 8
Maintenant par la sous-additivité de l’entropie, on a
n
X h i
Ent[eλZ ] ≤ E Ent(i) [eλZ ] .
i=1

Notons
que conditionnellement à X (i) , la variable Z prend ses valeurs dans un intervalle de taille
ci X (i) par hypothèse. Ainsi en utilisant (4.3), on obtient

n n
" # " #
c2i X (i) λ2 (i) λZ c2i X (i) λ2 λZ



X X vλ2 h λZ i
Ent[eλZ ] ≤ E E [e ] = E e ≤ E e .
8 8 8
i=1 i=1

L’argument de Herbst nous dit alors que pour tout λ ≥ 0,

h i vλ2
log E eλ(Z−EZ) ≤ .
8
On conclut par la méthode de Chernoff. 

35
 5. Une inégalité de Sobolev logarithmique modifiée
De façon plus générale, la sous-additivité de l’entropie implique la majoration suivante sur
Ent[eλZ ].

Proposition 4.9. Soit f : X n → R et Z = f (X1 , . . . , Xn ) avec X1 , . . . , Xn indépendantes.

On note Zi = fi (X (i) ) = fi (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) où fi : X n−1 → R est une fonction
arbitraire. Alors pour tout λ ∈ R,
n
X h i
λZ
Ent[e ]≤ E eλZ φ(−λ(Z − Zi )) ,
i=1

avec φ(x) = ex − x − 1.

Preuve de la Proposition 4.9. Commençons par utiliser la sous-additivité de l’entropie :

n
X h i
Ent[eλZ ] ≤ E Ent(i) [eλZ ] .
i=1

En appliquant la Proposition 4.5 avec u = eλZi , on a

h i
Ent(i) [eλZ ] ≤ E(i) eλZ (λZ − λZi ) − (eλZ − eλZi )
h  i
= E(i) eλZ e−λ(Z−Zi ) + λ(Z − Zi ) − 1
h i
= E(i) eλZ φ(−λ(Z − Zi )) .


En utilisant la Proposition 4.9, on peut alors améliorer la Proposition 4.8 comme suit.

Proposition 4.10. Soit f : X n → R et Z = f (X1 , . . . , Xn ) avec X1 , . . . , Xn indépendantes.

Notons
Zi = inf f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn ) .
xi ∈X
Pn
S’il existe v > 0 tel que i=1 (Z − Zi )2 ≤ v, alors pour tout t ≥ 0,
 2
t
P (Z − EZ ≥ t) ≤ exp − .
2v
Remarque 4.1. En remplaçant Z par −Z, on voit que si ni=1 (Zi − Z)2 ≤ v avec Zi =
P

supxi ∈X f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn ), alors pour tout t ≥ 0,

 2
t
P (Z − EZ ≤ −t) ≤ exp − .
2v
Preuve de la Proposition 4.10. Par définition de Zi et pour λ ≥ 0, on a −λ(Z − Zi ) ≤ 0. Or pour
2
tout x ≤ 0, φ(x) ≤ x2 . Ainsi, la Proposition 4.9 donne
n
λZ λ2 X h λZ i vλ2 h i
Ent[e ]≤ E e (Z − Zi )2 ≤ E eλZ .
2 2
i=1

On conclut avec l’argument de Herbst et la méthode de Chernoff. 

36
Exemple 4.2 (Plus grande valeur propre de matrices aléatoires symétriques). Soit X =
(Xi,j )1≤i,j≤n une matrice aléatoire symétrique dont les entrées (Xi,j )i≤j sont indépendantes avec
|Xi,j | ≤ 1, et soit Z = λ1 (A) la plus grande valeur propre de A. Soit v ∈ Rn tel que kvk = 1 et

Z = t vXv = sup t
uXu .
u∈Rn ,kuk=1

0 .
Notons Zi,j la plus grande valeur propre de la matrice X i,j où l’on a rejoué l’entrée Xi,j par Xi,j
On a
(Z − Zi,j )+ ≤ t v(X − X i,j )v 1Z≥Zi,j ≤ 2|(Xi,j − Xi,j
0
)vi vj | ≤ 4|vi vj | .
Ainsi,
X X
(Z − Zi,j )2 ≤ 16 |vi vj |2 = 16kvk4 = 16 ,
i≤j i,j

et par la Proposition 4.10,

t2
 
P(Z − EZ ≥ t) ≤ exp − .
32
Remarquons que cet argument ne marche pas pour les déviations à gauche (on verra cependant
au Chapitre 5 qu’une borne similaire peut être obtenue).

Une autre conséquence importante de la Proposition 4.10 est la sous-gaussianité des fonctions
convexes lipschitziennes.

Proposition 4.11. Soient X1 , . . . , Xn des variables aléatoires indépendantes à valeurs dans

[0, 1] et soit f : [0, 1]n → R une fonction séparément convexe (i.e. convexe en chaque coordonnée
lorsque les autres sont fixées), 1-lipschitzienne (i.e. pour tous x, y ∈ [0, 1]n , |f (x)−f (y)| ≤ kx−yk),
et continument différentiable. Alors si Z = f (X1 , . . . , Xn ), pour tout t ≥ 0,
t2
P(Z − EZ ≥ t) ≤ e− 2 .
Pn 2
Preuve de la Proposition 4.11. Nous allons montrer que i=1 (Z − Zi ) ≤ v avec Zi =
inf xi f (X1 , . . . , Xi−1 , xi , Xi+1 , . . . , Xn ) et utiliser la Proposition 4.10. Soit Xi0 la valeur de xi
en laquelle l’infimum dans la définition de Zi est atteint. Par convexité en chaque coordonnée, on
a
n n  2 n  2
X X ∂f X ∂f
(Z − Zi ) ≤ 2
(X) (Xi − Xi ) ≤ 0 2
(X) = k∇f (X)k2 .
∂xi ∂xi
i=1 i=1 i=1
2
Et comme f est 1-lipschitzienne, k∇f (X)k ≤ 1. Notons que là aussi, l’argument ne marche plus
pour les déviations à gauche. 

6. Une autre inégalité de Mc Diarmid

Proposition 4.12. Soit Z = f (X1 , . . . , Xn ), avec X1 , . . . , Xn indépendantes et f : X n → R. On
Pn (i)
suppose qu’il existe v, c > 0 tels que pour tout i ∈ J1, nK, on a Z −E(i) Z ≤ c et i=1 Var Z ≤ v.
Alors pour tout λ ≥ 0, on a
v
log Eeλ(Z−EZ) ≤ 2 φ(cλ) ,
c
où φ(u) = eu − u − 1.
37
Preuve de la Proposition 4.12. Sans perdre en généralité, on suppose c = 1. Montrons d’abord
que si X est une variable aléatoire réelle telle que X − EX ≤ 1, alors pour tout λ ≥ 0, on a
h i h i
Ent eλX ≤ (λ, eλ − eλ + 1) Var(X)E eλX .

En notant ψ(λ) = log Eeλ(X−EX) , on a

Ent eλX
  Z λ
0
= λψ (λ) − ψ(λ) = uψ 00 (u)du ,
E [eλX ] 0

et l’on a vu dans la preuve de l’inégalité de Mc Diarmid que ψ 00 (u) = VarQu (X), où Qu est la
euX(ω)
mesure de probabilité donnée par dQu (ω) = E[e uX ] dP(ω). Or,

E euX (X − EX)2
 
2
VarQu (X) = VarQu (X − EX) ≤ EQu [(X − EX) ] = .
E [euX ]

Par l’inégalité de Jensen, le dénominateur E euX est plus grand que euEX . On obtient
 

h i
VarQu (X) ≤ E eu(X−EX) (X − EX)2 ≤ eu E (X − EX)2 = eu Var(X) ,
 

où l’on a utilisé X − EX ≤ 1. Ainsi

Ent eλX
  Z λ
≤ Var(X) ueu du = Var(X)(λeλ − eλ + 1) .
E [eλX ] 0

Maintenant, par la sous-additivité de l’entropie et en appliquant l’inégalité ci-dessus à la loi

conditionnelle de Z sachant X (i) , on a, pour tout λ ≥ 0,
" n #
h i X h i
Ent eλZ ≤ E Ent(i) eλZ
i=1
n
" #
X h i
λ λ (i) λZ (i)
≤ (λe − e + 1)E E e Var (Z)
i=1
n
" #
X
= (λeλ − eλ + 1)E eλZ Var(i) (Z) .
i=1
Pn (i)
Si i=1 Var (Z) ≤ v, alors on a

Ent eλZ
 
≤ v(λeλ − eλ + 1) .
E [eλZ ]

Par la Proposition 4.6, on obtient alors

λ
v(γeγ − eγ + 1) e −1 λ
Z  γ 
log Eeλ(Z−EZ) ≤ λ dγ = vλ = v(eλ − λ − 1) ,
0 γ2 γ 0

ce qu’il fallait démontrer. 

38
 7. Concentration des fonctions auto-bornées
Une fonction f : X n → R est dite auto-bornée s’il existe des fonctions fi : X n−1 → R telles
que pour tout x ∈ X n et i ∈ J1, nK,
0 ≤ f (x) − fi (x(i) ) ≤ 1 ,
et
n 
X 
f (x) − fi (x(i) ) ≤ f (x) .
i=1

Proposition 4.13. Soit f : Xn → R une fonction auto-bornée et Z = f (X1 , . . . , Xn ) avec

X1 , . . . , Xn indépendantes. Alors pour tout λ ∈ R,
log Eeλ(Z−EZ) ≤ E[Z]φ(λ) ,
où φ(λ) = eλ − λ − 1.

Remarque 4.3. Une fonction auto-bornée Z = f (X1 , . . . , Xn ) est donc sous-Poisson avec
facteur de variance EZ et facteur d’échelle 1. Par la Proposition 2.1, on a donc, pour tout t ≥ 0,
2
t2 t
− 2(EZ+t/3)
P(Z − EZ ≤ −t) ≤ e− 2EZ et P(Z − EZ ≥ t) ≤ e .

Preuve de la Proposition 4.13. Posons Zi = fi (X (i) ). Par la Proposition 4.9, on a, pour tout
λ ∈ R,
n
X h i
Ent[eλZ ] ≤ E eλZ φ(−λ(Z − Zi )) .
i=1
Comme φ est une fonction convexe, que Z − Zi ∈ [0, 1] et que φ(0) = 0, on a φ(−λ(Z − Zi )) ≤
(Z − Zi )φ(−λ). Ainsi, comme ni=1 (Z − Zi ) ≤ Z,
P
h i
(4.4) Ent[eλZ ] ≤ φ(−λ)E ZeλZ .
Par un argument similaire à l’argument de Herbst, montrons que cette inégalité entraı̂ne que
pour tout λ ∈ R, ψ(λ) ≤ EZφ(λ) avec ψ(λ) = log Eeλ(Z−EZ) . En effet, l’inégalité (4.4) peut se
réécrire
(1 − e−λ )ψ 0 (λ) − ψ(λ) ≤ EZφ(−λ) ,
ou encore
ψ10 (λ) ≤ EZψ20 (λ) ,
où ψ1 (λ) = eψ(λ) −λ
λ −1 , prolongée par continuité en 0 par ψ1 (0) = 0, et ψ2 (λ) = eλ −1 , prolongée par

continuité en 0 par ψ2 (0) = −1. En intégrant entre 0 et λ (séparément pour λ ≥ 0 et λ ≤ 0), on

obtient bient ψ(λ) ≤ EZφ(λ). 

Exemple 4.4 (Bins and balls). Reprenons l’exemple 3.2 du nombre de symboles distincts
dans un échantillon X1 , . . . , Xn i.i.d. de loi (pj )j≥1 sur N∗ . On a
1{∃i∈J1,nK, Xi =j} .
X
Kn = f (X1 , . . . , Xn ) =
j≥1

La fonction f est auto-bornée. En effet, si l’on considère les fonctions fi données par
1{∃k∈J1,nK\{i}, xk =j} ,
X
fi (x(i) ) =
j≥1

39
autrement dit le nombre de symboles distincts lorsque l’on retire l’observation i, alors on a
clairement 0 ≤ f (x) − fi (x(i) ) ≤ 1 et
n   Xn X
1{xi =j, et ∀k6=i, xk 6=j}
X
f (x) − fi (x(i) ) ≤
i=1 i=1 j≥1

1{∃!i∈J1,nK, xi =j} ≤ f (x) .

X
≤
j≥1

Ainsi par la Proposition 4.13, Kn est sous-Poissonienne avec facteur de variance EKn . Notons que
ce facteur de variance est toujours bien plus petit que n (le facteur de variance dans l’inégalité
sous-gaussienne des différences bornées). En effet, on peut montrer que, quelle que soit la loi sous-
jacente, EKn → 0. Pour la loi géométrique par exemple, EKn est de l’ordre de log n. Cependant,
n

cela ne permet toujours pas d’atteindre le facteur variance EKn,1 (l’espérance du nombre de
symboles observés une seule fois), donné par l’inégalité d’Efron–Stein, qui dans certains cas peut
être bien encore plus petit que EKn (par exemple pour la loi géométrique où EKn,1 est d’ordre
constant). On peut montrer que la variable Kn est en fait bien sous-Poissonnienne avec facteur
de variance EKn,1 (voir Chapitre 8, Section 2).

40
 Chapitre 5

La méthode de transport

L’idée de la méthode de transport est de relier la concentration d’une variable Z à un coût de

transport, c’est-à-dire au  prix  à payer pour calculer l’espérance de Z sous une loi Q plutôt
que sous la loi P .

1. Le lemme de transport
On rappelle que si P et Q sont deux mesures de probabilité sur un espace mesurable (X , E),
alors l’entropie relative de Q par rapport à P , dite aussi divergence de Kullback–Leibler, est
donnée par R  
 log dQ (x) dQ(x) si Q  P ,
X dP
D(Q P ) =
+∞ sinon.

On remarque que si Q  P , alors D(Q P ) = Ent(U ), avec U = dQ

dP .
Dans ce qui suit, pour f : X → R, on note Ef = EP f = E[f (X)] avec X ∼ P , et
EQ f = E[f (Y )] avec Y ∼ Q.

Lemme 5.1 (Lemme de transport). Soit X une variable aléatoire définie sur (Ω, F, P), à
valeurs dans (X , E), et soit Z = f (X) avec f : X → R mesurable. Pour tout λ ∈ R, on a
log Eeλ(Z−EZ) = sup λ(EQ f − Ef ) − D(Q P ) .

QP

En particulier, pour v > 0, il y a équivalence entre

(i) pour toute loi Q  P ,
q
EQ f − Ef ≤ 2vD(Q P ) ,

et
(ii) pour tout λ ≥ 0,
vλ2
log Eeλ(Z−EZ) ≤ ·
2
Preuve du Lemme 5.1. Soit λ ∈ R. En posant T = eλZ et en identifiant une loi Q  P à la
variable aléatoire U = dQ
dP (X), cela revient à montrer que

log ET = sup {E[U log T ] − E[U log U ]} .

U ≥0, EU =1

Or par la Proposition 4.3, pour toute variable U ≥ 0 avec EU = 1,

E[U log U ] = Ent(U ) ≥ E[U log T ] − log E[T ] ,
T
et il y a égalité pour U = ET .
41
 q
Maintenant, si pour tout loi Q  P , on a EQ f − Ef ≤ 2vD(Q P ), alors, pour tout λ ≥ 0,
on a
 q 
λ(Z−EZ)
log Ee ≤ sup λ 2vD(Q P ) − D(Q P ) .
QP
2
En remarquant que le supremum est atteint pour Q telle que D(Q P ) = λ2v , on obtient bien
2 2
log Eeλ(Z−EZ) ≤ λ2v . Inversement, si pour tout λ ≥ 0, log Eeλ(Z−EZ) ≤ vλ2 , alors, pour tout
λ > 0 et toute loi Q  P , on a

vλ2
λ(EQ f − Ef ) − D(Q P ) ≤ ,
2
soit
D(Q P ) vλ
EQ f − Ef ≤ + ·
λ 2
r
2D(Q P)
q
En prenant λ = v , on obtient bien EQ f − Ef ≤ 2vD(Q P ). 
Voyons comment se servir du Lemme 5.1 pour établir l’inégalité des différences bornées
(avec un facteur de variance divisé par 4). Soit (X , E) un espace mesurable, f : X n → R une
fonction mesurable, et Z = f (X) avec X = (X1 , . . . , Xn ) de loi produit P = P1 ⊗ · · · ⊗ Pn . Soit
maintenant Q  P et Y une variable aléatoire (définie sur (Ω, F, P) aussi) de loi Q.
Jusqu’ici, on a spécifié uniquement les lois marginales P et Q de X et de Y , mais l’on peut
définir la loi du couple (X, Y ) comme on le souhaite. Notons C(P, Q) l’ensemble des couplages
de P et Q, i.e. l’ensemble des couples (X, Y ) tels que X est de loi P et Y de loi Q, et soit
(X, Y ) ∈ C(P, Q). Si l’on suppose que pour c1 , . . . , cn ≥, la fonction f vérifie pour tous x, y ∈ X n ,
n
ci 1{xi 6=yi } ,
X
(5.1) f (y) − f (x) ≤
i=1

alors on peut écrire

n n
!1/2 n
!1/2
X X X
Ef (Y ) − Ef (X) ≤ ci P (Xi 6= Yi ) ≤ c2i P (Xi 6= Yi )2 ,
i=1 i=1 i=1

où l’on a utilisé l’inégalité de Cauchy-Schwarz. Comme cela est vrai pour tout couplage (X, Y ),
on voit que si l’on peut montrer l’inégalité de transport de Marton :
n
X 1
(5.2) min P (Xi 6= Yi )2 ≤ D(Q P ) ,
(X,Y )∈C(P,Q) 2
i=1

alors on obtient une inégalité sous-gaussienne avec facteur de variance v = 14 ni=1 c2i , ce qui
P

correspond à l’inégalité des différences bornées (Corollaire 3.2) avec un facteur de variance divisé
par 4.
Pour n = 1, il s’agit en fait de l’inégalité de Pinsker, qui relie l’entropie relative de deux lois
P, Q sur (X , E) avec leur distance en variation totale, définie par

(5.3) dtv (P, Q) = sup {P (A) − Q(A)} .

A∈E
42
Si p et q sont les densités respectives de P et Q par rapport à une mesure dominante µ (par
exemple µ = P + Q), alors on a
Z Z Z
1
dtv (P, Q) = (p(x) − q(x))+ dµ(x) = |p(x) − q(x)| dµ(x) = 1 − p(x) ∧ q(x)dµ(x) .
X 2 X X
La première égalité peut se vérifier en remarquant que le sup dans la définition (5.3) est atteint
pour l’ensemble A = {x ∈ X , p(x) > q(x)}, la deuxième vient du fait que p et q sont des densités,
et la troisième du fait que |p(x) − q(x)| = p(x) + q(x) − 2p(x) ∧ q(x). Cette distance peut aussi
être caractérisée en termes de couplage :
dtv (P, Q) = min P(X 6= Y ) .
(X,Y )∈C(P,Q)

En effet, pour tout couplage (X, Y ) et pour tout A ∈ E, on a

P(X 6= Y ) ≥ P(X ∈ A, Y 6∈ A) ≥ P(X ∈ A) − P(Y ∈ A) = P (A) − Q(A) .
Ainsi min(X,Y )∈C(P,Q) P(X 6= Y ) ≥ dtv (P, Q). Inversement, si dtv (P, Q) = 0, alors P = Q et l’on
peut considérer le couplage X = Y qui vérifie l’égalité. Si dtv (P, Q) = 1, alors P et Q ont des
supports disjoints et tout couplage vérifie P(X 6= Y ) = 1. Enfin, si dtv (P, Q) ∈]0, 1[, on considère
le couplage (X, Y ) donné par
(5.4) R = dtv (P, Q)R1 + (1 − dtv (P, Q)) R2 ,
avec, pour toute fonction mesurable bornéee Ψ : X × X → R,
(p(x) − q(x))+ (q(y) − p(y))+
Z Z
Ψ(x, y)dR1 (x, y) = Ψ(x, y)d(µ ⊗ µ)(x, y) ,
X ×X X ×X dtv (P, Q)2
et Z Z
1
Ψ(x, y)dR2 (x, y) = p(x) ∧ q(x)Ψ(x, x)dµ(x) .
X ×X 1 − dtv (P, Q) X
On vérifie qu’il s’agit bien d’un couplage de P et Q. De plus, comme R2 est concentrée sur
{(x, y) ∈ X × X , x = y}, on a P(X 6= Y ) ≤ dtv (P, Q).

Proposition 5.2 (Inégalité de Pinsker). Soient P et Q deux probabilités sur un ensemble

mesurable (X , E) avec Q  P . Alors
1
dtv (P, Q)2 ≤ D(Q P ) .
2
Preuve de la Proposition 5.2. On remarque que la distance en variation totale peut s’écrire
EQ g − Eg avec, pour tout x ∈ X , g(x) = 1 dQ (x)≥1 . Comme g est à valeurs dans [0, 1], la borne
dP
de Hoeffding (2.2) donne pour tout λ ≥ 0,
λ2
log Eeλ(g(X)−Eg(X)) ≤ .
8
Et par le Lemme de transport 5.1, on conclut que
s
D(Q P )
dtv (P, Q) = EQ g − Eg ≤ ·
2

Établissons maintenant l’inégalité (5.2). Soient P = P1 ⊗ · · · ⊗ Pn et Q deux lois sur X n
Y ,...,Yi−1
avec Q  P , et soient X = (X1 , . . . , Xn ) ∼ P et Y = (Y1 , . . . , Yn ) ∼ Q. Notons Qi 1
43
la loi de Yi sachant Y1 , . . . , Yi−1 . Pour coupler X et Y , on procède de la façon suivante :
on commence par générer (X1 , Y1 ) selon le couplage optimal des lois P1 et Q1 , i.e. tel que
P(X1 6= Y1 ) = dtv (P1 , Q1 ). Puis, pour i = 2, . . . , n, si (X1 , . . . , Xi−1 ) et (Y1 , . . . , Yi−1 ) ont
Y ,...,Yi−1
été générées, on génère (Xi , Yi ) selon le couplage optimal des lois Pi et Qi 1 , i.e. tel que
Y1 ,...,Yi−1
P(Xi 6= Yi Y1 , . . . , Yi−1 ) = dtv (Pi , Qi ). En utilisant l’inégalité de Jensen, les propriétés
du couplage, puis l’inégalité de Pinsker, on a
X n X n
2
E P(Xi 6= Yi Y1 , . . . , Yi−1 )2
 
P(Xi 6= Yi ) ≤
i=1 i=1
n  
Y ,...,Yi−1 2
X  
= E dtv Pi , Qi 1
i=1
n
1 X h  Y1 ,...,Yi−1 i
≤ E D Qi Pi .
2
i=1
Il n’y a plus qu’à utiliser ce qu’on appelle parfois la chain rule pour l’entropie relative pour
remarquer que
n h  i
Y ,...,Yi−1
X
E D Qi 1 Pi = D(Q P ) .
i=1

2. L’inégalité de transport conditionnelle de Marton

Relâchons l’hypothèse (5.1) et supposons qu’il existe des fonctions mesurables ci : X n → R+
telles que pour touts x, y ∈ X n ,
n
ci (x)1{xi 6=yi } .
X
(5.5) f (y) − f (x) ≤
i=1
En utilisant deux fois l’inégalité de Cauchy-Schwarz, on a
Xn
 
Ef (Y ) − Ef (X) ≤ E ci (X)P(Xi 6= Yi X)
i=1
n
X 
1/2
E ci (X)2 E P(Xi 6= Yi X)2
  
≤
i=1
n
!1/2 n
!1/2
X X
2 2
 
≤ Eci (X) E P(Xi 6= Yi X) .
i=1 i=1
On voit ainsi que si l’on peut trouver un couplage (X, Y ) tel que
n
X
E P(Xi 6= Yi X)2 ≤ 2D(Q P ) ,
 

i=1
alors on obtient une inégalité de concentration sous-gaussienne à droite avec facteur de variance
v = ni=1 Eci (X)2 .
P

Proposition 5.3 (Inégalité de transport conditionnelle de Marton). Soit P = P1 ⊗ · · · ⊗ Pn

une loi produit sur X n et Q  P . Alors
" n #
X
2 2


min E P(Xi 6= Yi X) + P(Xi 6= Yi Y ) ≤ 2D(Q P ) ,
(X,Y )∈C(P,Q)
i=1
44
 Avant de prouver la Proposition 5.3, énonçons deux lemmes importants. Comme ci-dessus,
considérons p et q les densités respectives de P et Q par rapport à une même mesure dominante
µ, et définissons
"  #
q(x) 2 q(X) 2
Z  
2
d2 (Q, P ) = 1− p(x)dµ(x) = E 1 − .
X p(x) + p(X) +

Lemme 5.4. Soit P et Q deux lois de probabilité sur X . Alors

X)2 + P(X 6= Y Y )2 = d22 (Q, P ) + d22 (P, Q) .
 
min E P(X 6= Y
(X,Y )∈C(P,Q)
n o
q(X)
Preuve du Lemme 5.4. D’une part, pour tout couplage (X, Y ), P(X = Y X) ≤ min 1, p(X) .
En effet, pour toute fonction mesurable positive ϕ,
 
q(X)
E ϕ(X)P(X = Y X) = E ϕ(X)1{X=Y } ≤ E [ϕ(Y )] = E ϕ(X)
   
.
p(X)
 
q(X)
Ainsi min(X,Y )∈C(P,Q) P(X 6= Y X) ≥ 1 − p(X) . Inversement, en considérant le couplage
+
défini en (5.4), on a
 
p(X) ∧ q(X) q(X)
P(X = Y X) = = min 1, ,
p(X) p(X)
et  
p(Y ) ∧ q(Y ) p(Y )
P(X = Y Y)= = min 1, .
q(Y ) q(Y )


Lemme 5.5. Soit P et Q deux lois de probabilité sur X avec Q  P . Alors

d22 (Q, P ) + d22 (P, Q) ≤ 2D(Q P ) .
q(X)
Preuve du Lemme 5.5. Soit X ∼ P et U = p(X) . On a
" 2 #
1
d22 (Q, P ) = E[(1 − U )2+ ] , et d22 (P, Q) =E 1− U .
U +

D’autre part,

D(Q P ) = E [U log U + 1 − U ] = E [h((1 − U )+ )] + E [h(−(U − 1)+ )] ,

avec, pour tout u ≥ 0, h(t) = (1 − t) log(1 − t) + t. Le résultat s’obtient en vérifiant que pour
2 t2
tout t ∈ [0, 1], h(t) ≥ t2 , et que pour tout t ≥ 0, h(−t) ≥ 2(1+t) . 
Preuve de la Proposition 5.3. Soit P = P1 ⊗ · · · ⊗ Pn et Q deux lois sur X n avec Q  P . Pour
coupler X et Y , on procède comme dans la preuve de (5.2). Pour i = 1, . . . , n, si (X1 , . . . , Xi−1 )
Y ,...,Yi−1
et (Y1 , . . . , Yi−1 ) ont été générées, on génère Xi de loi Pi et Yi de loi Qi 1 de telle sorte que

E P(Xi 6= Yi Y1 , . . . , Yi−1 , Xi )2 + P(Xi 6= Yi Y1 , . . . , Yi )2 Y1 , . . . , Yi−1

 

Y ,...,Yi−1 Y ,...,Yi−1
= d22 (Qi 1 , Pi ) + d22 (Pi , Qi 1 ).

45
Cela est possible par le Lemme 5.4. Remarquons que, pour ce couplage, la loi conditionnelle de
Xi sachant Y est égale à la loi conditionnelle de Xi sachant Yi , et la loi conditionnelle de Yi
sachant X est égale à la loi conditionnelle de Yi sachant Xi . Ainsi
" n # " n #
X X
P(Xi 6= Yi X)2 + P(Xi 6= Yi Y )2 = E P(Xi 6= Yi Xi )2 + P(Xi 6= Yi Yi )2 .



E
i=1 i=1

En utilisant successivement l’inégalité de Jensen, les propriétés du couplage, le Lemme 5.5, et la

chain rule pour l’entropie relative, on a
" n #
X
P(Xi 6= Yi Xi )2 + P(Xi 6= Yi Yi )2


E
i=1
" n #
X
2 2


≤E P(Xi 6= Yi Y1 , . . . , Yi−1 , Xi ) + P(Xi 6= Yi Y1 , . . . , Yi )
i=1
" n #
Y ,...,Yi−1 Y ,...,Yi−1
X
≤E d22 (Qi 1 , Pi ) + d22 (Pi , Qi 1 )
i=1
" n #
 
Y ,...,Yi−1
X
≤ 2E D Qi 1 Pi
i=1
= 2D(Q P ) .

Proposition 5.6. Soit f : X n → R et X1 , . . . , Xn des variables aléatoires indépendantes à

valeurs dans X . Notons Z = f (X1 , . . . , Xn ). Supposons qu’il existe des fonctions mesurables
ci : X n → R+ telles que, pour tous x, y ∈ X n ,
n
ci (x)1yi 6=xi ,
X
f (y) − f (x) ≤
i=1

et notons
n
X n
X
2
v= E[ci (X) ] , et v∞ = sup ci (x)2 .
i=1 x∈X n i=1

Alors pour tout λ ≥ 0,

vλ2 v∞ λ2
log Eeλ(Z−EZ) ≤ , et log Eeλ(EZ−Z) ≤ ·
2 2
Preuve de la Proposition 5.6. Soit P = P1 ⊗ · · · ⊗ Pn la loi de X. Comme on l’a vu en début de
section, pour toute loi Q  P , si Y ∼ Q,
n
!1/2
√ X  2

Ef (Y ) − Ef (X) ≤ v min E P(Xi 6= Yi X) .
(X,Y )∈C(P,Q)
i=1

Par la Proposition 5.3, on obtient

q
Ef (Y ) − Ef (X) ≤ 2vD(Q P ) ,
46
 2
et le lemme de transport donne, pour tout λ ≥ 0, log Eeλ(Z−EZ) ≤ vλ2 . Pour la deuxième
inégalité, en considérant la fonction g = −f , on a
n
!1/2 n
!1/2
X X
E[ci (Y )2 ] E P(Xi 6= Yi Y )2
 
Eg(Y ) − Eg(X) ≤ min
(X,Y )∈C(P,Q)
i=1 i=1
q
≤ 2v∞ D(Q P ) .

3. L’inégalité de distance convexe de Talagrand

L’inégalité de concentration ci-dessus a de nombreuses conséquences importantes. Elle permet
notamment d’obtenir l’inégalité de distance convexe de Talagrand. Pour A ⊂ X n et α ∈ Rn+ un
vecteur de réels positifs, on définit la distance pondérée dα (x, A) de x ∈ X n à A par
n
αi 1xi 6=yi .
X
dα (x, A) = inf dα (x, y) = inf
y∈A y∈A
i=1

La distance convexe de x à A est alors définie par

dT (x, A) = sup dα (x, A) .

α∈Rn
+ , kαk≤1

Proposition 5.7 (Inégalité de distance convexe de Talagrand). soit X = (X1 , . . . , Xn ) avec

X1 , . . . , Xn indépendantes à valeurs dans X . Pour tout A ⊂ X n et pour tout t ≥ 0,
t2
P(X ∈ A)P (dT (X, A) ≥ t) ≤ e− 4 .

Preuve de la Proposition 5.7. Notons α(x) = (α1 (x), . . . , αn (x)) l’élément α ∈ Rn+ avec kαk ≤ 1
où le supremum dans la définition de la distance convexe dT (x, A) est atteint. On a
n n n
αi (x)1xi 6=x0i − inf αi (x)1yi 6=yi0 ≤ αi (x)1xi 6=yi .
X X X
dT (x, A) − dT (y, A) ≤ inf
0 0
x ∈A y ∈A
i=1 i=1 i=1

Ainsi la fonction f : x 7→ −dT (x, A) vérifie la condition de la Proposition 5.6 avec ci = αi .

Et comme pour tout x ∈ X n , on a ni=1 αi (x)2 ≤ 1, la Proposition 5.6 implique que si X =
P

(X1 , . . . , Xn ) est un vecteur de variables indépendantes à valeurs dans X , alors la variable

Z = dT (X, A) est sous-gaussienne avec facteur de variance 1 (à gauche et à droite). Les déviations
à droite donnent que tout t ≥ 0,
(EZ)2 2
− t4
P(Z ≥ t) ≤ e 2 .
(t−EZ)2
En effet, si t < EZ, l’inégalité est trivialement vraie et si t ≥ EZ, on a P(Z ≥ t) ≤ e− 2 ≤
(EZ)2 2
− t4 t2
e 2 , où l’on a utilisé que tEZ ≤ (EZ)2 + 4 . D’autre part, en utilisant les déviations à
gauche, on a
(EZ)2
P(X ∈ A) = P(Z = 0) ≤ P(Z − EZ ≤ −EZ) ≤ e− 2 .
t2
Ainsi P(X ∈ A)P (dT (X, A) ≥ t) ≤ e− 4 . 

47
Exemple 5.1 (Le voyageur de commerce). Reprenons l’exemple 3.5 du voyageur de commerce.
Tout d’abord, montrons par récurrence que pour tout n ≥ 1, pour tout h > 0, et pour tous points
x1 , . . . , xn dans un triangle rectangle d’hypoténuse h, il existe un parcours qui part d’un bout de
l’hypoténuse, arrive à l’autre, passe par tous les points, et est tel que la somme des carrés des
longueurs de chaque arête est inférieure à h2 . Notons que par le théorème de Pythagore, il suffit
de montrer le résultat pour un plus petit triangle rectangle contenant ces n points. Pour n = 1,
c’est bon. Supposons le résultat vrai jusqu’au rang n ≥ 1, prenons n + 1 points dans le plan et
notons h la longueur de l’hypoténuse d’un plus petit triangle rectangle contenant ces points. Si
l’on divise ce triangle en deux selon la hauteur issue du sommet opposé à l’hypoténuse, alors il y
a au plus n points dans chacun des deux triangles et l’hypothèse de récurrence et le théorème de
Pythagore permettent de conclure. Ainsi, pour x = (x1 , . . . , xn ) avec xi ∈ [0, 1]2 , on peut trouver
un parcours cyclique σx passant par x1 , . . . , xn tel que la somme des carrés des longueurs de
chaque arête est inférieure à 4. Notons αi (x) deux fois la longueur de l’arête précédant xi dans
ce parcours. On a, pour tous x, y ∈ [0, 1]2n ,
n
αi (x)1yi 6=xi .
X
Ln (x) ≤ Ln (y) +
i=1
En effet, si x et y n’ont pas de points en communs, alors c’est clair. Sinon, soit σy∗ un parcours
cyclique de longueur minimale passant par y1 , . . . , yn . On peut alors parcourir les points x1 , . . . , xn
de la façon suivante : partant d’un point commun à x et y, on parcourt σx tant que les points
visités ne sont pas communs à y. Si le point suivant sur σx , disons u, est commun à y, alors on
revient en arrière jusqu’au point commun précédant et on va en u en empruntant σy∗ . Et ainsi de
suite jusqu’à revenir au point de départ. On voit que la longueur de ce parcours est bien plus
petite que Ln (y) + ni=1 αi (x)1yi 6=xi . Comme
P

n
X n
X
αi (x)2 ≤ 4 kxσx (i) − xσx (i+1) k2 ≤ 16 ,
i=1 i=1
la Proposition 5.6 donne, pour tout t ≥ 0,
t2
P(|Ln − ELn | ≥ t) ≤ 2e− 32 .

48
 Chapitre 6

Classification et théorie de Vapnik-Chervonenkis

1. Un problème d’apprentissage statistique

Soit (X, Y ) un couple de variables aléatoires avec X à valeurs dans un espace X et Y à
valeurs dans {0, 1}. Un classifieur est une fonction mesurable f : X → {0, 1}, dont l’objectif est
de prédire, à partir de X, la valeur de Y . Le risque d’un classifieur f est donné par

R(f ) = P(Y 6= f (X)) .

Si l’on pose η(X) = P(Y = 1 X), il est facile de voir que le classifieur

f • (X) = 1{η(X)≥ 1 } ,
2

appelé classifieur de Bayes, atteint le plus petit risque possible :

R(f • ) = min R(f ) = E [min{η(X), 1 − η(X)}] .

f

En pratique, le classifieur de Bayes n’est pas d’une grande utilité. Pour pouvoir le calculer, il faut
connaı̂tre la loi du couple (X, Y ) qui est généralement inconnue. Il faut apprendre à classifier
à partir d’observations issues de cette loi. Plus précisément, on observe un échantillon i.i.d. de
même loi que (X, Y ) :
Dn = ((X1 , Y1 ), . . . , (Xn , Yn )) .
L’objectif est de construire, à partir de Dn , un classifieur fbn dont le risque soit le plus petit
possible. On cherche en fait à minimiser la quantité aléatoire
 
R(fbn ) = P Y 6= fbn (X) Dn ,

où

Exemple 6.1. Dans le cas où l’ensemble X est un ensemble discret, un classifieur naturel,
appelé classifieur par majorité, est construit de la façon suivante : pour tout x ∈ X , on calcule

N0 (x) = |{i ∈ J1, nK, Xi = x, Yi = 0}| ,

et
N1 (x) = |{i ∈ J1, nK, Xi = x, Yi = 1}| ,
et on pose
(
1 si N1 (x) ≥ N0 (x),
fbnmaj (x) =
0 si N0 (x) > N1 (x).
Autrement dit, on attribue à x le label majoritaire parmi les observations de Dn pour lesquelles
Xi = x.
49
 Une méthode souvent utilisée pour construire un classifieur fbn consiste à minimiser le risque
empirique. L’idée est d’approcher le risque R(f ) d’un classifieur f par sont équivalent empirique
n
1X
Rn (f ) = 1{Yi 6=f (Xi )} .
n
i=1

P
Par la loi des grands nombres, Rn (f ) −→ R(f ). Étant donné un ensemble F de classifieurs
(ici supposé dénombrable), souvent appelé dictionnaire, la méthode de minimisation du risque
empirique consiste à choisir
fn∗ ∈ arg min Rn (f ) .
f ∈F

Remarque 6.2. Le choix de F est crucial. Prendre F égal à l’ensemble de tous les classifieurs
est souvent un très mauvais choix et conduit au sur-apprentissage (le classifieur colle parfaitement
à l’aléa des données mais n’est pas capable de prendre en compte des nouvelles observations). En
effet, si X est assez grand pour que, presque sûrement, toutes les observations Xi soient distinctes,
alors le risque empirique est toujours minimisé par le classifieur qui s’ajuste parfaitement aux
données, i.e.
n
1x=Xi Yi .
X
fn (x) =
b
i=1

Autrement dit, si x = Xi , le classifieur répond Yi et si x 6∈ {X1 , . . . , Xn }, il répond, de façon

arbitraire, 0. On a alors Rn (fbn ) = 0 mais R(fbn ) peut être bien plus grand (plus F est grand, plus
supf ∈F |Rn (f ) − R(f )| est grand). En fait, il faut choisir F assez grand pour pouvoir approcher
le classifieur de Bayes par des éléments de F mais assez petit pour que Rn (f ) reste une bonne
approximation de R(f ), uniformément sur F.

À supposer que le minimum est atteint, une solution idéale au problème d’apprentissage sur
F est donnée par
f ∗ ∈ arg min R(f ) .
f ∈F

La principale question est alors de savoir quelle est l’amplitude de l’excès de risque R(fn∗ ) − R(f ∗ ).
On peut commencer par observer que

(6.1) R(fn∗ ) − R(f ∗ ) ≤ 2 sup |Rn (f ) − R(f )| .

f ∈F

En effet,

R(fn∗ ) ≤ Rn (fn∗ ) + supf ∈F |Rn (f ) − R(f )| puisque fn∗ ∈ F par construction ,

≤ Rn (f ∗ ) + supf ∈F |Rn (f ) − R(f )| puisque fn∗ minimise Rn sur F ,
≤ R(f ∗ ) + 2 supf ∈F |Rn (f ) − R(f )| puisque f ∗ ∈ F par construction .

Le but de ce chapitre est de contrôler des quantités de la forme supf ∈F |Rn (f ) − R(f )|.

2. Inégalités de Vapnik–Chervonenkis
Soit (X , E) un ensemble mesurable et P une mesure de probabilité sur X .
50
Définition 6.1. Soit A un ensemble d’éléments de la tribu E et x = (x1 , . . . , xn ) un vecteur de
n points de X . La trace de A sur x est définie comme

tr(A, x) = {A ∩ {x1 , . . . , xn } , A ∈ A} .

Le coefficient d’éclatement (shatter coefficient) d’ordre n est donné par

s(A, n) = maxn |tr(A, x)| .

x∈X

La dimension de Vapnik-Chervonenkis de A est définie par

V(A) = sup {n ∈ N , s(A, n) = 2n } .

Exemple 6.3 (Dimension de certaines classes).

— si X = R et A = {]n− ∞, x] , x ∈ R}, alors V(A)
o = 1.
d
Qd
— si X = R et A = j=1 ] − ∞, xj ] , xj ∈ R , alors V(A) = d.
— si X = Rd et si A est l’ensemble de tous les demi-espaces, i.e. de tous les sous-ensembles
de la forme {x ∈ Rd , ha, xi ≥ b}, pour a ∈ Rd et b ∈ R, alors V(A) = d + 1.

Lemme 6.1 (Lemme de Sauer–Shelah). Pour toute classe A, et pour tout n ∈ N, on a

V(A)  
X n
s(A, n) ≤ ≤ (n + 1)V(A) .
k
k=0

Preuve du Lemme 6.1. Voir Devroye et al. [7], Chapitre 13. 

Soit X = (X1 , . . . , Xn ) un vecteur i.i.d. de loi P . Pour A ∈ E, on note
n
1X
Pn (A) = 1{Xi ∈A} ,
n
i=1

la probabilité empirique de A. Pour une partie donnée A de E, on s’intéresse dans cette section à
la variable
sup |Pn (A) − P (A)| ,
A∈A

Proposition 6.2. Soit A ⊂ E et X = (X1 , . . . , Xn ) un échantillon i.i.d. de loi P . Alors, pour

tout ε > 0, on a
 
nε2
P sup |Pn (A) − P (A)| > ε ≤ 8 s(A, n)e− 32 .
A∈A

Preuve de la Proposition 6.2. Remarquons déjà que l’on peut supposer que nε2 ≥ 2 (sinon,
le résultat est immédiat). Soit X 0 = (X10 , . . . , Xn0 ) une copie indépendante de X et notons
Pn0 (A) = n1 ni=1 1{X 0 ∈A} . Montrons que, pour nε2 ≥ 2, on a
P
i

   
ε
P sup |Pn (A) − P (A)| > ε ≤ 2P sup Pn (A) − Pn0 (A) > .
A∈A A∈A 2
51
Soit A? un élément de A tel que |Pn (A) − P (A)| > ε s’il en existe un, ou bien un élément
quelconque de A s’il n’en existe pas. On a
 
ε  ε
P sup Pn (A) − Pn0 (A) > ≥ P Pn (A? ) − Pn0 (A? ) >
A∈A 2 2
 ε
≥ P |Pn (A? ) − P (A? )| > ε , Pn0 (A? ) − P (A? ) <
2 i
h  ε
= E 1{|Pn (A? )−P (A? )|>ε} P Pn (A ) − P (A ) <
0 ? ?
X .
2
Par l’inégalité de Chebyshev, on a
 ε  4P (A? )(1 − P (A? )) 1 1
P Pn0 (A? ) − P (A? ) ≥ X ≤ 2
≤ 2 ≤ ,
2 nε nε 2
pour nε2 ≥ 2. Ainsi
   
ε 1 1
P sup Pn (A) − Pn0 (A) > ≥ P (|Pn (A? ) − P (A? )| > ε) = P sup |Pn (A) − P (A)| > ε .
A∈A 2 2 2 A∈A
Montrons maintenant que
 
0 ε nε2
P sup Pn (A) − Pn (A) > ≤ 4 s(A, n)e− 32
A∈A 2
Soit (εi )ni=1 une suite indépendante de variables de Rademacher (uniformes sur {−1, 1}), indépendante
de (X, X 0 ). Par symétrie, on a
 n   n
1Xi ∈A − 1Xi0 ∈A ∼ εi 1Xi ∈A − 1Xi0 ∈A .
i=1 i=1
Ainsi
n
  !
ε 1X   ε
P sup Pn (A) − Pn0 (A) > = P sup εi 1Xi ∈A − 1Xi0 ∈A >
A∈A 2 A∈A n 2
i=1
n
!
1X ε
≤ 2P sup εi 1Xi ∈A > .
A∈A n i=1
4
Remarquons maintenant que si A et A0
sont deux éléments de A qui ont la même intersection
avec {X1 , . . . , Xn }, alors n i=1 εi 1Xi ∈A = n1 ni=1 εi 1Xi ∈A0 . On peut donc prendre le supremum
1 Pn P

uniquement sur tr(A, X) :

n n
! !
1X ε 1X ε
P sup εi 1Xi ∈A > =P sup εi 1Xi ∈A >
A∈A n i=1 4 A∈tr(A,X) n i=1 4
 !
n
1 ε
εi 1Xi ∈A ≥
X X
≤ E P X .
n 4
A∈tr(A,X) i=1

Or l’inégalité de Hoeffding donne

n
!
1X ε nε2
P εi 1Xi ∈A > X ≤ 2e− 32 .
n 4
i=1
Ainsi
n
!
1X ε nε2 nε2
P sup εi 1Xi ∈A > ≤ 2E [|tr(A, X)|] e− 32 ≤ 2 s(A, n)e− 32 .
A∈A n i=1
4

52
Exemple 6.4. Soient X1 , . . . , Xn des variables aléatoires réelles, i.i.d. de fonction de répartition
F que l’on suppose continue. La fonction de répartition empirique est donnée par
n
1X
∀x ∈ R , Fn (x) = 1{Xi ≤x} .
n
i=1
Pour quantifier de façon uniforme la distance entre Fn et F , on introduit
Kn = sup |Fn (x) − F (x)| .
x∈R

Notons que la loi de Kn ne dépend pas de F . En effet, le vecteur (F (X1 ), . . . , F (Xn )) a la même
loi qu’un vecteur (U1 , . . . , Un ) i.i.d. de loi uniforme sur [0, 1]. Ainsi
n n
1X 1X
Kn ∼ sup 1{Ui ≤F (x)} − F (x) = sup 1{Ui ≤u} − u ,
x∈R n i=1 u∈[0,1] n i=1
où pour la deuxième égalité, on a utilisé la continuité de F . La loi de Kn s’appelle loi de
√
Kolmogorov–Smirnov, et l’on peut montrer que nKn converge en loi vers le supremum d’un
pont brownien entre 0 et 1. En notant A = {] − ∞, x], x ∈ R}, on a toujours
| tr(x1 , . . . , xn )| ≤ n + 1 ,
avec égalité quand les xi sont tous distincts. Ainsi la Proposition 6.2 donne
 
nε2
(6.2) P sup |Fn (x) − F (x)| > ε ≤ 8(n + 1)e− 32 .
x∈R

On en déduit en particulier le théorème de Glivenko-Cantelli :

p.s.
sup |Fn (x) − F (x)| −→ 0 .
x∈R

La borne (6.2) est loin d’être optimale et Massart [17] a montré que
 
nε2
P sup |Fn (x) − F (x)| > ε ≤ 2e− 2 .
x∈R

Exemple 6.5. Reprenons le cadre de l’apprentissage statistique, avec Dn = ((X1 , Y1 ), . . . , (Xn , Yn ))

un échantillon i.i.d. à valeurs dans X × {0, 1} et F un ensemble de classifieurs f : X → {0, 1}.
En associant un classifieur f à l’événement A = {f (X) 6= Y }, on définit
A = {{(x, y) ∈ X × {0, 1} , f (x) 6= y} , f ∈ F} ,
En notant
A0 = {{x ∈ X , f (x) = 1} , f ∈ F} ,
on peut montrer que s(A, n) = s(A0 , n), et donc que V(A) = V(A0 ) (voir Devroye et al. [7][Chapitre
13]). Dans le cadre de la classification, on écrira en fait s(F, n) et V(F) pour désigner s(A, n) et
V(A). Avec ces identifications et en posant Zi = (Xi , Yi ) ∼ P , on a
n
1X
Rn (f ) = 1{Zi ∈A} = Pn (A) et R(f ) = P (A) .
n
i=1
La Proposition 6.2 donne alors
!
nε2
P sup |Rn (f ) − R(f )| > ε ≤ 8 s(F, n)e− 32 .
f ∈F

53
En utilisant la borne (6.1), on obtient
nε2
P (R(fn∗ ) − R(f ∗ ) > ε) ≤ 8 s(F, n)e− 128 .
Autrement dit, pour tout δ ∈]0, 1[, on a, avec probabilité au moins 1 − δ,
s  
∗ ∗ 128 8 s(F, n)
R(fn ) − R(f ) ≤ log
n δ
s    
128 8
(6.3) ≤ log + V(F) log(n + 1) ,
n δ
où la deuxième inégalité vient du Lemme 6.1. Dans la section suivante, nous allons voir que l’on
peut remplacer log(n + 1) par un terme d’ordre constant.

3. Chaı̂nage et inégalité de Dudley

Soit X = (X1 , . . . , Xn ) i.i.d. de loi P , et ε1 , . . . , εn des variables i.i.d. de loi de Rademacher,
indépendantes de X. Pour A ∈ A, on définit
n
1X
Pnε (A) = εi 1{Xi ∈A} ,
n
i=1
la version  rademacherisée  de Pn (A). Dans le cadre de la classification, on écrira Rεn (f ) =
i=1 εi 1{f (Xi )6=Yi } .
1 Pn
n

Proposition 6.3. On a
   
ε
E sup |Pn (A) − P (A)| ≤ 2E sup |Pn (A)|
A∈A A∈A

Preuve de la Proposition 6.3. Soit X 0 = (X10 , . . . , Xn0 ) une copie indépendante de X. En écrivant
" n #
1X
P (A) = E 1{Xi0 ∈A} X ,
n
i=1
et en utilisant la convexité de la valeur absolue et du supremum, on a
   
0
E sup |Pn (A) − P (A)| ≤ E sup Pn (A) − Pn (A) .
A∈A A∈A

Maintenant, si est une suite de Rademacher indépendantes de (X, X 0 ), on a

(εi )ni=1
n
  " #
1  
εi 1{Xi ∈A} − 1{Xi0 ∈A}
X
E sup Pn (A) − Pn0 (A) = E sup
A∈A A∈A n i=1
 
ε
≤ 2E sup |Pn (A)| .
A∈A

La Proposition 6.3, combinée avec l’inégalité de McDiarmid, donne la borne suivante.

Proposition 6.4. Pour tout δ ∈]0, 1[, avec probabilité au moins 1 − δ, on a

s
log 1δ
 

sup |Pn (A) − P (A)| ≤ 2E sup |Pnε (A)| + ·
A∈A A∈A 2n
54
Preuve de la Proposition 6.4. Par la Proposition 6.3, on a
   
ε
sup |Pn (A) − P (A)| ≤ 2E sup |Pn (A)| + sup |Pn (A) − P (A)| − E sup |Pn (A) − P (A)| .
A∈A A∈A A∈A A∈A

On remarque maintenant que la variable supA∈A |Pn (A) − P (A)| vérifie l’hypothèse de l’inégalité
de McDiarmid avec ci (x(i) ) ≤ n1 . Ainsi pour tout ε > 0, on a
   
2
P sup |Pn (A) − P (A)| − E sup |Pn (A) − P (A)| > ε ≤ e−2ε n ,
A∈A A∈A
ce qui donne bien le résultat voulu. 
Dans la suite de cette section, on cherche à majorer E [supA∈A |Pnε (A)|]. Voyons déjà comment
obtenir une borne similaire à (6.3). On a
n n
  " # " #
1 1
εi 1Xi ∈A = E εi 1Xi ∈A .
X X
E sup |Pnε (A)| = E sup sup
A∈A A∈A n i=1 A∈tr(A,X) n i=1

Conditionnellement à X = (X1 , . . . , Xn ), les variables n1 ni=1 εi 1Xi ∈A et − n1 ni=1 εi 1Xi ∈A sont

P P

sous-gaussiennes avec facteur variance n1 . Or, si Y1 , . . . , Ym sont sous-gaussiennes avec facteur

variance v, on a
 
p
(6.4) E max Yj ≤ 2v log(m) ,
1≤j≤m

ce qui donne (pour m = 2| tr(A, X)|),

n
" # r
1X 2 log (2| tr(A, X)|)
E sup εi 1Xi ∈A X ≤ .
A∈tr(A,X) n i=1
n
En utilisant le Lemme 6.1, on obtient
  r r
2 log (2 s(A, n)) 2
E sup |Pnε (A)| ≤ ≤ (log(2) + V(A) log(n + 1)) .
A∈A n n
Par une méthode dite de chaı̂nage, on peut en fait se passer du terme logarithmique. Pour cela,
commençons par fixer un vecteur x = (x1 , . . . , xn ) ∈ X n fixé, et, pour a ∈ A, notons
n
1X
Ya = εi 1{xi ∈a} .
n
i=1
On introduit une pseudo-distance sur A donnée par
v
u n
u1 X
∀a, b ∈ A , dx (a, b) = t 1{xi ∈a∆b} ,
n
i=1

où a∆b = a ∪ b − a ∩ b est la différence symétrique entre a et b. Cela fait de A un espace

pseudo-métrique totalement borné. Pour δ > 0, un δ-net pour dx est un ensemble fini Aδ ⊂ A de
cardinal maximal et tel que pour tous a, b ∈ Aδ avec a 6= b, on a dx (a, b) > δ. On note
Hx (δ, A) = log |Aδ | .
La fonction δ 7→ Hx (δ, A) s’appelle l’entropie métrique de A pour la pseudo-distance dx . On
définit l’entropie métrique universelle de A par
H(δ, A) = sup HQ (δ, A) ,
Q

55
où le supremum est pris sur toutes les lois de probabilité concentrées sur un sous-ensemble fini
de X , et où HQ (δ, A) correspond à l’entropie métrique pour la pseudo-distance
p
dQ (a, b) = Q(a∆b) .
(En fait dx (a, b) = dQ (a, b) pour Q la mesure empirique associée au vecteur x.) Pour simplifier,
on suppose ici que A est fini mais le résultat suivant se généralise au cas infini.

Proposition 6.5 (Inégalité de Dudley). Supposons que A est fini. On a

  Z 1/2 p
12
E sup Ya ≤√ H(u, A)du .
a∈A n 0

Preuve de la Proposition 6.5. Remarquons déjà que pour tous a, b ∈ A et tout λ > 0, on a, par
l’inégalité de Hoeffding,
n
log Ee n (1{xi ∈a} −1{xi ∈b} )εi
X λ
λ(Ya −Yb )
log Ee =
i=1
n
λ2
1{xi ∈a} − 1{xi ∈b}
X
2
≤
2n2
i=1
λ2
= d2x (a, b) .
2n
2
Ainsi, Ya − Yb est sous-gaussienne avec facteur de variance dx (a,b)
n . Pour j ∈ N, posons δj = 2
−j et

considérons un δj -net Aj de A pour dx . Pour tout j ∈ N, on peut alors trouver une application
πj : A → Aj telle que
∀a ∈ A , dx (a, πj (a)) ≤ δj .
Comme A est fini, il existe un entier J ∈ N tel que, pour tout a ∈ A,
J 
X 
Ya = Yπ0 (a) + Yπj+1 (a) − Yπj (a) .
j=0

D’autre part, comme on a toujours dx (a, b) ≤ 1, on peut prendre A0 = {a0 } pour un élément a0
quelconque, auquel cas π0 (a) = a0 pour tout a ∈ A. Comme E[Ya0 ] = 0, on obtient
  X J   
E sup Ya ≤ E sup Yπj+1 (a) − Yπj (a) .
a∈A j=0 a∈A

Maintenant, pour tout j ∈ N, on a

n  o
Yπj (a) , Yπj+1 (a) , a ∈ A ≤ |Aj |.|Aj+1 | ≤ |Aj+1 |2 ,

et, par l’inégalité triangulaire,

 
dx Yπj (a) , Yπj+1 (a) ≤ δj + δj+1 = 3δj+1 .

Ainsi, en utilisant l’inégalité (6.4), on a

s
  2
18δj+1 6δj+1
 q
E sup Yπj+1 (a) − Yπj (a) ≤ log (|Aj+1 |2 ) = √ H(δj+1 , A) ,
a∈A n n
56
où H(δj+1 , A) correspond à l’entropie universelle. En sommant sur j, et en utilisant la décroissance
de δ 7→ H(δ, A) et le fait que δj = 2(δj − δj+1 ), on obtient
J+1
12 1/2 p
  Z
12 X
q
E sup Ya ≤ √ (δj − δj+1 ) H(δj , A) ≤ √ H(u, A)du .
a∈A n n 0
j=1


On obtient donc   Z 1/2 p
24
E sup |Pnε (A)| ≤√ H(u, A)du
A∈A n 0
Or on peut montrer que
H(u, A) ≤ 2 V(A) log(e2 /u) ,
√
voir Haussler [12]. Ainsi, en utilisant l’inégalité de Jensen avec x 7→ x, on a
r s r
  Z 1/2
ε 2 V(A) (3 + log 2) V(A)
E sup |Pn (A)| ≤ 12 2 log(e2 /u)du = 24 ·
A∈A n 0 2n
Finalement, en revenant au résultat de la Proposition 6.4 et en utilisant la borne (6.1), on a,
avec probabilité au moins 1 − δ,
r s
2 log 1δ


∗ ∗ (3 + log 2) V(F)
R(fn ) − R(f ) ≤ 96 + ·
2n n

57
 Chapitre 7

Concentration de matrices

Dans ce chapitre, nous allons voir comment majorer P(kZk ≥ t), où Z est une matrice
symétrique réelle et où k · k correspond à la norme spectrale (dite aussi norme d’opérateur `2 ).

Rappelons d’abord quelques propriétés importantes de Sn l’ensemble des matrices symétriques

de Mn (R). Tout d’abord, si A ∈ Sn , alors A est diagonalisable dans une base orthogonale de
vecteurs propres. On notera
λ1 (A) ≥ · · · ≥ λn (A)
les n valeurs propres (réelles) de A, rangées par ordre décroissant. La norme spectrale de A est
alors donnée par
kAk = max{λ1 (A), −λn (A)} .
Une matrice A ∈ Sn est dite semi-définie positive si, pour tout u ∈ Rn , on a t uAu ≥ 0. De
façon équivalente, une matrice de Sn est semi-définie positive si toutes ses valeurs propres sont
positives ou nulles. De façon similaire, on dit qu’une matrice A ∈ Sn est dite définie positive si,
pour tout u ∈ Rn \ {0}, on a t uAu > 0, ce qui équivaut à dire que toutes les valeurs propres
de A sont strictement positives. On définit l’ordre partiel 4 sur Sn par A 4 B ssi B − A est
semi-définie positive. De même, on notera A ≺ B ssi B − A est définie positive. Une propriété
importante de l’ordre partiel 4 est la stabilité par conjugaison : si A 4 B, et si C est une matrice
à n lignes, alors t CAC 4 t CBC.

Remarquons aussi que si A < 0, alors λ1 (A) ≤ tr(A). De plus, si A, B ∈ Sn avec A 4 B, alors

∀i ∈ J1, nK , λi (A) ≤ λi (B) .

Ce dernier résultat est appelé le principe de monotonicité de Weyl et découle directement du

Théorème de Courant -Fisher :
t uAu t uBu
(7.1) λi (A) = max min t uu
≤ max min t uu
= λi (B) .
E, dim(E)=i u∈E E, dim(E)=i u∈E

Une façon naturelle d’étendre une fonction sur R à une fonction sur Sn est de l’appliquer aux
valeurs propres.

Définition 7.1. Soit f : I → R où I est un intervalle de R, et soit A ∈ Sn une matrice

symétrique dont toutes les valeurs propres λi appartiennent à I. Si
 
λ1
A = Q
 ..  −1
Q ,
.
λn
58
alors on définit la matrice f (A) par
 
f (λ1 )
f (A) = Q 
 ..  −1
Q .
.
f (λn )
(On peut vérifier que la définition de f (A) ne dépend pas de la décomposition spectrale A =
QΛQ−1 choisie.)

On peut ainsi définir l’exponentielle eA . De façon équivalente, eA est donnée par

+∞ q
X A
eA = I + ·
q!
q=1

Le logarithme log A peut être défini par la définition 7.1, ou bien de façon équivalente comme
l’inverse de l’exponentielle : pour tout A ∈ Sn , log eA = A.

Une conséquence de l’inégalité (7.1) est que si f est croissante sur I, alors
(7.2) A4B ⇒ tr f (A) ≤ tr f (B) .
Une fonction f est dite opérateur-monotone si elle vérifie la propriété plus forte :
(7.3) A4B ⇒ f (A) 4 f (B) .

Proposition 7.1. Le logarithme est opérateur-monotone.

Insistons sur le fait que l’exponentielle n’est pas opérateur-monotone.
Preuve de la Proposition 7.1. Remarquons déjà que pour tout a > 0, on a
Z +∞  
1 1
log a = − du .
0 1+u a+u
En effet, pour tout x > 0,
Z x 
1 1
− du = [log(1 + u) − log(a + u)]x0
0 1+u a+u
 
1+x
= log a + log
a+x
−→ log a .
t→+∞

Soit A ∈ Sn définie positive. En appliquant cette identité à toutes les valeurs propres de A, on a
Z +∞
(1 + u)−1 I − (A + uI)−1 du .


log A =
0

Montrons maintenant que si 0 ≺ A 4 B, et u ≥ 0, alors −(A + uI)−1 4 −(B + uI)−1 . Notons

Au = A + uI et Bu = B + uI. On a Au 4 Bu . Par la stabilité par conjugaison, on obtient
0 ≺ Bu−1/2 Au Bu−1/2 4 I .
Or, lorsqu’une matrice définie positive a toutes ses valeurs propres inférieures à 1, son inverse a
toutes ses valeurs propres supérieures à 1. Ainsi,
 −1
Bu−1/2 Au Bu−1/2 = Bu1/2 A−1 1/2
u Bu < I .

59
En appliquant à nouveau la stabilité par conjugaison, on a Bu−1 4 A−1 −1 −1
u , soit −Au 4 −Bu . En
appliquant cette inégalité dans la représentation intégrale du logarithme, on obtient log A 4 log B.

Énonçons enfin un dernier résultat, le théorème de Lieb. Pour la preuve, nous renvoyons au
chapitre 8 de Tropp [23].

Proposition 7.2. Soit H une matrice symétrique. L’application

A 7→ tr exp (H + log A)
est concave sur l’ensemble des matrices symétriques définies positives.

Nous sommes maintenant en mesure de montrer un équivalent de l’inégalité de Bernstein

pour les sommes de matrices symétriques indépendantes.

1. Une inégalité de Bernstein pour les sommes de matrices

Proposition 7.3. Soient X1 , . . . , XN des matrices n × n symétriques indépendantes telles que
EXi = 0 et kXi k ≤ K. Alors pour tout t ≥ 0,
N
! ( )
X t2
P Xi ≥ t ≤ 2n exp − Kt

,
i=1
2 σ2 + 3
PN
où σ 2 = 2
i=1 EXi .

Preuve de la Proposition 7.3. Notons S = N

P
i=1 Xi et λ1 (S) ≥ · · · ≥ λn (S) les valeurs propres de S
rangées par ordre décroissant. On a alors kSk = max{λ1 (S), −λn (S)}. Comme −λn (S) = λ1 (−S),
il suffit de montrer que
( )
t2
P (λ1 (S) ≥ t) ≤ n exp −
.
2 σ 2 + Kt3
On a, pour tout u ≥ 0,
P (λ1 (S) ≥ t) ≤ e−ut Eeuλ1 (S) = e−ut Eλ1 (euS ) ,
où la dernière inégalité vient du fait que euλ1 (S) = λ1 (euS ). Comme euS est définie positive,
toutes ses valeurs propres sont positives et l’on a λ1 (euS ) ≤ tr(euS ). À ce stade, on aimerait
pouvoir dire euS = N uXi , mais cette identité n’est pas vraie : une exponentielle de matrices
Q
i=1 e
ne transforme pas une somme en un produit. En revanche, on a l’inégalité suivante :
(N )
X
uS uXi
(7.4) E tr(e ) ≤ tr exp log Ee .
i=1
P −1
Cette inégalité découle du Théorème de Lieb 7.2 appliqué avec H = N i=1 uXi et A = e
uXN et

de l’inégalité de Jensen appliquée conditionnellement à X1 , . . . , XN −1 :

( N −1 )
X
uS uXN
 
E tr(e ) X1 , . . . , XN −1 ≤ tr exp u Xi + log Ee .
i=1
En prenant l’espérance conditionnelle sachant X1 , . . . , XN −2 , et en répétant le même argument, et
ainsi de suite, on obtient bien l’inégalité (7.4). On a ainsi réussi à passer de la fonction génératrice
60
des moments de S à celle des matrices Xi . Montrons maintenant que si X est une matrice n × n
symétrique avec EX = 0 et kXk ≤ K, alors pour tout 0 ≤ u < 3/K,
u2 EX 2
log EeuX 4
.
2 1 − uK
3

Tout d’abord, pour 0 ≤ u < 3/K et pour x tel que |x| ≤ K, on a

X (ux)k u2 x2 X uK k−2 u2 x2
 
ux
e = 1 + ux + ≤ 1 + ux + ≤ 1 + ux +
·
k≥2
k! 2
k≥2
3 2 1 − uK3

Comme toutes les valeurs propres de X sont contenues dans [−K, K], cela implique l’inégalité
matricielle
u2 X 2
(7.5) euX 4 I + uX +
,
2 1 − uK3

En prenant l’espérance dans (7.5), on a

u2 EX 2
EeuX 4 I +
.
2 1 − uK
3

En utilisant le fait que le logarithme est opérateur-monotone, puis l’inégalité log(1 + z) ≤ z pour
2 2
tout z ≥ 0 (appliquée à la matrice semi-définie positive 2 u1−EX ), on obtient bien
( uK 3 )
!
u2 EX 2 u2 EX 2
log EeuX 4 log I + 4
.
2 1 − uK 2 1 − uK


3 3

En revenant à (7.4), on a donc

( ) ( )
u2 N 2 2 u2
P
EX σ
E tr(euS ) ≤ tr exp i=1
i ≤ n exp
,
2 1 − uK
3 2 1 − uK 3

et ( ) ( )
σ 2 u2 σ 2 u2
P (λ1 (S) ≥ t) ≤ ne−ut exp = n exp −ut + .
2 1 − uK 2 1 − uK



3 3
t
En optimisant sur 0 ≤ u < 3/K, on voit que le membre de droit est minimal pour u = σ 2 +Kt/3
,
ce qui donne
( )
t2
P (λ1 (S) ≥ t) ≤ n exp −
.
2 σ 2 + Kt
3


2. Application : connexité du graphe d’Erdös-Renyi

Soit G ∼ G(n, p) un graphe aléatoire d’Erdös-Renyi sur n sommets et soit A sa matrice
d’adjacence, qui peut s’écrire
X
A= ξij (Eij + Eji ) ,
1≤i<j≤n

61
où (ξij )i<j est une suite i.i.d. de loi de Bernoulli B(p), et où (Eij )i,j est la base canonique de
Mn (R). Le Laplacien de G est la matrice ∆ = D − A, où D est la matrice diagonale des degrés
P
(Di,i = deg(i) = j Ai,j ). Cette matrice peut s’écrire
X
∆= ξij (Eii + Ejj − Eij − Eji ) .
1≤i<j≤n

La matrice ∆ est semi-définie positive et le vecteur 1 (toutes les coordonnées égales à 1) est
vecteur propre pour la valeur propre 0. Le spectre du Laplacien est intimement relié aux propriétés
géométriques de G. En particulier, le graphe G est connexe si et seulement si la deuxième plus
petite valeur de ∆ est strictement positive.

Pour simplifier le problème, nous allons d’abord former une matrice Z dont la plus petite
valeur propre correspond à la deuxième plus petite valeur propre de ∆. Pour cela, considérons la
matrice R ∈ Mn−1,n (R) d’une isométrie partielle de noyau Vect(1), i.e.
R t R = In−1 et R1 = 0 .
On définit alors la matrice Z ∈ Mn−1 (R) par
X
Z = R∆ t R = ξij R(Eii + Ejj − Eij − Eji ) t R .
1≤i<j≤n

L’espérance de Z se calcule facilement :

 
X
EZ = pR  (Eii + Ejj − Eij − Eji ) t R
1≤i<j≤n

= pR (n − 1)In − (1 t 1 − In ) t R

= pnIn−1 .
En particulier, λmin (EZ) = pn. Pour 1 ≤ i < j ≤ n, notons Xij = ξij R(Eii + Ejj − Eij − Eji ) t R,
P
de telle sorte que Z = i<j Xij . Les matrices Xij sont symétriques indépendantes, et, par stabilité
par conjugaison, elles restent semi-définies positives. De plus, le théorème de Courant-Fisher
implique que la plus petite valeur propre de Z, notée λmin (Z), correspond à la deuxième plus
petite valeur propre de ∆. Remarquons aussi que la norme spectrale de chaque matrice Xij est
inférieure à 2. En effet
kXij k ≤ |ξij |kRkkEii + Ejj − Eij − Eji kk t Rk .
Or |ξij | ≤ 1 (car ξij vaut 0 ou 1), kRk = k t Rk = 1 (car R est une isométrie partielle), et on peut
facilement voir que la norme de Eii + Ejj − Eij − Eji est inférieure à 2. Soit maintenant t > 0.
Pour tout u > 0, on a
 
P (λmin (Z) ≤ t) = P e−uλmin (Z) ≥ e−ut
h i
≤ eut E e−uλmin (Z)
h i
= eut E eλmax (−uZ)
= eut E λmax e−uZ



≤ eut E tr e−uZ ,



62
où l’on a utilisé la croissance de l’exponentielle et le fait que e−uZ est définie positive. En utilisant
à plusieurs reprises le théorème de Lieb et l’inégalité de Jensen conditionnelle comme dans la
preuve de la Proposition 7.3, on obtient
 
 X 
−uZ −uXij

  
E tr e ≤ tr exp log E e .
 
1≤i<j≤n

Par convexité de x 7→ e−ux , on a, pour tout x ∈ [0, 2],

e−2u − 1
e−ux ≤ 1 + x.
2
Comme les valeurs propres de Xij sont comprises dans [0, 2], on obtient l’inégalité matricielle :
e−2u − 1
e−uXij 4 I + Xij .
2
En prenant l’espérance, en utilisant que le logarithme est opérateur-monotone puis en appliquant
matriciellement l’inégalité log(1 + z) ≤ z, on obtient
e−2u − 1 e−2u − 1
 
 −uX 
log E e ij
4 log I + E[Xij ] 4 E[Xij ] .
2 2
Et en sommant sur i < j et en prenant la trace de l’exponentielle, on obtient
 −2u   −2u 
 −uZ

 e −1 e −1
E tr e ≤ tr exp E[Z] = (n − 1) exp np .
2 2
Ainsi,
e−2u − 1
  
P (λmin (Z) ≤ t) ≤ n exp inf ut + np .
u>0 2
L’infimum est atteint pour u = 12 log np


t . Pour t = εnp avec ε > 0, on obtient
np
P (λmin (Z) ≤ εnp) ≤ ne− 2
(1−ε+ε log(ε))
.
2(1+δ) log n
On voit que pour p > n avec δ > 0, en prenant ε assez petit, la probabilité de G ne soit
pas connexe tend vers 0. Cette borne est presque optimale, à un facteur 2 : on peut montrer que si
p > (1+δ)nlog n , alors G est connexe avec grande probabilité, et inversement, que si p < (1−δ)nlog n ,
alors G contient des sommets isolées avec grande probabilité.

63
 Chapitre 8

Concentration sans indépendance

1. Concentration pour les chaı̂nes de Markov

Soit (Xt )t∈N une chaı̂ne de Markov sur un espace d’état Ω fini, de matrice de transition P .
On sait que si la chaı̂ne est ergodique au sens où

∃t ∈ N , ∀x, y ∈ Ω , P t (x, y) > 0 ,

alors il existe une unique probabilité stationnaire π et la chaı̂ne converge vers π en variation
totale :
max dtv P t (x, ·), π −→ 0 .


x∈Ω t→+∞

Notons D(t) = maxx∈Ω dtv P t (x, ·), π . Le temps de mélange est défini pour ε ∈]0, 1[, par

tmix (ε) = min {t ∈ N , D(t) ≤ ε} .

Définissons aussi
D(t) = max dtv P t (x, ·), P t (y, ·) ,


x,y∈Ω

et τ (ε) = min t ∈ N , D(t) ≤ ε . On montre facilement que D(t) ≤ D(t) ≤ 2D(t), ce qui im-
plique tmix (ε) ≤ τ (ε) ≤ tmix (ε/2).

Soit f : Ωn → R une fonction telle que pour tout x, y ∈ Ωn ,

n
ci 1xi 6=yi ,
X
f (y) − f (x) ≤
i=1

avec c1 , . . . , cn ≥ 0, et soit Z = f (X1 , . . . , Xn ). Nous allons montrer que pour tout t ≥ 0, et pour
tout ε ∈]0, 1[,
 
2
 
 t 
P (Z − EZ ≥ t) ≤ exp −  2 .
 2 2−ε τ (ε) Pn c2 
 
1−ε i=1 i

(Pour des raffinements de cette inégalité et des extensions à des suites dépendantes plus générales
que des chaı̂nes de Markov, voir par exemple Samson et al. [22], Kontorovich [14], Paulin et al.
[19].)
L’idée va être de décomposer la suite (X1 , . . . , Xn ) en blocs de longueur τ (ε) et de considérer
la martingale de Doob associée à la filtration engendrée pas ces blocs. Pour cela, écrivons
64
n = p.τ (ε) + s, avec p ≥ 0 et s ∈ J0, τ (ε) − 1K, et posons


Y1 = X1 , . . . , Xτ (ε) ,
..
.


Yp = X(p−1)τ (ε)+1 , . . . , Xpτ (ε) ,


Yp+1 = Xpτ (ε)+1 , . . . , Xn .
Pour k ∈ J1, pK, on pose Ck = c(k−1)τ (ε)+1 + · · · + ckτ (ε) et Cp+1 = cpτ (ε)+1 + · · · + cn . Remarquons
que pour tout k ∈ J1, p + 1K, et pour tout y1k = (y1 , . . . , yk ), on a
h i h i h i h i
k−1 0
E Z Y1k = y1k − E Z Y1k−1 = y1k−1 ≤ max 0
E Z Y 1
k
= y k−1
1 z − E Z Y1
k
= y 1 z .
z,z

En utilisant la définition de τ (ε) et la caractérisation de la distance en variation totale par

couplage, ainsi que l’hypothèse sur la fonction f , on obtient, pour k ∈ J1, pK,
h i h i
E Z Y1k = y1k−1 z − E Z Y1k = y1k−1 z 0 ≤ Ck + Ck+1 + εCk+2 + · · · + εp−k Cp+1 ,
et
h i h i
E Z Y1p+1 = y1p z − E Z Y1p+1 = y1p z 0 ≤ Cp+1 .

En notant ∆ la matrice triangulaire supérieure donnée par

εp−1
 
1 1 ε ... ...
 1 1
 ε ... εp−2 

 .. .. 
 . . 
∆= 
.. ..


 . . 
 
 1 1 
1
et C le vecteur C = (C1 , . . . , Cp+1 ), on a, pour tout k ∈ J1, p + 1K,
E[Z Fk ] − E[Z Fk−1 ] ≤ (∆C)k ,
où Fk = σ(Y1 , . . . , Yk ). Par l’inégalité d’Azuma-Hoeffding, on obtient
( )
t2
P (Z − EZ ≥ t) ≤ exp − Pp+1 .
2 k=1 (∆C)2k
Pour conclure, notons que
p+1
X
(∆C)2k = k∆Ck2 ≤ k∆k2 kCk2 .
k=1

D’une part
1 2−ε
k∆k ≤ 1 + 1 + ε + · · · + εp−1 ≤ 1 + = ·
1−ε 1−ε
D’autre part, par l’inégalité de Cauchy-Schwarz,
n
X
2
kCk ≤ τ (ε) c2i .
i=1
65
 2. Concentration avec dépendance négative
2.1. Association négative.

Définition 8.1. Une suite (Xn )n≥1 de variables aléatoires réelles est dite négativement associée
(NA) si pour tous sous ensembles finis disjoints A, B ⊂ N∗ , et pour toutes fonctions f : R|A| → R
et g : R|B| → R, croissantes coordonnée par coordonnée, on a
E [f (XA )g(XB )] ≤ E [f (XA )] E [g(XB )]

Une conséquence importante de l’association négative (NA) est que toutes les bornes de
concentration issues de la méthode de Chernoff pour les sommes de variables indépendantes
s’appliquent automatiquement aux sommes de variables négativement associées. En effet, si
X1 , . . . , Xn sont négativement associées, alors, pour tout λ ∈ R, on a
h Pn i Y n h i
E eλ i=1 Xi ≤ E eλXi .
i=1

Énonçons deux propriétés simples mais très utiles de l’association négative :

(1) Si X = (X1 , . . . , Xn ) est NA, si Y = (Y1 , . . . , Ym ) est NA, et si X et Y sont indépendantes,
alors (X, Y ) est NA.
(2) Si X = (X1 , . . . , Xn ) est NA, si A1 , . . . , Ak sont des sous-ensembles disjoints de
J1, nK, et si h1 , . . . , hk sont des fonctions réelles croissantes définies respectivement
sur R|A1 | , . . . , R|Ak | , alors la suite (h1 (XA1 ), . . . , hk (XAk )) est NA.

Exemple 8.1 (Bins and balls). Reprenons l’exemple de variables aléatoires X1 , . . . , Xn i.i.d.
de loi (pj )j≥1 sur N∗ . Remarquons que pour tout i ∈ J1, nK, la suite (1Xi =j )j≥1 est NA. Cela
provient d’un résultat plus général : si (Zj )j≥1 est une suite de variables à valeurs dans {0, 1}
telle que j≥1 Zj = 1, alors (Zj )j≥1 est NA. En effet, soient A, B ⊂ N∗ finis disjoints, et soient
P

f et g des fonctions réelles croissantes définies respectivement sur {0, 1}|A| et {0, 1}|B| . Sans
perte de généralité, on peut supposer que f (0, . . . , 0) = 0 et que g(0, . . . , 0) = 0. Dans ce cas,
E[f (ZA )] ≥ 0 et E[g(ZB )] ≥ 0. Mais comme au plus une variable Zj , pour j ∈ A ∪ B, vaut 1, on
a nécessairement E[f (ZA )g(ZB )] = 0. Maintenant, par la propriété (1), la suite (1Xi =j )j≥1,1≤i≤n
est NA. Et par la propriété (2), la suite (Nj )j≥1 avec
n
1Xi =j ,
X
Nj =
i=1

est NA. Rappelons que Kn = j≥1 1Nj >0 correspond au nombre de symboles distincts. Encore
P

par la propriété (2), la suite (1Nj >0 )j≥1 est NA. Ainsi, en utilisant l’inégalité de Bennett, on
obtient, pour tout λ ∈ R,
λ(1 −E1Nj >0 )
h i X h i
log E eλ(Kn −EKn ) ≤ log E e Nj >0
j≥1

Var(1Nj >0 )φ(λ) .

X
≤
j≥1

Par l’inégalité d’Efron-Stein, on obtient Var(1Nj >0 ) ≤ E[1Nj =1 ]. Ainsi

h i
log E eλ(Kn −EKn ) ≤ E[Kn,1 ]φ(λ) ,
66
 1Nj =1 est le nombre de symboles apparaissant une seule fois dans l’échantillon.
P
où Kn,1 = j≥1

2.2. Propriété de recouvrement stochastique.

Définition 8.2. Une mesure µ sur {0, 1}n est dite k-homogène (k ∈ J1, nK) si son support est
inclus dans
n
( )
X
x ∈ {0, 1}n , xi = k .
i=1

Pour x, y ∈ {0, 1}n , on note x ≥ y si pour tout i ∈ J1, nK, xi ≥ yi . De plus, on dit que x
recouvre y, et l’on note x  y, si x et y coı̈ncident sur toutes les coordonnées sauf sur au plus
une pour laquelle xi = 1 et yi = 0.

Définition 8.3. Soient µ et ν deux mesures sur {0, 1}n . On dit que µ domine stochastiquement
ν si pour tout sous-ensemble A ⊂ {0, 1}n croissant (i.e. fermé supérieurement), on a µ(A) ≥ ν(A).
De façon équivalente, on peut coupler µ et ν de telle sorte que le support soit inclus dans
{(x, y), x ≥ y}.

Définition 8.4. Soient µ et ν deux mesures sur {0, 1}n . On dit que µ recouvre stochastiquement
ν (et l’on note µ  ν) si l’on peut coupler µ et ν de telle sorte que le support soit inclus dans
{(x, y), x  y}.

Définition 8.5. Soit µ une mesure de probabilité sur {0, 1}n . On dit que µ possède la propriété
de recouvrement stochastique (SCP) si pour tout S ⊂ J1, nK, et pour tous x, y ∈ {0, 1}|S| , avec
x  y, on a



µ · XS = y  µ · XS = x ,


où µ · XS = x correspond à la loi conditionnelle de XS c sachant {XS = x}.

Donnons quelques exemples de mesures possédant la SCP :

• mesures déterminantales : une mesure de probabilité µ sur {0, 1}n est dite déterminantale
s’il existe une matrice hermitienne K ∈ Mn (C) telle que, pour tout S ⊂ J1, nK,
Y
E Xj = det KS ,
j∈S

où X ∼ µ et où KS correspond à la matrice obtenue en ne retenant que les lignes

et les colonnes d’indice appartenant à S. Borcea et al. [2] ont montré que de telles
mesures possédaient la SCP (en fait, ils montrent qu’elles vérifient une propriété plus
forte appelée propriété de Rayleigh forte).Un exemple de mesure déterminantale est celle
des arbres couvrants aléatoires. Soit G = (V, E) un graphe fini connexe, dont les arêtes
sont numérotées de 1 à n. Un arbre couvrant est un sous-ensemble de E, sans cycle et qui
connecte tous les sommets. On peut tirer un arbre couvrant aléatoirement de la façon
suivante : soit ω(e) ≥ 0 le poids de l’arête e, et µ la probabilité sur les arbres couvrants
telles que µ(T ) ∝ e∈T ω(e). Vue comme une mesure sur {0, 1}n (Xe = 1 ssi e ∈ T ), c’est
Q

une mesure déterminantale (voir Burton and Pemantle [4] et Lyons [16]).
• mesures sur l’ensemble des bases d’un matroı̈de : soit E un ensemble fini non-vide et B
une collection non-vide de parties de E de même cardinal. La paire (E, B) est appelée un
matroı̈de si elle vérifie la propriété :
∀A, B ∈ B , ∀ ∈ A \ B , ∃b ∈ B \ A , A ∪ {b} \ {a} ∈ B .
67
 L’ensemble B alors appelé l’ensemble des bases du matroı̈de et le cardinal des bases est
appelé le rang. Si E est l’ensemble d’arêtes d’un graphe G fini connexe, et B l’ensemble des
arbres couvrants de G, alors la paire (E, B) est un matroı̈de. Il est naturel de munir B de
la mesure uniforme. Plus généralement, pour une suite (ω(e))e∈E de poids positifs, on peut
Q
définir la mesure de probabilité pondérée µω telle que pour tout A ∈ B, µω (A) ∝ e∈A ω(e).
Si |E| = n, ces mesures peuvent être vues comme des mesures sur {0, 1}n (en identifiant
E avec J1, nK et une partie A ∼ µω au vecteur X = (Xe )e∈E avec Xe = 1e∈A ). Pour des
matroı̈des généraux, il est possible d’avoir E[Xe Xf ] > E[Xe ]E[Xf ]. Si pour tous e, f ∈ E,
on a E[Xe Xf ] ≤ E[Xe ]E[Xf ], on dit que la matroı̈de a la propriété de corrélation négative.
Une notion plus forte est celle de matroı̈de équilibré. Les mineurs d’un matroı̈de sont tous
les matroı̈des qui peuvent être obtenus en répétant l’opération de choisir un élément e et
de ne garder soit que les bases qui contiennent e, soit celles qui ne le contiennent pas. On
dit qu’un matroı̈de est équilibré si tous ses mineurs (dont lui-même) ont la propriété de
corrélation négative. Feder and Mihail [9] ont montré que les mesures µω sur l’ensemble
des bases d’un matroı̈de équilibré possèdent la SCP.
• Bernoulli indépendantes conditionnées à leur somme : soit k ∈ J0, nK et λ1 , . . . , λn > 0.
La mesure sur {0, 1}n donnée par
λxi 1kxk=k
Qn
∀x ∈ {0, 1} , µ(x) = P i=1 i Qn
n
yj
y, kyk=k j=1 λj

possède la SCP. En fait, il s’agit d’un cas particulier de mesure pondérée sur l’ensemble
des bases d’un matroı̈de (E = J1, nK et B l’ensemble des parties de E de cardinal k, et
ω(i) = λi ). Remarquons aussi qu’il s’agit
 de la loi de (X1 , . . . , Xn ) où les variables Xi
λi
sont indépendantes, et Xi ∼ B 1+λi .
Le résultat suivant est dû à Pemantle and Peres [20].

Proposition 8.1. Soit µ une mesure de probabilité sur {0, 1}n , k-homogène et possédant la SCP,
et soit (X1 , . . . , Xn ) ∼ µ. Soit f : {0, 1}n → R une fonction 1-lipschitzienne et Z = f (X1 , . . . , Xn ).
Alors, pour tout t ≥ 0,
 2
t
P (Z − EZ ≥ t) ≤ exp − .
8k

Preuve de la Proposition 8.1. À X = (X1 , . . . , Xn ), on associe le vecteur Y = (Y1 , . . . , Yk ) donc

la loi est donnée séquentiellement par : pour tout j ∈ J1, kK, pour tout i ∈ J1, nK,

P Yj = i Y1 , . . . , Yj−1 = P Xi = 1 XY1 = · · · = XYj−1 = 1 1i6=Y1 ,...,Yj−1 .

Le vecteur Y donne l’emplacement des 1 dans le vecteur X, dans un ordre échangeable. Soit
g telle que f (X) = g(Y ). Remarquons que la fonction g est 2-lipschitzienne. Considérons la
martingale de Doob
Mj = E[g(Y ) Fj ] − E[g(Y )] ,
associée à la filtration Fj engendrée par Y1 , . . . , Yj . Pour 1 ≤ j ≤ k − 1, et y1 , . . . , yj+1 ∈ J1, nK
tels que P(Y1 = y1 , . . . , Yj+1 = yj+1 ) > 0, on a, en notant Ej l’événement {Y1 = y1 , . . . , Yj = yj },
   
E g(Y ) Ej , Yj+1 = yj+1 − E g(Y ) Ej

    
= P Yj+1 6= yj+1 Ej E g(Y ) Ej , Yj+1 = yj+1 − E g(Y ) Ej , Yj+1 6= yj+1 .

68
Par la SCP, la différence entre les deux espérances conditionnelles ci-dessus est comprise entre
−2 et 2. Ainsi, en appliquant l’inégalité d’Azuma–Hoeffding 3.1, on a
2t2
   2
t
P (Z − EZ ≥ t) ≤ exp − 2 = exp − .
4 k 8k


3. Paires échangeables
Dans cette section, nous introduisons une méthode développée par Chatterjee pour obtenir
de la concentration en l’absence d’indépendance. Cette méthode repose sur la notion de paires
échangeables, et correspond à une variante de la méthode de Stein. La méthode de Stein est une
technique élégante et puissante pour démontrer des approximations distributionnelles. Pour des
introductions à cette méthode, voir Barbour and Chen [1], Ross [21], et Chatterjee [6].

Soit (X, X 0 ) une paire échangeable de variables aléatoires à valeurs dans un ensemble X , i.e.
telle que (X, X 0 ) ∼ (X 0 , X). Soit f : X → R une fonction mesurable telle que Ef (X) = 0, et soit
F : X × X → R une fonction mesurable antisymétrique (i.e. f (x, x0 ) = −f (x0 , x)) et telle que
E F (X, X 0 ) X = f (X) .
 

On suppose pour commencer que F est donnée, mais on verra comment on peut trouver une
telle fonction F à partir de f . Notons déjà un cas particulier où l’on peut facilement trouver une
telle fonction : pour 0 < a ≤ 1, une a-paire de Stein est une paire échangeable (X, X 0 ) vérifiant
E[X 0 X] = (1 − a)X. Si (f (X), f (X 0 )) est une a-paire de Stein, alors on vérifie facilement que
(x0 )
la fonction antisymétrique F donnée par F (x, x0 ) = f (x)−fa convient.

Remarquons que pour toute fonction mesurable h : X → R telle que E |h(X)F (X, X 0 )| < ∞,
on a
1 
E [f (X)h(X)] = E h(X) − h(X 0 ) F (X, X 0 ) .


(8.1)
2
En effet, on a E [f (X)h(X)] = E [h(X)F (X, X 0 )], et, par échangeabilité de (X, X 0 ) et antisymétrie
de F , on a
E h(X)F (X, X 0 ) = E h(X 0 )F (X 0 , X) = −E h(X 0 )F (X, X 0 ) .
     

En particulier, en prenant h = f , on obtient

 1 
Var (f (X)) = E f (X)2 = E f (X) − f (X 0 ) F (X, X 0 ) .


2
Pour x ∈ X , on définit
1 
v(x) = E f (X) − f (X 0 ) F (X, X 0 ) X = x .


2
Le théorème ci-dessous est dû à Chatterjee [5].

Proposition 8.2. Soit (X, X 0 ) une paire échangeable,

 λfet(X)soient f , 0F , v les fonctions définies
ci-dessus. On suppose que pour tout λ ∈ R, on a E e |F (X, X )| < ∞. Supposons qu’il
existe b, c ≥ 0 tels que pour tout x ∈ X ,
v(x) ≤ bf (x) + c .
69
Alors, pour tout t > 0,
t2 t2
   
P (f (X) > t) ≤ exp − et P (f (X) < −t) ≤ exp − .
2(c + bt) 2c

Preuve de la Proposition 8.2. Notons m(λ) = E eλf (X) . En utilisant (8.1), on a, pour tout
 

λ ∈ R,
h i 1 h 0
 i
m0 (λ) = E f (X)eλf (X) = E eλf (X) − eλf (X ) F (X, X 0 )
2
−e x y x y
Par convexité de l’exponentielle, on a pour tous x = 6 y, ex−y ≤ e +e2 . On obtient ainsi, en
0
utilisant à nouveau l’échangeabilité de (X, X ), puis l’hypothèse sur v,
|λ| h λf (X) 0
 i
|m0 (λ)| ≤ + eλf (X ) f (X) − f (X 0 ) F (X, X 0 )


E e
4 h i
= |λ|E eλf (X) v(X)
h i
≤ |λ|E eλf (X) (bf (X) + c)
= |λ| bm0 (λ) + cm(λ) .

m0 (λ)
Comme λ 7→ m0 (λ) est convexe avec m0 (0) = 0, on a λ ≥ 0. Pour 0 < λ < 1/b, on obtient

m0 (λ) λc
≤ ,
m(λ) 1 − λb
et
θ
cθ2
Z
cu
log m(θ) ≤ du ≤ ·
0 1 − bu 2(1 − bθ)
 
t2
La méthode de Chernoff donne alors que pour tout t > 0, P(f (X) > t) ≤ exp − 2(c+bt) . Pour
0
cλ2
λ < 0, on a m (λ)
m(λ) ≥ λc, donc par intégration log m(λ) ≤ 2 et la méthode de Chernoff permet
de conclure. 

Application : poids d’une permutation. Soit A = (ai,j )1≤i,j≤n une matrice réelle et soit
π une permutation aléatoire de {1, . . . , n}, uniformément distribuée. On s’intéresse au poids de
la permutation π défini comme
Xn
Z= ai,π(i) .
i=1

Par exemple, si A est la matrice identité, la variable X correspond au nombre de points fixes.
Ou bien si ai,j = vj 1{i≤k} , X correspond à la somme des valeurs d’un échantillon de taille k tiré
sans remise dans une population de taille n. Ou encore si ai,j = |i − j|, il s’agit de la distance de
Spearman entre π et l’identité.

Proposition 8.3. Supposons que les poids ai,j appartiennent tous à [0, 1], et soit Z = ni=1 ai,π(i)
P

où π est une permutation uniforme. Alors pour tout t ≥ 0,

t2 t2
   
P (Z − EZ ≥ t) ≤ exp − et P (Z − EZ ≤ −t) ≤ exp − .
4EZ + 2t 4EZ
70
Preuve de la Proposition 8.3. Soit π une permutation uniforme de {1, . . . , n} et I, J deux entiers
tirés uniformément et indépendamment dans {1, . . . , n}. Soit π 0 = π ◦ (I, J) la permutation
obtenue à partir de π en transposant I et J. Notons
n n n n
X 1 X 0
X 1 X
W = ai,π(i) − ai,j et W = ai,π0 (i) − ai,j .
n n
i=1 i,j=1 i=1 i,j=1

La paire (W, W 0 ) est clairement échangeable et l’on a

E W 0 − W π = E aI,π(J) + aJ,π(I) − aI,π(I) − aJ,π(J) π
   
 
n
1 X 1 X
= 2 2 ai,π(j) − ai,π(i) 
n n
i,j i=1
2
=− W.
n
0 2
Ainsi (W, W ) est une n -paire de Stein. De plus, en utilisant que 0 ≤ ai,j ≤ 1,
h
2 i
E (W 0 − W )2 π = E aI,π(J) + aJ,π(I) − aI,π(I) − aJ,π(J)
 
π
1 X
2
= 2 ai,π(j) + aj,π(i) − ai,π(i) − aj,π(j)
n
i,j
2 X

≤ 2 ai,π(j) + aj,π(i) + ai,π(i) + aj,π(j)
n
i,j
4(Z + EZ) 4W 8EZ
= = + ·
n n n
W −W 0
Ainsi, en appliquant la Proposition 8.2 avec F (W, W 0 ) = 2/n , b = 1 et c = 2EZ, on obtient
bien le résultat voulu. 

Magnétisation dans le modèle de Curie–Weiss. Soit β ∈ R+ et h ∈ R. Le modèle de

Curie–Weiss avec interactions ferromagnétiques à température inverse β et champ externe h est
donné par la mesure de probabilité µ sur {−1, 1}n définie par
 
n
1  β X X 
µ(σ) = exp σi σj + βh σi ,
Z n 
i<j i=1

où Z est la constante de normalisation. La magnétisation d’une configuration σ est définie comme
n
1X
m(σ) = σi .
n
i=1
Pour n grand et σ distribuée selon µ, la magnétisation satisfait
m(σ) ≈ tanh (βm(σ) + βh) .
Cette équation a une seule solution pour β sous une certaine valeur critique, et plusieurs solutions
pour β au-dessus.

Proposition 8.4. Pour tout β ≥ 0, pour tout h ∈ R, et pour tout t ≥ 0,

t2
   
β t
P |m(σ) − tanh (βm(σ) + βh)| ≥ + √ ≤ 2 exp − .
n n 4(1 + β)
71
Preuve de la Proposition 8.4. Soit σ ∼ µ et σ 0 obtenue en choisissant une coordonnée I ∈ J1, nK
uniformément au hasard, et en remplaçant σI par un élément distribué selon la loi conditionnelle
de la I ième coordonnée sachant toutes les autres. On vérifie facilement que la paire (σ, σ 0 ) est
échangeable. Soit
Xn
0
F (σ, σ ) = (σi − σi0 ) ,
i=1
et
1X
mi (σ) = σj .
n
j6=i
On a

exp (βmi (σ) + βh)
P σi = 1 σj , j 6= i = ·
exp (βmi (σ) + βh) + exp (−βmi (σ) − βh)
Ainsi  
E σi σj , j 6= i = tanh (βmi (σ) + βh) ,
et
f (σ) = E F (σ, σ 0 ) σ
 

n
1X  

= σi − E σi σj , j 6= i
n
i=1
n
1X
= m(σ) − tanh (βmi (σ) + βh) .
n
i=1
Comme σ et ne diffèrent qu’en au plus une coordonnée, on a |F (σ, σ 0 )| ≤ 2, et |m(σ)−m(σ 0 )| ≤
σ0
2
n . En utilisant le fait que la fonction x 7→ tanh(x) est 1-lipschitzienne, on a
n
βX 2(1 + β)
f (σ) − f (σ 0 ) ≤ m(σ) − m(σ 0 ) + mi (σ) − mi (σ 0 ) ≤ ·
n n
i=1
2(1+β)
Ainsi v(σ) ≤ n et la Proposition 8.2 appliquée avec b = 0 et c = 2(1+β)
n donne
n
!
t2
 
1X t
P m(σ) − tanh (βmi (σ) + βh) ≥ √ ≤ 2 exp − .
n n 4(1 + β)
i=1
Pour conclure, il suffit d’utiliser à nouveau le fait que x 7→ tanh(x) est 1-lipschitzienne :
n n
1X βX β
tanh (βmi (σ) + βh) − tanh (βm(σ) + βh) ≤ |m(σ) − mi (σ)| ≤ ·
n n n
i=1 i=1


72
 Bibliographie

[1] A. D. Barbour and L. H. Chen. Steins (magic) method. arXiv preprint arXiv :1411.1179,
2014.
[2] J. Borcea, P. Brändén, and T. Liggett. Negative dependence and the geometry of polynomials.
Journal of the American Mathematical Society, 22(2) :521–567, 2009.
[3] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University
Press, Oxford, 2013.
[4] R. Burton and R. Pemantle. Local characteristics, entropy and limit theorems for spanning
trees and domino tilings via transfer-impedances. The Annals of Probability, pages 1329–1371,
1993.
[5] S. Chatterjee. Stein’s method for concentration inequalities. Probability theory and related
fields, 138(1) :305–321, 2007.
[6] S. Chatterjee. A short survey of stein’s method. arXiv preprint arXiv :1404.1392, 2014.
[7] L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition, volume 31.
Springer Science & Business Media, 2013.
[8] D. P. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized
algorithms. Cambridge University Press, 2009.
[9] T. Feder and M. Mihail. Balanced matroids. In Proceedings of the twenty-fourth annual
ACM symposium on Theory of computing, pages 26–38, 1992.
[10] D. A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages
100–118, 1975.
[11] D. A. Grable. A large deviation inequality for functions of independent, multi-way choices.
Combinatorics, probability and Computing, 7(1) :57–63, 1998.
[12] D. Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded
vapnik-chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2) :217–232,
1995.
[13] J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. Citeseer,
1989.
[14] L. Kontorovich. Measure concentration of strongly mixing processes with applications. PhD
thesis, Carnegie Mellon University, School of Computer Science, Machine Learning ?, 2007.
[15] M. Ledoux. The concentration of measure phenomenon. Number 89. American Mathematical
Soc., 2001.
[16] R. Lyons. Determinantal probability measures. Publications Mathématiques de l’IHÉS, 98 :
167–212, 2003.
[17] P. Massart. The tight constant in the dvoretzky-kiefer-wolfowitz inequality. The annals of
Probability, pages 1269–1283, 1990.
[18] C. McDiarmid. Concentration. In Probabilistic methods for algorithmic discrete mathematics,
pages 195–248. Springer, 1998.

73
[19] D. Paulin et al. Concentration inequalities for markov chains by marton couplings and
spectral methods. Electronic Journal of Probability, 20, 2015.
[20] R. Pemantle and Y. Peres. Concentration of Lipschitz functionals of determinantal and
other strong Rayleigh measures. Combinatorics, Probability and Computing, 23(1) :140–160,
2014.
[21] N. Ross. Fundamentals of Stein’s method. Probab. Surv, 8 :210–293, 2011.
[22] P.-M. Samson et al. Concentration of measure inequalities for markov chains and \phi-mixing
processes. The Annals of Probability, 28(1) :416–461, 2000.
[23] J. A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends R
in Machine Learning, 8(1-2) :1–230, 2015.
[24] J. A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends R
in Machine Learning, 8(1-2) :1–230, 2015.
[25] R. Vershynin. High-dimensional probability : An introduction with applications in data
science, volume 47. Cambridge university press, 2018.

74