Leçon 313 — Inégalités de concentration. Markov, Tchebychev, Hoeffding.

Points clés

• Inégalité de Markov et Tchebychev
• Inégalité de Hoeffding
• Méthode de Chernoff (borne exponentielle)
• Inégalité de McDiarmid
• Applications : bornes de déviation

Plan

1. Inégalités élémentaires
   • Inégalité de Markov : [formule] pour [formule]
   • Inégalité de Bienaymé-Tchebychev : [formule]
   • Inégalité de Jensen : [formule] pour [formule] convexe
2. Méthode de Chernoff
   • Principe : [formule] puis optimiser en [formule]
   • Transformée de Laplace [formule] : propriétés de convexité
   • Borne de Chernoff pour les variables de Bernoulli : [formule]
3. Inégalité de Hoeffding
   • Lemme de Hoeffding : si [formule] et [formule], alors [formule]
   • Théorème de Hoeffding : [formule]
   • Borne bilatérale : [formule]
4. Inégalité de McDiarmid
   • Condition des différences bornées : [formule]
   • Énoncé : [formule]
   • Généralisation de Hoeffding aux fonctions de variables indépendantes
5. Inégalités sous-gaussiennes
   • Variable sous-gaussienne : [formule] pour tout [formule]
   • Exemples : variable bornée, variable gaussienne
   • Somme de sous-gaussiennes indépendantes : contrôle exponentiel
6. Applications
   • Bornes de déviation pour les sondages : [formule]
   • Apprentissage statistique : bornes de généralisation PAC
   • Concentration de la norme d'un vecteur gaussien

Théorèmes clés

• Inégalité de Hoeffding : si [formule] sont indépendantes avec [formule], alors [formule]
• Inégalité de McDiarmid : sous les différences bornées [formule], [formule]
• Borne de Chernoff multiplicative : pour [formule] et [formule], [formule] (pour [formule])
• Lemme de Hoeffding : si [formule] et [formule], alors [formule]

Exemples importants

• Pile ou face : [formule] par Hoeffding
• Concentration de la médiane empirique
• Taille d'échantillon pour un sondage avec marge d'erreur [formule] et confiance [formule]

Erreurs courantes

• Appliquer Hoeffding à des variables non bornées
• Oublier l'hypothèse d'indépendance dans Hoeffding et McDiarmid
• Confondre les bornes additives et multiplicatives de Chernoff

Conseils du jury

• La démonstration de l'inégalité de Hoeffding (via le lemme) est un développement apprécié
• Savoir comparer la qualité des différentes bornes sur des exemples
• Le jury apprécie les applications modernes (apprentissage, algorithmes randomisés)

Développements associés

• Inégalité de Hoeffding
• Bornes de Chernoff
• Méthode de Monte Carlo
• Inégalité de Tchebychev

Prérequis

variables aleatoires discretes, fonctions convexes, loi grands nombres