Inégalité de Chernoff

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

L'inégalité de Chernoff est un résultat de théorie des probabilités. 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.

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

Soient X_1,X_2,\dots,X_n des variables aléatoires indépendantes, telles que E[X_i]=0 et \left|X_i\right|\leq 1\, pour tout i. On pose X=\sum_{i=1}^n X_i et on appelle σ2 la variance de X.

Alors, on a pour tout 0 \leq k \leq 2 \sigma\, :

P(\left|X\right|\geq k\sigma)\leq 2e^{-k^2/4}

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

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

P(\frac{1}{n}\sum_{i=1}^{n} X_i > p + \epsilon) \leq e^{-2\epsilon^2n}, et P(\frac{1}{n}\sum_{i=1}^{n} X_i < p - \epsilon) \leq e^{-2\epsilon^2n}.

Preuve[modifier | modifier le code]

Applications[modifier | modifier le code]


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