Inégalité de Hoeffding

Restez toujours informé : suivez-nous sur Google (☆)

L’inégalité de Hoeffding 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, accroissements là encore bornés : cette version plus générale est parfois connue sous le nom d'inégalité d'Azuma-Hoeffding.

Inégalité de Hoeffding — Soit une suite $\scriptstyle\ (X_k)_{1\le k\le n}\$ de variables aléatoires réelles indépendantes vérifiant, pour deux suites $\scriptstyle\ (a_k)_{1\le k\le n},\$ $\scriptstyle\ (b_k)_{1\le k\le n}\$ de nombres réels tels que $\scriptstyle\ a_k<b_k,\$

\forall k, P (a_{k} \leq X_{k} \leq b_{k}) = 1.

On pose

S_{n} = X_{1} + X_{2} + \dots + X_{n} .

Alors, pour tout $\scriptstyle\ t>0,\$

P (S_{n} - E [S_{n}] \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} ( b _{i} - a _{i} ) ^{2}}), P (S_{n} - E [S_{n}] \leq - t) \leq exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} ( b _{i} - a _{i} ) ^{2}}), P (∣ S_{n} - E [S_{n}] ∣ \geq t) \leq 2 exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} ( b _{i} - a _{i} ) ^{2}}) .

Bornes pour la dispersion de la loi binomiale de paramètres n et p=0,5, obtenues respectivement à l'aide de l'inégalité de Bienaymé-Tchebychev et à l'aide de l'inégalité de Hoeffding.

Cas de la loi binomiale :

Supposons que

P (X_{k} = 1) = 1 - P (X_{k} = 0) = p .

Alors $\scriptstyle\ S_n\$ suit la loi binomiale de paramètres n et p. Les inégalités de Bienaymé-Tchebychev et Hoeffding donnent respectivement

P (∣ S_{n} - E [S_{n}] ∣ \geq x n) \leq \frac{p ( 1 - p )}{x ^{2}}, P (∣ S_{n} - E [S_{n}] ∣ \geq x n) \leq 2 exp (- 2 x^{2}) .

On voit que dans ce cas (et c'est assez représentatif de la situation générale) l'inégalité de Hoeffding est beaucoup plus précise pour $\scriptstyle\ x\$ suffisamment grand.