Inégalité de Chernoff

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Chernoff.

En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée. On parle également de borne de Chernoff.

Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle. Elle porte le nom de Herman Chernoff.

Énoncés[modifier | modifier le code]

Il existe de nombreux énoncés, et de nombreux cas particuliers.

Cas général[modifier | modifier le code]

Soit une variable aléatoire réelle dont la fonction génératrice des moments est telle que :

Alors[1], pour tout ,

et

Avec des variables symétriques et une espérance nulle[modifier | modifier le code]

Soient des variables aléatoires indépendantes, telles que et pour tout i. On pose et on appelle σ2 la variance de X.

Alors, on a pour tout  :

Avec des variables symétriques booléennes[modifier | modifier le code]

Soient des variables aléatoires booléennes (i.e. à valeurs dans {0,1}) indépendantes, de même espérance p, alors ,

, et .

Preuve[modifier | modifier le code]

Il existe plusieurs manières de prouver ces inégalités[2].

Cas général

Avec des variables symétriques booléennes

Applications[modifier | modifier le code]

Ces inégalités sont très utilisées en informatique théorique, notamment en théorie de la complexité et en algorithmique, où elle permettent de prouver des résultats sur les algorithmes probabilistes.

Voir aussi théorie des grandes déviations.

Extensions[modifier | modifier le code]

On peut écrire des généralisation intéressantes pour les matrices aléatoires, appelées en anglais matrix Chernoff bound (en)[3].

Références[modifier | modifier le code]

  1. Brémaud 2009, p. 184
  2. Wolfgang Mulzer, « Five Proofs of Chernoff’s Bound with Applications », Bulletin of the EATCS, no 124,‎ (lire en ligne).
  3. Joel A Tropp, « User-friendly tail bounds for sums of random matrices », Foundations of Computational Mathematics, vol. 12, no 4,‎ , p. 389-434

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]