Les inégalités de Markov et de Bienaymé-Tchebychev s’attachent à décrire le comportement d’une variable aléatoire, mais qu’en est-il des sommes de variables aléatoires ? L’inégalité de Hoeffding offre ici une borne précise sur la probabilité que la somme de variables aléatoires indépendantes s’écarte de son espérance. Cette inégalité est déjà tombée aux oraux HEC (sujet S12 de 2022) et pourrait faire l’objet d’une partie de sujet écrit type Maths I.
Introduction
Contrairement à l’inégalité de Markov, qui ne nécessite que l’espérance d’une variable aléatoire, et à l’inégalité de Bienaymé-Tchebychev, qui utilise la variance, l’inégalité de Hoeffding s’applique aux sommes de variables aléatoires indépendantes et bornées. Elle fournit une borne dite exponentielle (ce qui rend la formule satisfaisante) sur la probabilité que ces sommes s’écartent de leur espérance. Cette propriété rend l’inégalité de Hoeffding plus puissante pour analyser les variables aléatoires.
Toujours est-il que les inégalités de Markov et de Bienaymé-Tchebychev ont le mérite d’être plus générales, mais l’inégalité de Hoeffding offre des bornes plus serrées et plus informatives lorsque les variables aléatoires en question vérifient certaines hypothèses.
Dès lors, définissons cette inégalité, avant d’étudier quelques propriétés de celle-ci et des questions classiques qui pourraient tomber en Maths I, Maths II ou oral type HEC. En bonus, tu pourras trouver à la fin une démonstration de cette inégalité.
Définition
Soient \( X_1, X_2, \ldots, X_n \) des variables aléatoires indépendantes telles que \( a_i \leq X_i \leq b_i \) presque sûrement pour tout \( i \). Soit \( S_n = \sum_{i=1}^n X_i \). Alors, pour tout \( t > 0 \),
\[
P\left( \left| S_n – \mathbb{E}[S_n] \right| \geq t \right) \leq 2 \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right).
\]
Exemples d’application concrets : le lancer de pièces
Considérons \( n \) lancers de pièces équilibrées, où chaque lancer est représenté par une variable aléatoire \( X_i \) qui vaut 1 pour pile et 0 pour face. On a \( \mathbb{E}[X_i] = \frac{1}{2} \).
Soit \( S_n = \sum_{i=1}^n X_i \) le nombre total de « pile ». On peut utiliser l’inégalité de Hoeffding pour borner la probabilité que \( S_n \) s’écarte de son espérance \( \mathbb{E}[S_n] = \frac{n}{2} \).
Étude de l’inégalité
Symétrie
L’inégalité est symétrique, ce qui signifie qu’elle borne la probabilité que \( S_n \) soit supérieure ou inférieure à son espérance.
Bornes
Les variables doivent être bornées, c’est-à-dire qu’elles doivent prendre des valeurs dans un intervalle fini. Heureusement, c’est le cas de la plupart des variables aléatoires réelles et à densité étudiées dans le cadre du programme. Attention toutefois à bien vérifier cette propriété sur la variable à étudier.
Notons aussi que la borne de probabilité décroît exponentiellement avec le carré de l’écart \( t \) et est inversement proportionnelle à la somme des carrés des amplitudes des intervalles \( (b_i – a_i)^2 \). C’est cette vitesse de convergence qui assure la précision de l’inégalité de Hoeffding.
Questions classiques
Question 1
Utiliser l’inégalité de Hoeffding pour montrer que si \( X_1, X_2, \ldots, X_n \) sont des variables aléatoires i.i.d. de Bernoulli de paramètre \( p \), alors pour tout \( \epsilon > 0 \),
\[
P\left( \left| \frac{1}{n} \sum_{i=1}^n X_i – p \right| \geq \epsilon \right) \leq 2 \exp(-2n\epsilon^2).
\]
Solution Q1
Les variables \( X_i \) sont de Bernoulli de paramètre \( p \), donc \( X_i \) vaut 1 avec probabilité \( p \) et 0 avec probabilité \( 1-p \).
L’espérance de chaque \( X_i \) est \( \mathbb{E}[X_i] = p \).
Puisque \( X_i \) sont bornées entre 0 et 1, on peut appliquer l’inégalité de Hoeffding :
\[
P\left( \left| \frac{1}{n} \sum_{i=1}^n X_i – p \right| \geq \epsilon \right) \leq 2 \exp(-2n\epsilon^2).
\]
Question 2
Soient \( X_1, X_2, \ldots, X_n \) des variables aléatoires indépendantes telles que \( a \leq X_i \leq b \). Montrer que pour tout \( t > 0 \),
\[
P\left( \left| \frac{1}{n} \sum_{i=1}^n X_i – \mathbb{E}[X_i] \right| \geq t \right) \leq 2 \exp\left( \frac{-2nt^2}{(b-a)^2} \right).
\]
Solution Q2
Puisque \( X_i \) sont indépendantes et bornées entre \( a \) et \( b \), on peut appliquer l’inégalité de Hoeffding.
Soit \( S_n = \sum_{i=1}^n X_i \). L’espérance de \( S_n \) est \( \mathbb{E}[S_n] = n \mathbb{E}[X_i] \).
Utilisons alors l’inégalité de Hoeffding :
\[
P\left( \left| S_n – \mathbb{E}[S_n] \right| \geq nt \right) \leq 2 \exp\left( \frac{-2(nt)^2}{n(b-a)^2} \right) = 2 \exp\left( \frac{-2nt^2}{(b-a)^2} \right).
\]
En divisant par \( n \), on obtient bien comme voulu :
\[
P\left( \left| \frac{1}{n} S_n – \mathbb{E}[X_i] \right| \geq t \right) \leq 2 \exp\left( \frac{-2nt^2}{(b-a)^2} \right).
\]
Grâce à ces deux questions, tu peux remarquer que la formule n’est pas si difficile que ça à appliquer alors que sa définition paraît très complexe. En effet, l’expression \(\sum_{i=1}^n (b_i – a_i)^2\) se simplifie souvent, car on manipule régulièrement des variables aléatoires ayant les mêmes bornes.
BONUS : démonstration de l’inégalité de Hoeffding
L’exercice des oraux HEC Paris 2019 en voie approfondie s’attache à démontrer cette inégalité. Voyons ici une autre manière toutefois assez proche de démontrer cette propriété.
Soient \( X_1, X_2, \ldots, X_n \) des variables aléatoires indépendantes telles que \( a_i \leq X_i \leq b_i \) presque sûrement pour tout \( i \). Nous voulons montrer que pour tout \( t > 0 \),
\[
P\left( \left| \sum_{i=1}^n X_i – \mathbb{E}[\sum_{i=1}^n X_i] \right| \geq t \right) \leq 2 \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right).
\]
Considérons les variables centrées \( Y_i = X_i – \mathbb{E}[X_i] \). Ainsi, \( \mathbb{E}[Y_i] = 0 \) et \( a_i – \mathbb{E}[X_i] \leq Y_i \leq b_i – \mathbb{E}[X_i] \).
La fonction exponentielle est convexe (la dérivée seconde l’exponentielle est encore l’exponentielle qui est strictement positive sur \(\mathbb{R}\)). Cela signifie que pour toute variable aléatoire \( Z \),
\[
\mathbb{E}[\exp(Z)] \leq \exp(\mathbb{E}[Z]).
\]
C’est ici une application de l’inégalité de Jensen qui est hors programme pour son application probabiliste. Contentons-nous seulement d’admettre cette étape (à ce point, l’exercice d’oral HEC passe également par la convexité de l’exponentielle, mais énonce des sous-questions pour contourner ce problème du hors programme).
Pour une variable aléatoire \( Y_i \) bornée, nous pouvons borner son moment générateur. Comme la variable \( Y_i \) est centrée, pour \( s > 0 \),
\[\mathbb{E}[exp(sY_i)] \leq \exp \left( \frac{s^2 (b_i – a_i)^2}{8} \right)\]
Indice pour cette étape : il s’agit ici de borner la variance des \(Y_i\) en repartant de la définition de la variance et de remarquer que ces variables sont centrées.
Puisque les \( Y_i \) sont indépendantes,
\[
\mathbb{E}\left[ \exp\left( s \sum_{i=1}^n Y_i \right) \right] = \prod_{i=1}^n \mathbb{E}[\exp(sY_i)] \leq \prod_{i=1}^n \exp\left( \frac{s^2 (b_i – a_i)^2}{8} \right).
\]
Cela donne :
\[
\mathbb{E}\left[ \exp\left( s \sum_{i=1}^n Y_i \right) \right] \leq \exp\left( \frac{s^2 \sum_{i=1}^n (b_i – a_i)^2}{8} \right).
\]
Utilisons l’inégalité de Markov pour \( \exp(s \sum_{i=1}^n Y_i) \) :
\[
P\left( \sum_{i=1}^n Y_i \geq t \right) \leq \frac{\mathbb{E}\left[ \exp\left( s \sum_{i=1}^n Y_i \right) \right]}{\exp(st)}.
\]
En substituant la borne obtenue précédemment,
\[
P\left( \sum_{i=1}^n Y_i \geq t \right) \leq \exp\left( \frac{s^2 \sum_{i=1}^n (b_i – a_i)^2}{8} – st \right).
\]
Pour minimiser cette borne, choisissons \( s = \frac{4t}{\sum_{i=1}^n (b_i – a_i)^2} \). Ce choix de \(s\) provient de l’étude du minimum du polynôme du second degré \(\frac{s^2 \sum_{i=1}^n (b_i – a_i)^2}{8} – st\). En substituant cette valeur,
\[
P\left( \sum_{i=1}^n Y_i \geq t \right) \leq \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right).
\]
Par symétrie, la même borne s’applique pour \( P\left( \sum_{i=1}^n Y_i \leq -t \right) \).
En combinant les deux bornes (ce qui explique l’apparition du facteur \(2\)), nous obtenons l’inégalité de Hoeffding :
\[
P\left( \left| \sum_{i=1}^n X_i – \mathbb{E}[\sum_{i=1}^n X_i] \right| \geq t \right) \leq 2 \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right).
\]
Conclusion
En définitive, l’inégalité de Hoeffding est complètement hors programme, mais peut être redémontrée avec les outils du programme, ce qui en fait un parfait exercice technique pour une partie de Maths I ou d’exercice d’oral (plutôt HEC qu’ESCP). Il pourrait ainsi t’être utile de t’entraîner sur le sujet HEC S12 tombé en 2022.
Tu peux retrouver le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder à toutes nos autres ressources mathématiques !
