Chernov (inégalité de)

Un service reçoit 100 requêtes indépendantes. Chacune a une probabilité de 0,1 d’échouer, donc on attend 10 échecs en moyenne. Il reste possible d’en observer 20, mais ce grand écart devient rapidement improbable.

L’inégalité de Chernov transforme cette intuition en garantie chiffrée. Sans calculer toutes les issues possibles, elle majore la probabilité que le total s’éloigne fortement de sa moyenne. Plus le seuil s’éloigne de l’espérance, plus la borne diminue de façon exponentielle.

L’inégalité de Chernov, souvent orthographiée Chernoff, désigne une famille de bornes de concentration. Elle s’applique à une somme de variables aléatoires indépendantes en contrôlant sa fonction génératrice des moments. Pour une somme $S={\sum }_{i=1}^n{X}_{i}S=\backslash sum\_\{i=1\}^\{n\}X\_i$, on compare une déviation à l’espérance de la somme, notée $\mu =\mathbb{E}[S]\backslash mu=\backslash mathbb\{E\}[S]$.

Dans le cas courant où les variables X_i sont indépendantes et valent 0 ou 1, une forme multiplicative majore la probabilité que S dépasse son espérance d’une proportion donnée. L’indépendance est essentielle à cette factorisation. La version précise dépend du domaine des variables et du côté de la déviation étudiée ; l’expression donnée dans l’énoncé concerne la queue supérieure de variables de Bernoulli.

La borne ne donne pas la probabilité exacte. Elle fournit une garantie calculable qui décroît exponentiellement avec l’espérance et l’ampleur relative de l’écart. C’est ce comportement qui la rend utile pour analyser des algorithmes probabilistes.

Soient X₁, …, X_n des variables de Bernoulli indépendantes, S leur somme et μ l’espérance de S. Pour tout nombre réel δ strictement positif, la queue supérieure vérifie :

Le paramètre δ mesure l’écart relatif au-dessus de l’espérance. Le membre de droite est une borne, non la valeur exacte de la probabilité.

La forme multiplicative affichée s’emploie lorsque chaque variable vaut 0 ou 1, que les variables sont indépendantes et que leur somme possède une espérance μ connue. Le seuil doit s’écrire comme un multiple 1 + δ de cette espérance, avec δ > 0 pour une déviation vers le haut.

Si les essais sont dépendants, la factorisation à l’origine de cette borne peut échouer : cent pannes déclenchées par une même coupure ne se comportent pas comme cent pannes indépendantes. Il faut alors utiliser un résultat adapté à la dépendance. Si les variables indépendantes sont bornées mais ne sont pas des variables de Bernoulli, une autre forme de Chernov ou une inégalité comme celle de Hoeffding convient mieux.

Un service traite 100 requêtes indépendantes. Pour chacune, la probabilité d’échec vaut 0,1. On cherche une garantie sur le risque d’observer au moins 20 échecs. Les données sont donc n = 100 essais, p = 0,1 et un seuil égal à 20.

1. Le nombre S d’échecs est une somme de 100 variables de Bernoulli indépendantes.
2. Son espérance vaut μ = 100 × 0,1 = 10 échecs.
3. Le seuil 20 s’écrit (1 + δ)μ. Comme 20 = 2 × 10, on obtient δ = 1.
4. On remplace μ et δ dans la borne :

La probabilité d’au moins 20 échecs est donc garantie inférieure ou égale à environ 2,1 %. Le contrôle est refaisable : 20 représente bien deux fois l’espérance 10, et (e/4)¹⁰ ≈ 0,021006. Le schéma met en regard l’espérance, le seuil choisi et cette majoration.

Dans l’analyse d’un algorithme probabiliste, on additionne souvent des événements élémentaires : collisions, erreurs ou choix défavorables. Chernov donne alors une garantie sur un dépassement rare sans énumérer toutes les exécutions.

Pour dimensionner un système, on fixe d’abord un seuil tolérable, puis on exprime son écart relatif à l’espérance. La borne permet de vérifier si le risque maximal obtenu respecte l’objectif.

Si seules la moyenne et une information très générale sont disponibles, Markov ou Bienaymé-Tchebychev demandent moins d’hypothèses. Quand les variables sont indépendantes et bornées, une borne exponentielle devient souvent plus informative.

Inégalité de Markov. Elle s’applique à une variable aléatoire positive à partir de son espérance, sans exiger une somme d’essais indépendants. Si l’on connaît seulement la positivité et la moyenne, Markov reste applicable alors que la forme multiplicative de Chernov ne l’est pas.

Inégalité de Bienaymé-Tchebychev. Elle contrôle un écart à la moyenne grâce à la variance. Pour une somme indépendante bornée, Chernov exploite davantage de structure et fournit une décroissance exponentielle ; si l’on ne connaît que la variance, Tchebychev reste le choix disponible.

Inégalité de Hoeffding. Elle borne aussi les déviations de sommes de variables indépendantes bornées, mais sa forme additive utilise directement les bornes de chaque variable. Le choix dépend donc des hypothèses et de la manière, additive ou relative, dont le seuil est exprimé.

Dépendance cachée. Des variables ayant chacune la bonne probabilité marginale ne suffisent pas. Si elles réagissent toutes à une cause commune, le symptôme est une accumulation de résultats simultanés ; il faut modéliser cette dépendance avant de choisir une borne.

Seuil non entier. Une somme de variables de Bernoulli prend des valeurs entières. Un événement comme S ≥ 19,4 équivaut donc à S ≥ 20 ; il faut arrondir le seuil dans le bon sens avant d’évaluer δ.

Borne supérieure, pas estimation. Dans l’exemple, 2,1 % est un plafond garanti, non une approximation de la probabilité réelle. Employer ce nombre comme fréquence prédite surestime généralement le risque ; un calcul binomial exact est nécessaire si la valeur exacte est recherchée.

Mauvais côté de la déviation. La formule donnée traite S au-dessus de μ et exige δ > 0. Pour un déficit sous l’espérance, il faut utiliser une borne de queue inférieure et ses propres conditions, au lieu de changer simplement le signe de δ.

La fiche variable aléatoire précise l’objet dont les réalisations sont additionnées et dont l’espérance sert de repère.

L’inégalité de Hoeffding offre une autre borne exponentielle lorsque les variables indépendantes sont bornées et que l’écart est exprimé de manière additive.