Inégalité de Hoeffding

L'inégalité de Hœffding est une inégalité de concentration concernant les sommes de variables aléatoires indépendantes et bornées.



Catégories :

Inégalité - Probabilités

Page(s) en rapport avec ce sujet :

  • Le second résultat est une inégalité de Hœffding. Théor`eme 3.2. Soit (Xi) i∈Z une suite strictement stationnaire de variables aléatoires `a valeurs dans ... (source : lsta.upmc)
  • (Une inégalité de Hœffding). 1. Soit Z une variable aléatoire réelle vérifiant a ≤ Z ≤ b presque sûrement. On se... (source : math.univ-paris13)
  • Donner une majoration de αn utilisant l'inégalité de Hœffding. Quelle... Peut- on appliquer l'inégalité de Hœffding `a N directement ? indirectement ?... (source : iecn.u-nancy)

L'inégalité de Hœffding est une inégalité de concentration concernant les sommes de variables aléatoires indépendantes et bornées. Il existe une version plus générale de cette inégalité, concernant une somme d'accroissements de martingales, ici encore bornés : cette version plus générale est quelquefois connue sous le nom d'inégalité d'Azuma-Hœffding.

Inégalité de Hœffding — Soit une suite de variables aléatoires réelles indépendantes vérifiant, pour deux suites de nombres réels tels que

\forall k,\qquad \mathbb{P}(a_k\le X_k\le b_k)=1.

On pose

S_n=X_1+X_2+\dots+X_n.

Alors, pour tout 0, \ " src="http ://upload. wikimedia. org/math/f/5/7/f57e25ed75688c1f85777e6a232d42a2. png" />

\begin{align}
\mathbb{P}\left(S_n-\mathbb{E}[S_n]\ge t\right)
&\le\exp\left(-\frac{2\,tˆ2}{\sum_{i=1}ˆn(b_i-a_i)ˆ2}\right),
\\
\mathbb{P}\left(S_n-\mathbb{E}[S_n]\le -t\right)
&\le\exp\left(-\frac{2\,tˆ2}{\sum_{i=1}ˆn(b_i-a_i)ˆ2}\right),
\\
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge t\right)
&\le 2\exp\left(-\frac{2\,tˆ2}{\sum_{i=1}ˆn(b_i-a_i)ˆ2}\right).
\end{align}
Limites pour la dispersion de la loi binomiale de paramètres n et p=0, 5, obtenues respectivement avec l'inégalité de Bienaymé-Tchebychev ainsi qu'avec l'inégalité de Hœffding.
Cas de la loi binomiale :

Supposons que Alors suit la loi binomiale de paramètres n et p. Les inégalités de Bienaymé-Tchebychev et Hœffding donnent respectivement

\begin{align}
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge x\sqrt{n}\right)
&\le \frac{p(1-p)}{xˆ2},
\\
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge x\sqrt{n}\right)
&\le 2\exp\left(-2\,xˆ2\right).
\end{align}

On voit que dans ce cas (et c'est assez représentatif de la situation générale) l'inégalité de Hœffding est bien plus précise pour suffisamment grand.

Voir aussi

Pages liées

Bibliographie

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/In%C3%A9galit%C3%A9_de_Hoeffding.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu