Inégalité de Chernoff

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 (de).

É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

est la transformée de Cramer de  :

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]

Cas général

Avec des variables symétriques booléennes

Applications[modifier | modifier le code]

Voir 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)[2].

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

  1. Brémaud 2009, p. 184
  2. 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]