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 \scriptstyle X une variable aléatoire réelle dont la fonction génératrice des moments est telle que :

\phi(t)=\mathbb E[e^{tX}]<+\infty,

Alors[1], pour tout \scriptstyle a>0,

\mathbb P\left(X\geq a\right)\leq e^{-h(a)} et
\mathbb P\left(X\leq -a\right)\leq e^{-h(-a)}

\scriptstyle h est la transformée de Cramer de \scriptstyle X : \scriptstyle 
    h(x) = \begin{cases} \sup_{t \geq 0} \{xt + \log(\phi(t))\} & \text{ si }x>0 \\ \sup_{t \leq 0} \{-xt - \log(\phi(t))\} & \text{ si }x\leq 0 \end{cases}

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 \mathbb 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\, :

\mathbb 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

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

Preuve[modifier | modifier le code]

Applications[modifier | modifier le code]

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]