Scribd
Importer
222 vues2 pages

Inegalite de Hoeffding

Ce document présente le théorème d'inégalité de Hoeffding et ses applications. Il démontre que la probabilité que la somme de variables aléatoires centrées dépasse un seuil décroit exponentiellement avec la taille de l'échantillon. Le document contient également des lemmes sur les moments générateurs de variables aléatoires.

Transféré par

Be Good
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
222 vues2 pages

Inegalite de Hoeffding

Ce document présente le théorème d'inégalité de Hoeffding et ses applications. Il démontre que la probabilité que la somme de variables aléatoires centrées dépasse un seuil décroit exponentiellement avec la taille de l'échantillon. Le document contient également des lemmes sur les moments générateurs de variables aléatoires.

Transféré par

Be Good
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Inégalité de Hoeffding

Leçons : 253, 260, 262

On se place dans (Ω, F , P) un espace probabilisé.


Théorème 1
Soit (X n )n suite de variables aléatoires centrées telles que |X n | ¶ cn presque sûrement.
n n
Soit an = c 2j et Sn = X j . Alors si " > 0,
P P
j=1 j=1
−" 2
 ‹
P(|Sn | > ") ¶ 2 exp
2an

Lemme 2
Soit X variable aléatoire centrée telle que |X | ¶ 1 presque sûrement. Alors L X (t) =
t2
E[e t X ] ¶ e 2 .
1− x 1+ x
Démonstration. Si t ∈ R et x ∈ [−1, 1] alors t x = × (−t) + × t donc par
2 2
1 − x −t 1 + x t
convexité de la fonction exp, e t x ¶ e + e.
2 2
• Appliquant ce •résultat˜ à e , on obtient, comme |X | ¶ 1 presque sûrement, L X (t) ¶
tX

1 − X −t 1+X t
˜
E e +E e = ch(t) car X est centrée.
2 2
+∞
P t 2n +∞
P t 2n t2
Enfin, ch(t) = ¶ = e 2 car (2n)! = n! × (n + 1) × · · · × (2n) ¾ 2 n n!

n=0 (2n)!
n
n=0 2 n!

Xj
Démonstration (du théorème). Par indépendance des X j , on a en remarquant que vérifie
cj
les conditions du lemme,

t 2 c 2j
n n n
‚ Œ  
Y Y Y t 2 an
∀t ∈ R, LSn (t) = L X j (t) = L X j (t c j ) ¶ exp = exp
j=1 j=1
cj
i=1
2 2

Soit " > 0. Selon l’inégalité de Markov,


 
E e tSn
 
t 2 an
P(Sn > ") = P(e tSn
>e )¶
t"
¶ exp − t"
e t" 2
t 2 an
Or si ϕ : t 7→ −t", c’est une fonction polynômiale de degré 2 de coefficient dominant
2
"
positif et ϕ 0 (t) = t an − " donc ϕ atteint son minimum en .
an
" n "
 2 2
  2‹
a −"
Ainsi, P(Sn > ") ¶ exp 2 − = exp .
an 2 an 2an
En appliquant ce résultat à −Sn , on obtient 
−" 2
‹
P(|Sn | > ") ¶ P(Sn > ") + P(Sn < −") ¶ 2 exp , ce qu’il fallait démontrer.
2an

Gabriel LEPETIT 1 ENS Rennes - Université Rennes 1


Proposition 3
On suppose de plus qu’il existe α, β > 0 tels que 2α − β > 0 et an ¶ n2α−β pour tout
Sn
n ∈ N. Alors presque sûrement α tend vers 0.
n
 2 2α ‹  2 β
−" n −" n
Démonstration. Selon le théorème précédent, P(|Sn | ¾ "nα ) ¶ exp ¶ exp ,
2an 2
ce dernier terme étant le terme général positif d’une série convergente (par exemple parce
1
que il est négligeable devant 2 ).
n
Sn
Donc, selon le lemme de Borel-Cantelli, α converge presque sûrement.
n

Référence : Jean-Yves OUVRARD (2009). Probabilités (Master Agrégation). T. 2. Cassini,


p. 210

Gabriel LEPETIT 2 ENS Rennes - Université Rennes 1

Vous aimerez peut-être aussi