Inégalité de 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 nommée ainsi en l'honneur du mathématicien Herman Chernoff.

Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle.

Énoncés

modifier

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

Cas général

modifier

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

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  :

  ainsi que  ,
et donc aussi  .

Avec des variables symétriques booléennes

modifier

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

 , et  .

Démonstration

modifier

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

Cas général

Avec des variables symétriques booléennes

Applications

modifier

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

Voir aussi théorie des grandes déviations.

Extensions

modifier

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

Références

modifier
  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

Bibliographie

modifier