L’inégalité de Chernoff est une inégalité dite de concentration au même titre que l’inégalité de Markov et de Bienaymé-Tchebychev, à la différence qu’elle est hors programme. Cependant, c’est une inégalité super utile qui pourrait parfaitement s’adapter à un sujet technique de type Maths II. Avoir quelques notions autour de cette inégalité pourrait donc s’avérer être d’une grande utilité. Ainsi, nous développerons d’abord sa définition et ses cas particuliers pour certains types de variables aléatoires, permettant de simplifier l’expression de l’inégalité. Tu retrouveras ensuite une interprétation graphique à l’aide de Python. En bonus, tu trouveras à la fin une démonstration de cette inégalité qui fait intervenir un outil hors programme, mais qui reste toutefois compréhensible pour un préparationnaire aguerri.
Définition
Tout d’abord, précisons que l’inégalité de Chernoff s’applique à la somme de variables aléatoires indépendantes et identiquement distribuées (i.i.d.). Plus précisément, elle donne une borne supérieure pour la probabilité qu’une telle somme s’écarte de sa moyenne. La forme la plus courante de cette inégalité suppose que chaque variable aléatoire prend ses valeurs dans l’intervalle \([0, 1]\) et a une espérance \( \mu = \mathbb{E}[X_i] \).
Soit \( X_1, X_2, \dots, X_n \) des variables aléatoires indépendantes et identiquement distribuées, et soit \( S_n = X_1 + X_2 + \dots + X_n \) leur somme. Si \( \mu = \mathbb{E}[X_i] \) est l’espérance de chaque \( X_i \), alors l’inégalité de Chernoff fournit une estimation de la probabilité que \( S_n \) dévie de \( n\mu \), l’espérance de la somme.
La formule générale de l’inégalité de Chernoff s’écrit de la manière suivante pour \(t >0\) :
\[
\mathbb{P}(S_n – n\mu \geq t) \leq \exp\left(-\frac{2t^2}{n}\right)
\]
et de manière symétrique :
\[
\mathbb{P}(S_n – n\mu \leq -t) \leq \exp\left(-\frac{2t^2}{n}\right)
\]
Cela indique que la probabilité qu’une somme \( S_n \) soit éloignée de sa moyenne \( n\mu \) de plus de \( t \) diminue de manière exponentielle avec le carré de \( t \), ce qui suggère que des écarts importants soient extrêmement improbables, même pour des sommes de variables de grande taille (voir la partie sur l’interprétation graphique).
Cas particuliers pour différents types de lois
L’inégalité de Chernoff trouve des applications spécifiques pour différents types de distribution, notamment la loi binomiale et la loi de Poisson. Chacun de ces cas permet de mieux comprendre comment les propriétés de la distribution influencent la concentration des variables aléatoires.
Loi binomiale
La loi binomiale est une généralisation de la loi de Bernoulli, où chaque \( X_i \) suit une loi de Bernoulli indépendante, mais le nombre d’essais est plus grand. Soit \( X_i \sim B(p) \), et \( S_n = X_1 + X_2 + \dots + X_n \) suit une loi binomiale de paramètres \( n \) et \( p \), c’est-à-dire \( S_n \sim B(n, p) \). Dans ce cas, l’espérance est \( \mu = np \).
L’inégalité de Chernoff appliquée à cette situation donne :
\[
\mathbb{P}(S_n – np \geq t) \leq \exp\left(-\frac{2t^2}{n}\right)
\]
Voici donc une première application très simple de la formule.
Loi de Poisson
Si \( X_i \sim P(\lambda) \), alors l’espérance de \( X_i \) est \( \lambda \). Soit \( S_n = X_1 + X_2 + \dots + X_n \), où chaque \( X_i \) suit une loi de Poisson. Dans ce cadre, l’inégalité de Chernoff peut être appliquée pour estimer la probabilité d’une déviation significative de la somme \( S_n \) :
\[
\mathbb{P}(S_n – n\lambda \geq t) \leq \exp\left(-\frac{2t^2}{n}\right)
\]
Cette formule illustre que même dans un contexte où les variables suivent une loi de Poisson, la concentration autour de la moyenne est extrêmement forte.
Interprétation graphique (et Python)
Pour donner encore plus de sens à cette formule et à son utilité, il convient de montrer graphiquement en quoi la décroissance exponentielle du membre de droite permet une très bonne majoration de la probabilité du membre de gauche.
Voici un code Python qui permet de souligner cela et, encore plus important, le graphique qui en résulte pour montrer la décroissance exponentielle de l’expression de droite pour des grandes valeurs de \(t\).
Et le graphique qui en résulte :
Tu vois ainsi bien que lorsque \(t\) augmente, la probabilité maximale de \(\mathbb{P}(S_n \geq t\)) décroît d’autant plus rapidement.
Bonus : démonstration de l’inégalité de Chernoff dans le cas général
Cette démonstration n’est pas simple, mais accessible pour un élève de prépa en deuxième année très bien entraîné. Voyons-la dès à présent !
Soit \(S_n\) une somme de variables aléatoires indépendantes \( X_1, X_2, \dots, X_n \) avec une espérance égale pour chacune à \( \mu = \mathbb{E}[X_i] \).
Soit \( t > 0 \) et considérons la fonction génératrice exponentielle de \( S_n \), qui est définie par :
\[
M(\lambda) = \mathbb{E}[\exp(\lambda S_n)] = \mathbb{E}\left[\exp\left(\lambda \sum_{i=1}^{n} X_i\right)\right]
\]
En utilisant l’indépendance des \( X_i \), nous pouvons factoriser cette espérance :
\[
M(\lambda) = \prod_{i=1}^{n} \mathbb{E}[\exp(\lambda X_i)]
\]
Nous devons maintenant calculer \( \mathbb{E}[\exp(\lambda X_i)] \) pour une variable \( X_i \) prenant ses valeurs dans \( [0,1] \).
Puisque chaque \( X_i \) prend des valeurs dans \( [0, 1] \), la fonction \( \exp(\lambda X_i) \) est croissante par rapport à \( X_i \). Pour tout \( \lambda \), nous avons :
\[
\mathbb{E}[\exp(\lambda X_i)] = \int_0^1 \exp(\lambda x) f_{X_i}(x) dx
\]
De manière générale, nous savons que \( \mathbb{E}[\exp(\lambda X_i)] \leq \exp(\lambda \mu) \), car cela est une conséquence directe de l’inégalité de Jensen, étant donné que \( \exp(\lambda X_i) \) est une fonction convexe. Cette inégalité de Jensen appliquée aux espérances de variables aléatoires est hors programme, il n’est donc pas nécessaire de connaître cette propriété.
Nous utilisons ensuite l’inégalité de Markov pour estimer la probabilité que \( S_n \) dépasse \( n\mu + t \). Pour cela, nous appliquons l’inégalité de Markov à l’exponentielle de \( S_n \), en utilisant la borne \( M(\lambda) \) obtenue précédemment.
En utilisant \( t > 0 \) et \( \lambda > 0 \), nous avons :
\[
\mathbb{P}(S_n \geq n\mu + t) = \mathbb{P}(\exp(\lambda S_n) \geq \exp(\lambda (n\mu + t)))
\]
Par l’inégalité de Markov, cela est inférieur à :
\[
\mathbb{P}(\exp(\lambda S_n) \geq \exp(\lambda (n\mu + t))) \leq \frac{\mathbb{E}[\exp(\lambda S_n)]}{\exp(\lambda (n\mu + t))}
\]
Nous avons montré que \( \mathbb{E}[\exp(\lambda S_n)] = \prod_{i=1}^{n} \mathbb{E}[\exp(\lambda X_i)] \), et chaque terme \( \mathbb{E}[\exp(\lambda X_i)] \) est majoré par \( \exp(\lambda \mu) \). Donc :
\[
\mathbb{E}[\exp(\lambda S_n)] \leq \exp(n\lambda \mu)
\]
Ainsi, nous obtenons :
\[
\mathbb{P}(S_n \geq n\mu + t) \leq \frac{\exp(n\lambda \mu)}{\exp(\lambda (n\mu + t))} = \exp(-\lambda t)
\]
On est maintenant proche de la fin ! Il n’y a plus qu’à modifier un tout petit peu le membre de droite de l’inégalité. Pour obtenir l’inégalité la plus précise possible, il convient donc de minimiser l’expression \( \exp(-\lambda t) \) en fonction de \( \lambda \). Cela se fait en choisissant \( \lambda = \frac{t}{n\sigma^2} \), où \( \sigma^2 \) est la variance de \( X_i \).
En conclusion, l’inégalité de Chernoff fournit une borne exponentielle sur la probabilité que la somme des variables aléatoires dévie de sa moyenne et est généralement formulée sous la forme suivante :
\[
\mathbb{P}(S_n \geq n\mu + t) \leq \exp\left(-\frac{2t^2}{n\sigma^2}\right)
\]
Et de manière symétrique :
\[
\mathbb{P}(S_n \leq n\mu – t) \leq \exp\left(-\frac{2t^2}{n\sigma^2}\right)
\]
Ce résultat montre que les écarts significatifs par rapport à la moyenne deviennent de moins en moins probables à mesure que \( n \) augmente, avec une décroissance exponentielle.
Conclusion
Ainsi, l’inégalité de Chernoff est une inégalité de concentration hors programme, mais qui pourrait très bien faire l’objet d’un sujet de type Maths II ou d’une partie de sujet. Comme il n’y a pas eu, à ce jour, de sujet d’écrit sur cette inégalité, si tu veux t’entraîner sur un sujet d’oral autour de cette notion, il existe le sujet S1 de HEC voie mathématique approfondie de 2021 qui établit des inégalités relatives à Chernoff.
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
